Compositions and partitions · Definition

Pentagonal number theorem

enumerative combinatoricscompositions and partitions

Before you start you need to know

This result gives the complete power series expansion of Euler's product. It links the generating function of partitions to a very simple sum with coefficients \(\pm1\).

Definition

Euler's pentagonal number theorem states that the product \(\prod_{n\ge1}(1-x^n)\) equals an alternating sum of powers of \(x\) indexed by generalized pentagonal numbers.

\[\prod_{n\ge1}(1-x^n)=\sum_{k=-\infty}^{\infty}(-1)^k x^{k(3k-1)/2}\]

The exponents \(k(3k-1)/2\) for \(k\in\mathbb{Z}\) are the generalized pentagonal numbers, and their sign is \((-1)^k\). As a consequence, most coefficients of the product are zero, and only pentagonal exponents appear with nonzero coefficient.

For \(x^{5}\), the nearby pentagonal exponents are \(0,1,2,5,7\) with signs \(+,-,-,+,+\). Thus the coefficient of \(x^5\) in \(\prod(1-x^n)\) is \(+1\), which can be checked by expanding the first factors and counting combinations of distinct exponents.

A typical mistake is forgetting that \(k\) also runs over negative integers, so only the positive exponents \(1,2,5,7\) are included and the term \(x^{0}\) is lost. Another error is giving every term a positive sign, which ignores the alternation \((-1)^k\).

Think about it

What would happen to the expansion if only \(k\ge0\) were used?

Exponents such as \(2\) and \(7\), with nonzero coefficients, would be missing, so the expansion would be incomplete.

Exercises 10

  1. What sign does the term with exponent \(k(3k-1)/2\) have when \(k=1\) in the theorem's sum?
  2. What generalized pentagonal exponent is obtained with \(k=2\)?
  3. What exponent does \(k=-1\) give in \(k(3k-1)/2\)?
  4. What is the coefficient of \(x^{0}\) in \(\prod_{n\ge1}(1-x^n)\)?
  5. What is the sign of the \(x^{1}\) term in the expansion of the product?
  6. Compute the coefficient of \(x^{7}\) in \(\prod_{n\ge1}(1-x^n)\) using the pentagonal number theorem.
  7. How many exponents below 10 have a nonzero coefficient in \(\prod_{n\ge1}(1-x^n)\)?
  8. Is it true that every exponent \(m\) with nonzero coefficient in \(\prod_{n\ge1}(1-x^n)\) is even?
  9. Use the theorem to show that the coefficient of \(x^{22}\) in \(\prod_{n\ge1}(1-x^n)\) is 1, stating the value of \(k\).
  10. Let \(c_m\) be the coefficient of \(x^m\) in \(\prod_{n\ge1}(1-x^n)\). What is \(c_{15}\)?

References

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