Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 39 ยท Getting Started

Combinatorics and Stirling's Approximation

Count arrangements with factorials and binomial coefficients, then learn Stirling's approximation ln N! = N ln N - N, the tool behind entropy calculations.

Counting microstates means counting arrangements. This lesson gives you the counting rules you need and the one approximation that makes counting practical for huge numbers: Stirling's approximation for the factorial.

Permutations and combinations

The factorial of a whole number N is N! = N ร— (Nโˆ’1) ร— ... ร— 2 ร— 1, with 0! = 1.

  • Permutations: N distinguishable objects can be ordered in N! ways.
  • Combinations: choosing n objects from N without caring about order can be done in
Text
C(N, n) = N! / ( n! (N โˆ’ n)! )

ways. This is the binomial coefficient, read "N choose n". It is symmetric, C(N, n) = C(N, Nโˆ’n), and satisfies ฮฃ_n C(N, n) = 2^N.

  • Multinomial: splitting N distinguishable objects into groups of sizes n_1, n_2, ..., n_k (with ฮฃ n_i = N) gives N! / (n_1! n_2! ... n_k!) arrangements.
Python Binomial coefficients and their sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The problem with big factorials

Even moderately large factorials overflow a calculator: 70! is about 1.2 ร— 10^100. For N ~ 10^23 you cannot compute N! at all, nor do you need to. What matters in statistical mechanics is ln N!, because entropy is the logarithm of a count.

Stirling's approximation

For large N:

Text
ln N! โ‰ˆ N ln N โˆ’ N

A more accurate version, handy when N is not huge, includes one more term:

Text
ln N! โ‰ˆ N ln N โˆ’ N + ยฝ ln(2ฯ€N)

The idea behind it: ln N! = ฮฃ ln k, which is well approximated by the integral โˆซ ln x dx = x ln x โˆ’ x from 1 to N. The extra ยฝ ln(2ฯ€N) is a small correction that grows only logarithmically.

For physics, N is typically 10^20 or larger, so N ln N โˆ’ N is accurate to a relative error far below anything measurable. Dropping the last term is standard.

Python How good is Stirling's approximation?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will see that the simple form is rough for N = 5 but excellent for N = 10^6, and the improved form is very accurate even for small N.

Applying it: entropy-sized counts

Let us count the ways to put n of N particles on the left side: ฮฉ = C(N, n). Taking the logarithm and applying Stirling to each factorial, with x = n/N:

Text
ln ฮฉ = N ln N โˆ’ n ln n โˆ’ (N โˆ’ n) ln(N โˆ’ n)
     = โˆ’N [ x ln x + (1 โˆ’ x) ln(1 โˆ’ x) ]

This function is zero at x = 0 and x = 1 and has its maximum, N ln 2, at x = 1/2. That matches ฮฃ C(N, n) = 2^N: the largest term carries essentially all of the logarithmic weight.

Python ln Omega per particle against the fraction x

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How sharp is the peak?

Near n = N/2 the binomial coefficient looks Gaussian. Writing n = N/2 + ฮด and expanding ln C(N, n) gives

Text
C(N, n) โ‰ˆ 2^N ยท โˆš(2/(ฯ€N)) ยท exp( โˆ’2ฮดยฒ / N )

The width of this Gaussian is ฯƒ = โˆšN / 2. For N = 10^22 that is 5 ร— 10^10, which sounds large but is only 5 ร— 10^-12 of N. In relative terms the peak is incredibly sharp, as lesson 1 hinted.

Python Compare the exact count with the Gaussian peak

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In code, never compute factorial(N) for large N. Use math.lgamma(N + 1), which returns ln N! directly and never overflows.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many ways can you choose 2 particles out of 6 to be excited (order does not matter)?

    C(6,2) = 6!/(2! 4!) = 15.
  2. 2. What is Stirling's approximation (leading terms)?

    For large N, ln N! is approximately N ln N - N.
  3. 3. Why is ln N! the quantity we care about rather than N! itself?

    Entropy is proportional to a logarithm of the number of microstates, and the counts themselves are astronomically large.
  4. 4. The sum of C(N, n) over all n equals which value?

    Each of N two-valued objects has 2 choices, so the total is 2^N.

Summary

  • N! counts orderings; C(N, n) = N!/(n!(Nโˆ’n)!) counts selections; multinomials split into several groups.
  • Stirling: ln N! โ‰ˆ N ln N โˆ’ N (add ยฝ ln(2ฯ€N) for better accuracy).
  • The count C(N, n) has a Gaussian peak at n = N/2 of width โˆšN/2.
  • In code use math.lgamma for ln N!.

Next: Constants and Units