Counting and Combinatorics of Microstates

Shuffle a deck of cards and you will almost certainly produce an ordering that has never existed before in the history of the universe — there are $52! \approx 8\times10^{67}$ of them, more than the number of atoms in our galaxy by many orders of magnitude. Statistical mechanics is built on exactly this kind of astronomical bookkeeping. Fix a macroscopic constraint — a total energy, a particle number, a magnetization — and ask the only question that matters: in how many microscopic ways can it be realized? That count is the multiplicity $\Omega$ , and Boltzmann's bridge $S = k_B \ln \Omega$ turns it straight into thermodynamics. The tools are humble. Three combinatorial patterns do almost all the work: the factorial $N!$ counts orderings, the binomial coefficient $\binom{N}{k}$ counts unordered selections, and the multinomial coefficient $N!/\prod_i n_i!$ counts ways to sort labelled objects into bins of fixed size. Every microstate count you will ever meet — spins up and down, atoms in the left and right halves of a box, quanta shared among oscillators — is one of these three in disguise. The entire subtlety lies in one question: what is distinguishable from what? Label the particles or not, allow a state to be multiply occupied or not, and the same Hamiltonian yields different counting rules and different equations of state. Because $N \sim 10^{23}$ , exact factorials are hopeless and Stirling's approximation (its own article) smooths them into extensive functions. That smoothing exposes the deepest fact of the whole enterprise: the multiplicity is so sharply spiked about its maximum that the most probable macrostate simply is equilibrium, to a precision no measurement could ever challenge. This article builds the counting toolkit, proves that one term of a combinatorial sum swallows the whole, and hands the results forward to the multiplicity function, the Boltzmann entropy, and the statistical ensembles.

Key takeaways

The multiplicity $\Omega$ — the number of microstates realizing a macrostate — is the master combinatorial object of statistical mechanics; its logarithm is the Boltzmann entropy $S=k_B\ln\Omega$ .
Three tools recur everywhere: permutations $N!$ , combinations $\binom{N}{k}$ , and the multinomial coefficient $N!/\prod_i n_i!$ that partitions labelled objects into bins.
The multinomial coefficients over all bin assignments sum to $k^N$ — a clean identity, and the springboard for showing that one term dominates the entire sum.
Distinguishability decides the count: classical labelling, Gibbs-corrected classical, and Bose/Fermi occupation counting are three different combinatorial problems for one physical system.
Stirling's approximation converts factorial counting into smooth, extensive entropies and makes the peak of $\Omega$ overwhelmingly dominant, with relative width $\sim 1/\sqrt{N}$ .
The Gibbs factor $1/N!$ for identical particles restores extensivity and defuses the Gibbs paradox.
Key idea: equilibrium thermodynamics is one combinatorial number — the multiplicity $\Omega$ of accessible microstates — and counting it correctly is entirely a matter of getting distinguishability right.

The core insight

Equilibrium thermodynamics is encoded in a single combinatorial quantity — the multiplicity $\Omega$ of accessible microstates — whose logarithm is the entropy; the whole art is counting microstates with the correct notion of distinguishability.

Where this lives today

Counting microstates is not a historical relic; it is a live computational engine. When no closed-form multiplicity exists — the three-dimensional Ising model, a folding protein, a spin glass — physicists estimate $\ln\Omega(E)$ , the density of states, directly by simulation. The Wang–Landau algorithm performs a random walk in energy that flattens the visited histogram and thereby reconstructs $\Omega(E)$ over hundreds of orders of magnitude; nested sampling does the analogous job for continuous phase spaces. These methods are exactly the numerical descendants of the hand-counting in this article, scaled to systems no pencil could touch. The same combinatorics underwrites information theory and modern computing. Shannon's entropy $H=-\sum_i p_i\ln p_i$ is the large- $N$ limit of the multinomial coefficient for messages with given symbol frequencies, so data compression and statistical mechanics count with the same tool. And the multinomial structure reappears wherever labelled things are sorted into bins with fixed totals — from the partition functions of lattice polymers to the combinatorial cores of machine-learning models over discrete configurations.

