Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 36 ยท Partitions and Catalan Numbers

Integer Partitions

Count integer partitions: generate every partition of n, compute p(n) with dynamic programming, and compare partitions into distinct, odd and bounded parts.

A partition of a positive integer n is a way of writing n as a sum of positive integers where order does not matter. So 4 = 3 + 1 and 4 = 1 + 3 are the same partition. The number of partitions of n is written p(n).

The partitions of 4 are 4, 3+1, 2+2, 2+1+1, 1+1+1+1, so p(4) = 5. Partitions are different from compositions (where order matters and the count is 2^(n-1)), and unlike permutations they have no simple closed formula. We study them by generating them, counting them by dynamic programming, and finding identities.

Generating all partitions

We write each partition as a list of parts in non-increasing order, which removes the order ambiguity. The recursive generator picks the first (largest) part, then partitions the rest using parts no larger than it.

Counting with dynamic programming

To count without listing, use the coin-change idea: parts of size 1, 2, 3, ... are "coins" in unlimited supply, and p(n) is the number of ways to pay n. Process part sizes one at a time; for part size k, ways[s] += ways[s - k]. This is the product 1/((1-x)(1-x^2)(1-x^3)...), the generating function of p(n).

Python List partitions and count with DP

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.

p(6) = 11, and p(100) = 190,569,292. The numbers grow fast but not as fast as 2^n: roughly exp(pi sqrt(2n/3)) / (4 n sqrt3) (Hardy-Ramanujan), which you can see plotted in Practice Set: Advanced Counting.

Restricted partitions

Many natural questions limit the parts. The recursion stays the same; only the allowed part sizes change.

  • Distinct parts: no part repeats (5 + 3 + 1).
  • Odd parts: every part is odd.
  • At most k parts or largest part at most k.
  • Exactly k parts.

Run the comparison below and look at the columns.

Python Four kinds of restricted partitions

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.

Two coincidences jump out of the output:

  1. Distinct parts and odd parts always have the same count (1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ...). This is Euler's theorem, and the generating functions prove it: prod (1 + x^k) = prod 1/(1 - x^(2k-1)), because 1 + x^k = (1 - x^(2k))/(1 - x^k) and the even factors cancel.
  2. At most 3 parts equals largest part at most 3. This is no accident either: the next lesson explains it with Ferrers diagrams and conjugation.
flowchart TD
    A["Partitions of n"] --> B["Unrestricted: p(n)"]
    A --> C["Distinct parts"]
    A --> D["Odd parts"]
    C -. "Euler: equal counts" .- D
    A --> E["At most k parts"]
    A --> F["Largest part at most k"]
    E -. "conjugation: equal counts" .- F

Equal counts reveal hidden bijections.

Partitions versus other counting objects

  • Number of ways to write n as an ordered sum: compositions, 2^(n-1).
  • Partitions of n into exactly k parts equal partitions of n - k into at most k parts (subtract 1 from each part).
  • Partitions of a set (not a number) are counted by Stirling and Bell numbers.

Do not confuse "partition of an integer" with "partition of a set". The first counts multisets of numbers adding to n; the second splits labeled objects into groups.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is p(5), the number of integer partitions of 5?

    5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1 gives 7.
  2. 2. Which generating function has coefficients p(n)?

    Each part size k can be used any number of times, giving the factor 1/(1 - x^k).
  3. 3. Euler's theorem says the number of partitions of n into distinct parts equals the number of partitions of n into...

    The two infinite products are equal, so the counts agree for every n.
  4. 4. In the DP loop for p(n), why is the outer loop over part sizes?

    Adding part sizes one at a time fixes the order of kinds, so each multiset appears exactly once.

Summary

  • A partition is an unordered sum; p(n) counts them and has no simple closed formula.
  • Generate with a recursion on the largest part; count with coin-change DP in O(n^2).
  • Generating function: prod 1/(1 - x^k). Restrictions change the allowed part sizes.
  • Distinct parts equal odd parts (Euler); at most k parts equal largest part at most k.

Next: Ferrers Diagrams and Pentagonal Numbers