Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 68 · Counting

Advanced Counting

Count derangements, Catalan numbers, Stirling numbers and integer partitions, and meet generating functions, with each result computed and checked in Python.

The basic tools (sum, product, permutations, combinations) cover a great deal, but some famous counting problems need a new idea. How many ways can n letters go into n envelopes so that no letter reaches its own envelope? How many ways can you pair up n opening and n closing parentheses correctly? How many ways can a set be split into k groups, or a number written as a sum of smaller numbers?

These problems produce sequences with names: derangement numbers, Catalan numbers, Stirling numbers and partition numbers. Each has a recurrence you can program in a few lines, and each shows up all over computer science. At the end, you will see generating functions, a technique that turns a counting problem into polynomial multiplication. As always, we confirm every formula by counting the slow way on small cases.

Four famous sequences

Derangements Nothing lands in its own place.
Catalan Balanced brackets and binary trees.
Stirling Splitting a set into k groups.
Partitions Writing n as a sum of parts.
1 / 2

Derangements

A derangement of n objects is a permutation in which no object stays in its original position. Think of n people who each throw a hat into a pile and take a random one back: a derangement means nobody gets their own hat. The number of derangements is written D(n) (or !n).

Inclusion-exclusion from Counting Principles gives a formula. Start with all n! permutations, subtract those that fix at least one point, correct for double counting, and so on:

D(n) = n! · (1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!)

There is also a simple recurrence: D(n) = (n-1) · (D(n-1) + D(n-2)), with D(0) = 1 and D(1) = 0. The series in the brackets is the beginning of the series for 1/e, so D(n)/n! approaches 1/e ≈ 0.3679 very quickly. In a big pile of hats, the chance that nobody gets their own hat is about 37%, independent of the number of hats.

Python Derangements three ways

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.

Catalan numbers

The Catalan numbers are C(n) = C(2n, n) / (n + 1), giving 1, 1, 2, 5, 14, 42, 132, ... They count many unrelated-looking things, all of the same "nested" structure:

  • strings of n pairs of parentheses that are properly balanced, such as (()) and ()() for n = 2;
  • binary trees with n nodes;
  • ways to parenthesize a product of n+1 factors;
  • paths on a grid from one corner to the opposite corner that never cross the diagonal;
  • ways to triangulate a convex polygon with n+2 sides.

They satisfy the recurrence C(n+1) = Σ C(i) · C(n-i), summed for i from 0 to n. For parentheses, this says: the first opening bracket matches some closing bracket; the part inside holds i pairs and the rest holds the remaining n - i.

Python Catalan numbers: formula, recurrence, balanced strings

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 brute-force counter enumerates all 4ⁿ strings of length 2n, so it only works for small n, while the formula handles n = 30 instantly.

Stirling numbers of the second kind

The Stirling number S(n, k) counts the ways to partition an n-element set into exactly k non-empty, unlabelled blocks (see partitions in Power Sets and Cartesian Products). The recurrence mirrors Pascal's rule:

S(n, k) = k · S(n-1, k) + S(n-1, k-1)

The last element either goes into one of the k existing blocks of a partition of the other n-1 elements, or forms a block by itself. Starting values are S(0, 0) = 1 and S(n, 0) = S(0, k) = 0 otherwise. Adding up a whole row gives the Bell number B(n) = Σ S(n, k), the number of all partitions of the set.

There is a sibling family, the (unsigned) Stirling numbers of the first kind c(n, k), which count permutations of n objects that split into exactly k cycles. They satisfy c(n, k) = (n-1) · c(n-1, k) + c(n-1, k-1).

Python Stirling numbers and Bell numbers

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 Bell numbers at the end of each row are 1, 1, 2, 5, 15, 52, 203 and 877, matching the partition counts from the earlier lesson.

Integer partitions

An integer partition of n writes n as a sum of positive integers, ignoring order. The partitions of 4 are 4, 3+1, 2+2, 2+1+1 and 1+1+1+1, so p(4) = 5. (Compare with compositions, where 3+1 and 1+3 differ.) Do not confuse them with set partitions, which split a set.

There is no simple closed formula, but there is a neat recurrence on the largest part allowed: let p(n, m) be the number of partitions of n using parts at most m. Then

p(n, m) = p(n, m-1) + p(n-m, m)

Either no part equals m, or at least one part is m and you remove it. The values begin 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42.

Python Counting integer 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.

Generating functions: an introduction

A generating function stores a sequence as the coefficients of a power series: a0 + a1·x + a2·x² + .... Multiplying such series combines choices, which is exactly what the product rule does. That makes it a powerful counting machine.

Example: you may use any number of 1-coin, 2-coin and 5-coin. A choice of 1-coins contributes 1 + x + x² + x³ + ... (use 0, 1, 2, ... coins, each adding that amount). For 2-coins the series is 1 + x² + x⁴ + ..., and for 5-coins 1 + x⁵ + x¹⁰ + .... The product of the three series has, as the coefficient of xᵐ, the number of ways to pay exactly m. Integer partitions work the same way: the product over all k of 1 / (1 - xᵏ), where each factor is the series for "use the part k any number of times", has p(n) as its coefficient of xⁿ.

Truncated polynomial multiplication is all you need to try this.

Python Counting with generating functions

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.

Notice that the coin counts at position 10 and the brute-force count agree, and that the partition list matches the sequence from the previous section. The same machinery solves recurrences too, which is why generating functions are a favourite tool for exact counting.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. How many derangements are there of 4 objects?

    D(4) = 3 * (D(3) + D(2)) = 3 * (2 + 1) = 9. Of the 24 permutations of 4 objects, 9 move every object.
  2. 2. Which count does the Catalan number C(3) = 5 give?

    C(3) = 5 counts balanced strings with 3 pairs: ((())), (()()), (())(), ()(()) and ()()().
  3. 3. What does S(4, 2) = 7 mean?

    S(n, k) counts set partitions into k blocks: 3 ways with 2+2 (pairs) and 4 ways with 3+1 make 7.
  4. 4. How many integer partitions does 5 have?

    5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1 and 1+1+1+1+1 give 7 partitions.
  5. 5. In a generating function, what does multiplying two series correspond to?

    The coefficient of x^m in the product adds up all ways to split m between the two groups, which is the product rule at work.

Summary

  • Derangements D(n) count permutations with no fixed point; D(n) = (n-1)(D(n-1) + D(n-2)), and D(n)/n! tends to 1/e.
  • Catalan numbers C(2n, n)/(n+1) count balanced bracket strings, binary trees and triangulations.
  • Stirling numbers of the second kind S(n, k) count set partitions into k blocks; row sums are Bell numbers. Those of the first kind count permutations by their number of cycles.
  • Integer partitions satisfy p(n, m) = p(n, m-1) + p(n-m, m).
  • Generating functions encode a sequence as a series; multiplying series combines independent choices.

Next: Discrete Probability, where counting turns into chances.