The physical picture

Every microstate count is really one of three questions about balls and boxes. In how many orders can I line up $N$ distinct balls? — that is $N!$ , the permutation count. In how many ways can I choose which $k$ of them go into one box, ignoring order inside? — that is the binomial $\binom{N}{k}$ . In how many ways can I sort them into several boxes of prescribed sizes $n_1, n_2, \dots$ ? — that is the multinomial $N!/\prod_i n_i!$ . Learn to see these three patterns and most of statistical mechanics becomes pattern recognition. Distinguishability is the entire game. Toss two coins and there are four labelled outcomes — HH, HT, TH, TT — but only three macrostates counted by heads: zero, one, or two. The middle macrostate is realized two ways and so is twice as likely; that "how many ways" factor is the multiplicity, and equilibrium sits wherever it is largest. Toss $N$ coins and the same logic gives a binomial $\binom{N}{n}$ that peaks razor-sharp at $n = N/2$ . The figure below shows that peak sharpening as $N$ grows — the flat, forgiving landscape of a handful of coins becoming a needle for a macroscopic number.

Figure

The binomial multiplicity sharpens into a needle as N grows — the microscopic origin of equilibrium

The magic of large $N$ is a paradox that is not one. The multiplicity $\Omega$ can be astronomically large — $\Omega \sim 10^{(10^{23})}$ for a mole — yet its logarithm is gently extensive, $\ln\Omega \propto N$ , a well-behaved thermodynamic quantity. And the peak of $\Omega$ as a function of any macroscopic variable is so narrow — absolute width $\propto \sqrt{N}$ but relative width $\propto 1/\sqrt{N}$ — that the system is found in the single most probable macrostate with effective certainty. That is why "most probable" and "average" become the same thing, and why thermodynamics is deterministic even though its foundation is a lottery. Quantum statistics changes counting at the root. For identical quantum particles the question "which particle is in which state?" is not merely hard, it is meaningless — the particles carry no labels. The right question is "how many particles occupy each state?", a different combinatorial problem whose answer forks into Bose–Einstein (any number per state) and Fermi–Dirac (at most one) counting. Classical Maxwell–Boltzmann statistics is the dilute limit where the fork does not matter. The figure below drives the point home with the smallest possible example: three particles, two states, three different answers.

Figure

Distinguishability sets the count: 3 particles into 2 states gives 8, 4, or 0

The core equations

The whole edifice rests on Boltzmann's identification of entropy with a count. It is worth stating first because every combinatorial tool below exists only to evaluate the $\Omega$ inside it.

S = k_B \ln \Omega \qquad (1)

where: $S$ — thermodynamic entropy of the macrostate; $k_B = 1.380649\times10^{-23}\ \mathrm{J/K}$ (exact, SI); $\Omega$ — number of microstates realizing the macrostate. Read it as: entropy is nothing but the log of a multiplicity, so learning to count $\Omega$ is learning thermodynamics. The two most basic counts distinguish whether the order of a selection matters. Permutations count ordered arrangements; combinations count unordered ones — the difference is exactly the $k!$ orderings of a chosen subset.

P(N,k)=\frac{N!}{(N-k)!},\qquad \binom{N}{k}=\frac{N!}{k!\,(N-k)!} \qquad (2)

where: $P(N,k)$ — ordered selections of $k$ from $N$ ; $\binom{N}{k}$ — unordered selections; $N!$ — orderings of $N$ distinct objects. In statistical mechanics the binomial is ubiquitous because most macrostates fix only "how many," never "which ones in which order." Sorting labelled objects into more than two bins generalizes the binomial to the multinomial coefficient — the workhorse of occupation counting.

