Compositions and partitions · Definition

Partition generating function

enumerative combinatoricscompositions and partitions

Before you start you need to know

Euler observed that counting partitions amounts to multiplying geometric series, one for each part size. That idea turns a counting problem into a product of series.

Definition

The partition generating function is the formal series \(\sum_{n\ge 0} p(n)\,x^n\), where \(p(n)\) counts the partitions of the integer \(n\).

\[\sum_{n\ge 0} p(n)x^n=\prod_{k\ge 1}\frac{1}{1-x^k}\]

Each part of size \(k\) may appear \(0,1,2,\dots\) times, contributing \(1+x^k+x^{2k}+\cdots=\frac{1}{1-x^k}\). Since the choices for different part sizes are independent, the generating function is the product \(\prod_{k\ge 1}\frac{1}{1-x^k}\). Expanding the product, the coefficient of \(x^n\) counts exactly the partitions of \(n\).

For example, for \(n=4\) the partitions are \(4,\ 3+1,\ 2+2,\ 2+1+1,\ 1+1+1+1\), so \(p(4)=5\). Expanding \(\prod_{k\ge1}\frac{1}{1-x^k}\) up to \(x^4\) gives \(1+x+2x^2+3x^3+5x^4+\cdots\), where the coefficient of \(x^4\) matches this count.

A typical mistake is confusing partitions with compositions. In a composition the order of the summands matters, so \(1+2\) and \(2+1\) are counted separately and the generating function becomes \(\frac{1}{1-x-x^2-\cdots}\). For partitions order does not matter, and the product above is the correct model.

Think about it

Why does the product of geometric series ignore the order of the summands, unlike \(1/(1-x-x^2-\cdots)\)?

The product chooses how many times each size k appears without regard to order, while compositions record the order of the summands.

Exercises 10

  1. What is the coefficient of \(x^1\) in \(\prod_{k\ge1}\frac{1}{1-x^k}\)?
  2. How many partitions does the integer 2 have?
  3. Which coefficient in the expansion of \(\prod_{k\ge1}\frac{1}{1-x^k}\) equals \(p(3)\)?
  4. What factor does the part of size \(k\) contribute to the generating function?
  5. What is the coefficient of \(x^2\) in \(\prod_{k\ge1}\frac{1}{1-x^k}\)?
  6. If \(p(n)\) is the number of partitions of \(n\), what is \(p(3)\)?
  7. Using \(1+x+2x^2+3x^3+5x^4+\cdots\), what is \(p(4)\)?
  8. What is the coefficient of \(x^5\) in \(\frac{1}{(1-x)(1-x^2)}\)?
  9. How many partitions of 4 have all their parts equal to 1 or 2?
  10. Let \(F(x)=\prod_{k\ge1}\frac{1}{1-x^k}\). What is the coefficient of \(x^5\) in \(F(x)\)? Hint: \(p(5)\) comes from counting all partitions of 5.

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.