Compositions and partitions · Definition

Integer partition

enumerative combinatoricscompositions and partitions

Before you start you need to know

Partitions arise when counting ways to split a quantity into parts without regard to order. Their study connects enumerative combinatorics with generating functions.

Definition

A partition of an integer n is a way of writing n as a sum of positive integers, where the order of the summands does not matter. The number of partitions of n is denoted p(n).

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

A partition is usually written with its parts in non-increasing order, for example \(5=3+1+1\). Two partitions are equal when they have the same parts with the same multiplicities, and the function \(p(n)\) counts these classes. By Euler's generating function, \(p(n)\) is the coefficient of \(x^n\) in \(\prod_{k\ge 1}(1-x^k)^{-1}\), where each factor accounts for how many copies of the part \(k\) are used.

For \(n=4\) the partitions are \(4\), \(3+1\), \(2+2\), \(2+1+1\) and \(1+1+1+1\), so \(p(4)=5\). This direct count can be checked with the generating function, whose coefficient of \(x^4\) is also \(5\). This method is useful when the explicit list becomes too long.

A typical mistake is counting \(3+1\) and \(1+3\) as different partitions. Since order does not matter, both represent the same partition and should be counted once. It helps to always write the parts in decreasing order to avoid duplicates.

Think about it

What would happen to the count if the order of the summands mattered?

Each partition would become several different compositions, so the count would grow and would no longer be \(p(n)\).

Exercises 10

  1. How many partitions does the integer \(3\) have?
  2. Which of the following is a partition of \(5\)?
  3. How many partitions of \(4\) have exactly two parts?
  4. What is the number of partitions \(p(2)\)?
  5. Which partition of \(6\), written in non-increasing order, has all its parts equal to \(2\)?
  6. How many partitions does \(5\) have?
  7. How many partitions of \(6\) have all parts distinct?
  8. What is the coefficient of \(x^3\) in \(\prod_{k\ge 1}\frac{1}{1-x^k}\)?
  9. How many partitions of \(4\) have all parts odd?
  10. Let \(q(n)\) be the number of partitions of \(n\) into distinct parts. What is \(q(6)\), and which value makes \(q(6)=p(6)-\)(number of partitions of \(6\) with a repeated part) true?

References

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