\binom{N}{n_1,n_2,\dots,n_r}=\frac{N!}{n_1!\,n_2!\cdots n_r!},\qquad \sum_i n_i=N \qquad (3)

where: $n_i$ — objects placed in bin $i$ ; $r$ — number of bins (states, energy levels); $N=\sum_i n_i$ . This counts the distinct assignments of which labelled object lands in which bin, having divided out the irrelevant order within each bin. Summing the multinomial over all ways to split $N$ objects into $r$ bins gives a strikingly simple total — the identity that later lets one term dominate the whole.

\sum_{n_1+\cdots+n_r=N}\binom{N}{n_1,\dots,n_r} = r^{\,N} \qquad (4)

where: $r^N$ — the total number of ways to assign each of $N$ labelled objects independently to one of $r$ bins. The left side reorganizes that total by the macrostate $(n_1,\dots,n_r)$ ; the right side counts microstates directly, so the two must agree. Because $N\sim10^{23}$ , every factorial is evaluated through Stirling's approximation (its own article, serial 1132), which we invoke by name rather than re-derive.

\ln N! = N\ln N - N + \tfrac{1}{2}\ln(2\pi N) + \frac{1}{12N} + \cdots \qquad (5)

where: the leading $N\ln N - N$ is extensive and does all the thermodynamic work; the $\tfrac12\ln(2\pi N)$ term is subextensive and matters only for the width of a peak, not its position. The single most common count in the subject is the two-level (spin) multiplicity — a pure binomial in the number of excited units.

\Omega(N,n)=\binom{N}{n}=\frac{N!}{n!\,(N-n)!} \qquad (6)

where: $N$ — number of independent two-level units (e.g. spin- $\tfrac12$ moments); $n$ — number excited; $\Omega$ — microstates with exactly $n$ excited. Fixing the energy of a paramagnet fixes $n$ , so this one binomial carries the whole thermodynamics of the two-level system. Indistinguishable particles distributed among sublevels are counted by "stars and bars," and the Pauli-restricted count is a plain binomial — the two quantum statistics in one line each.

\Omega_{\mathrm{BE}}=\binom{n+g-1}{n},\qquad \Omega_{\mathrm{FD}}=\binom{g}{n} \qquad (7)

where: $n$ — identical particles to place; $g$ — available single-particle states (sublevels). Bosons: arrange $n$ stars among $g{-}1$ bars, any occupancy allowed. Fermions: choose which $n$ of the $g$ states are singly filled, none doubly. Finally, the classical ideal-gas count carries the Gibbs factor $1/N!$ that makes the entropy extensive — the seam where counting meets the Gibbs paradox (its own article, serial 1131).

\Omega_{\text{ideal}}\ \propto\ \frac{V^N}{N!}\times(\text{momentum-shell factor}) \qquad (8)

where: $V^N$ — spatial placements of $N$ molecules; $N!$ — permutations of identical molecules, divided out because relabelling produces no new physical microstate. Drop the $N!$ and the entropy stops being extensive; keep it and the paradox dissolves.

Derivation AThe multinomial theorem and the sum rule

The goal here is to prove the sum identity of equation (4) — that adding the multinomial coefficients over every macrostate returns $r^N$ — because that identity is the foundation of everything that follows: it is the statement that microstates are conserved no matter how you bin them, and it sets up the far deeper claim that a single macrostate swallows the entire sum. We prove it two ways so the physics is unmistakable: once by direct microstate counting, once from the algebraic multinomial theorem, and we check the two agree.

Step 1. Count microstates directly. Assign each of the $N$ labelled objects to one of $r$ bins, independently. Object 1 has $r$ choices, object 2 has $r$ choices, and so on, giving $r \times r \times \cdots = r^N$ total microstates. Why: independence of the assignments turns the joint count into a product of identical factors — this is the "microstate" side of the ledger, blind to how many landed in each bin.

Step 2. Reorganize by macrostate. Group those $r^N$ microstates by their occupation vector $(n_1,\dots,n_r)$ with $\sum_i n_i = N$ . The number of microstates sharing a given occupation vector is exactly the multinomial coefficient $\binom{N}{n_1,\dots,n_r}$ — the ways to choose which labelled objects fill each bin of prescribed size. Why: fixing the macrostate leaves free only the identities of the objects in each bin, and that is precisely what the multinomial counts.

Step 3. Equate the two ledgers. Summing the per-macrostate counts must recover the total, so

\sum_{n_1+\cdots+n_r=N}\binom{N}{n_1,\dots,n_r} = r^N.

Why: the same $r^N$ microstates are counted once directly and once after sorting into macrostates — conservation of microstates.

Step 4. Confirm from the multinomial theorem. Algebraically, $(x_1+\cdots+x_r)^N = \sum \binom{N}{n_1,\dots,n_r}\prod_i x_i^{n_i}$ . Setting every $x_i=1$ gives $r^N$ on the left and the coefficient sum on the right — identical to Step 3. Why: the algebra and the counting are the same statement viewed from two sides; the coefficients of a generating function are literally microstate counts. *Verified: symbolically in sympy for $r=2,3,4$ and $N$ up to 12 — the reorganized sum equals $r^N$ exactly in every case (see verify script).*

Go deeper · Derivation B · 1 minOne term swallows the whole sum

Derivation BOne term swallows the whole sum

Equation (4) says the $\binom{N+r-1}{r-1}$ macrostate terms add up to $r^N$ ; the astonishing fact of statistical mechanics is that almost all of that total lives in a single term — the most probable macrostate — with the rest exponentially negligible. This is the combinatorial heart of the Second Law: "the largest term equals the whole sum" is why the most probable macrostate is the only one ever observed. We prove it for the symmetric case, where the peak sits at equal occupations $n_i^\ast = N/r$ .

Step 1. Identify the largest term. By symmetry the multinomial $\binom{N}{n_1,\dots,n_r}$ is maximized at $n_i^\ast = N/r$ for all $i$ ; call that maximum term $\Omega_{\max}$ . Its value from Stirling is $\ln\Omega_{\max} \approx N\ln r - \tfrac{r-1}{2}\ln N + \text{const}$ . Why: equalizing the bins maximizes the product of factorials in the denominator's reciprocal — the flattest distribution has the most arrangements.

Step 2. Bound the number of terms. The number of distinct macrostates (occupation vectors) is $\binom{N+r-1}{r-1}$ , which grows only polynomially in $N$ (as $N^{r-1}$ ), not exponentially. Why: with $r$ fixed, the count of ways to write $N$ as an ordered sum of $r$ non-negative integers is a polynomial in $N$ of degree $r-1$ .

Step 3. Sandwich the total. Since every term is at most $\Omega_{\max}$ and there are at most $\binom{N+r-1}{r-1} \sim N^{r-1}$ of them,

\Omega_{\max} \ \le\ r^N\ =\ \sum \binom{N}{n_1,\dots,n_r}\ \le\ N^{r-1}\,\Omega_{\max}.

Why: the whole sum is trapped between one copy of the largest term and a polynomial number of them.

Step 4. Take logs and divide by $N$ . Because $\ln N^{r-1} = (r-1)\ln N$ is subextensive,

\frac{1}{N}\ln\Omega_{\max} \ \le\ \frac{1}{N}\ln r^N \ \le\ \frac{1}{N}\ln\Omega_{\max} + \frac{(r-1)\ln N}{N},

and the correction term vanishes as $N\to\infty$ . So $\tfrac1N\ln\Omega_{\max} \to \ln r = \tfrac1N\ln(\text{whole sum})$ . Why: on the extensive scale that entropy lives on, the largest term and the entire sum are indistinguishable — the polynomial prefactor is invisible against the exponential. *Verified: numerically for $r=2$ , the ratio $\ln\Omega_{\max}/\ln(2^N)\to 1$ (0.66 at $N=10$ , 0.94 at $N=10^3$ , $\to 1$ ), and the polynomial term-count bound holds exactly (see verify script).*

Limiting cases

The same physical system is counted differently depending on the statistics assumed — and the quantum counts collapse to the classical one when states are sparsely filled.

Case	Result	Meaning
Maxwell–Boltzmann (Gibbs-corrected)	$\Omega_{\mathrm{MB}}=\dfrac{1}{N!}\prod_i \dfrac{g_i^{n_i}}{n_i!}$	Labelled counting divided by $N!$ ; valid when occupations are dilute, $n_i\ll g_i$ .
Bose–Einstein	$\Omega_{\mathrm{BE}}=\prod_i \dbinom{n_i+g_i-1}{n_i}$	Any number of identical bosons per state; stars and bars in each level.
Fermi–Dirac	$\Omega_{\mathrm{FD}}=\prod_i \dbinom{g_i}{n_i}$	At most one fermion per state (Pauli); choose which $n_i$ of $g_i$ are filled.
Dilute limit $n_i\ll g_i$	$\Omega_{\mathrm{BE}},\,\Omega_{\mathrm{FD}}\to\Omega_{\mathrm{MB}}$	Both quantum counts reduce to the Gibbs-corrected classical form.
Single bin, $r=1$	$\Omega=1$ , $S=0$	Only one arrangement — no freedom, zero entropy.

Worked examples

1 · Four spins, counted by hand (confidence builder)

Enumerate every microstate of four independent spin- $\tfrac12$ moments, group them by the number $n$ of up-spins, and confirm the multiplicities sum to the total number of microstates.

Step 1. List the total. Each spin is up or down, so there are $2^4 = 16$ microstates in all — the number every macrostate count must add back up to.

Step 2. Count each macrostate with the binomial. The macrostate is fixed by $n$ , the number of up-spins, and its multiplicity is $\Omega(4,n)=\binom{4}{n}$ : $\binom{4}{0}=1$ (all down), $\binom{4}{1}=4$ , $\binom{4}{2}=6$ , $\binom{4}{3}=4$ , $\binom{4}{4}=1$ . Written out, $n=2$ really does have six arrangements: ↑↑↓↓, ↑↓↑↓, ↑↓↓↑, ↓↑↑↓, ↓↑↓↑, ↓↓↑↑.

Step 3. Sum and check. $1+4+6+4+1 = \mathbf{16} = 2^4$ — the multiplicities exactly exhaust the microstates, a tiny instance of the sum rule $\sum_n\binom{N}{n}=2^N$ .

Step 4. Read off equilibrium. The peak is at $n=2$ with $\Omega=6$ , six times more likely than either extreme. Even with only four spins, the balanced macrostate already dominates — and the domination sharpens without limit as $N$ grows, which is the whole content of the second derivation.

2 · A quantum of counting: three bosons versus three fermions (exam level)

Place three identical particles into two single-particle states. Count the microstates for bosons (stars and bars) and for fermions (Pauli), and explain the difference.

Step 1. Bosons — stars and bars. With $n=3$ identical particles and $g=2$ states, equation (7) gives $\Omega_{\mathrm{BE}}=\binom{n+g-1}{n}=\binom{4}{3}=\mathbf{4}$ . The four occupancy patterns are $(3,0),(2,1),(1,2),(0,3)$ — only "how many in each state" matters, never which particle.

Step 2. Fermions — Pauli. With at most one particle per state, three fermions cannot fit into two states: $\Omega_{\mathrm{FD}}=\binom{g}{n}=\binom{2}{3}=\mathbf{0}$ . The count is literally zero — exclusion makes the macrostate impossible.

Step 3. Contrast with labelled counting. If the particles wore labels, "3 into 2 states" would give $2^3=8$ microstates. Bosonic indistinguishability collapses those 8 into 4 physical states; fermionic exclusion forbids them outright. Same three particles, same two states, three different answers — 8, 4, and 0 — set entirely by distinguishability and occupancy rules.

Step 4. Recover the classical limit in your head. Were there $g=1000$ states instead of 2, the three particles would almost never want the same state, the correction between $\binom{g+n-1}{n}$ and $\binom{g}{n}$ would be negligible, and both would collapse to the Gibbs-corrected $g^n/n!$ — the dilute Maxwell–Boltzmann count.

Origins · 1 minbinomial coefficient and how this was discovered

binomial coefficient

counting since antiquity · the workhorse of microstate counting

The binomial coefficient $\binom{N}{k}$ — the number of ways to choose $k$ objects from $N$ regardless of order — is the single most-used tool in statistical mechanics, and its history predates the physics by centuries. The triangular array that generates it was known to the Chinese mathematician Yang Hui (13th century) and the Persian polymath Al-Karaji (10th century) long before Blaise Pascal systematized it in 1654; Jacob Bernoulli's posthumous Ars Conjectandi (1713) turned it into the foundation of probability. When Boltzmann counted the microstates of a gas in the 1870s he was, at bottom, evaluating binomials and their multinomial generalizations. Every two-level system, every paramagnet, every "how many up-spins" question in this book resolves to a binomial — which is why the humble $\binom{N}{k}$ , and the identity $\sum_n\binom{N}{n}=2^N$ it satisfies, deserves to be recognized as a physical object, not just an algebraic one.

History

1654

— Pascal and Fermat, in their correspondence on games of chance, systematize the binomial coefficients ("Pascal's triangle") and found probability theory.

1713

— Jacob Bernoulli's posthumous Ars Conjectandi establishes combinatorics and the law of large numbers, the mathematical backbone of microstate counting.

1730

— Stirling and de Moivre give the asymptotic form of

N!

, making large-

N

combinatorics tractable.

1877

— Boltzmann identifies entropy with the logarithm of a microstate count, turning combinatorics into thermodynamics.

1924

— Bose counts photon states by occupation number rather than by labelled particles, launching quantum statistics.

1926

— Fermi and Dirac introduce the exclusion-respecting count for half-integer-spin particles.

Going further

Texts. Pathria & Beale, Statistical Mechanics, 3rd ed., Ch. 1–3 · Kardar, Statistical Physics of Particles, Ch. 4 · Reif, Fundamentals of Statistical and Thermal Physics, Ch. 1–3 & Appendix A · Sethna, Statistical Mechanics: Entropy, Order Parameters, and Complexity, Ch. 3 · Landau & Lifshitz, Statistical Physics Part 1, §7, §40.

Provenance. All results are standard combinatorics and textbook statistical mechanics. A verifier should recompute: the multinomial sum rule $\sum\binom{N}{n_1,\dots,n_r}=r^N$ (Steps 1–4 of the first derivation; checked in sympy for $r=2,3,4$ ); the "largest term equals the whole sum" bound $\Omega_{\max}\le r^N\le N^{r-1}\Omega_{\max}$ and the limit $\tfrac1N\ln\Omega_{\max}\to\ln r$ (Reif Ch. 1, Kardar §4.3; checked numerically for $r=2$ ); the two-level binomial $\Omega=\binom{N}{n}$ with peak variance $N/4$ (Reif Ch. 1); the stars-and-bars $\binom{n+g-1}{n}$ and Fermi $\binom{g}{n}$ counts and their dilute collapse to $g^n/n!$ (Pathria Ch. 6). Historical dates (Pascal–Fermat 1654, Bernoulli 1713, Bose 1924, Fermi/Dirac 1926) are verified in the lane history gate. $k_B=1.380649\times10^{-23}\,\mathrm{J/K}$ is exact (2019 SI).

Builds on: Microstates and Macrostates · Fundamental Postulate of Equal A Priori Probabilities Leads to: The Multiplicity Function · Boltzmann Entropy · The Stirling Approximation · Indistinguishability and the Gibbs Paradox · Statistical Ensembles

If Ω is so astronomically large, how can it possibly be the "number" of anything?

It genuinely is a count, just an unimaginably big one. For a mole of gas $\Omega$ is roughly $10^{(10^{23})}$ — a 1 followed by about $10^{23}$ zeros, a number you could not physically write down. What tames it is the logarithm: $\ln\Omega \sim N$ is an ordinary extensive quantity of order Avogadro's number, and it is $\ln\Omega$ , not $\Omega$ , that becomes the entropy. So the count is real and finite; we simply never manipulate it directly, only its logarithm.

Why does the sum of all the multinomial terms equal exactly r^N?

Because both sides count the very same thing — the microstates — just organized differently. The right side, $r^N$ , assigns each of the $N$ labelled objects independently to one of $r$ bins. The left side first sorts those microstates by their occupation pattern $(n_1,\dots,n_r)$ and counts each pattern's members with a multinomial coefficient, then adds the patterns back up. Sorting and re-summing cannot change a total, so the two are equal. It is conservation of microstates, nothing more.

The sum has enormously many terms — how can one of them equal the whole sum?

The number of macrostate terms grows only polynomially in $N$ (like $N^{r-1}$ ), while the largest term grows exponentially (like $r^N$ ). An exponential swamps any polynomial, so on the extensive scale that entropy lives on — $\tfrac1N\ln(\cdot)$ — the largest term and the entire sum become indistinguishable. Concretely for coins, $\ln\binom{N}{N/2}/\ln 2^N$ climbs from 0.66 at $N=10$ to 0.94 at $N=1000$ and marches to 1. The "extra" terms are not zero, they are simply invisible against the peak.

Do I divide by N! always, or only sometimes?

Only for genuinely identical particles whose permutations you have already counted as distinct. The $1/N!$ undoes an overcount: if your counting treated "particle A here, particle B there" as different from "B here, A there" but the particles are identical, you inserted $N!$ spurious copies and must divide them out. If your objects are truly distinguishable (distinct lattice sites, labelled boxes), there is no overcount and no $N!$ . The tell is extensivity: with the correct factor, $S$ scales linearly with system size; without it, you get the Gibbs paradox.

Stars and bars gives boson counts — is there an intuitive picture?

Yes. To place $n$ identical particles into $g$ states, draw $n$ stars in a row and separate the states with $g-1$ vertical bars. For example ★★|★ means two particles in state 1 and one in state 2. Every distinct arrangement of the $n$ stars and $g-1$ bars is one microstate, and there are $\binom{n+g-1}{n}$ ways to choose which of the $n+g-1$ positions hold stars. The bars are the walls between shelves; the stars are indistinguishable balls you drop onto the shelves.

How is Shannon's information entropy the same as microstate counting?

Take a long message of $N$ symbols in which symbol $i$ appears with frequency $p_i$ . The number of distinct messages with those frequencies is the multinomial $N!/\prod_i (p_iN)!$ . Apply Stirling and divide by $N$ : $\tfrac1N\ln(\text{count}) \to -\sum_i p_i\ln p_i$ , which is exactly Shannon's $H$ . So the information content of a source and the entropy of a physical macrostate are the same large- $N$ limit of the same multinomial coefficient — Boltzmann and Shannon are counting with one tool.

Does correct counting need quantum mechanics, or is it purely classical bookkeeping?

The combinatorial tools — factorials, binomials, multinomials, stars and bars — are purely classical bookkeeping and were known centuries before quantum theory. What quantum mechanics supplies is the rule for what to count: that identical particles carry no labels (so you count occupation numbers, not "which particle where"), and that fermions obey exclusion (at most one per state). The $1/N!$ Gibbs factor was a classical patch anticipating this; quantum statistics makes it exact and adds the Bose/Fermi fork. The arithmetic is old; the physics decides which arithmetic applies.