The Lumenary · Advanced undergraduate

Enumerative combinatorics

Name: ______________________

Date: ______________________

You will learn to

Use ordinary generating functions for unlabelled structures and exponential generating functions for labelled ones, including the exponential formula
Derive the derangement formula $D(n) = n! \sum_{k=0}^{n} (-1)^k / k!$ by inclusion–exclusion and from its exponential generating function
Prove Euler's theorem that partitions into odd parts and partitions into distinct parts are equinumerous, by generating functions and by Glaisher's bijection
Prove Burnside's lemma and count colourings up to symmetry with it and with Pólya's cycle index
Relate the cycle structure of permutations to Stirling numbers and to the exponential formula

1.
How many derangements (permutations with no fixed point) does a set of $5$ elements have?
2.
How many partitions of $7$ into distinct parts are there?
3.
How many necklaces of $5$ beads, each bead one of $3$ colours, are there up to rotation?
4.
A student counts two-colour necklaces with $4$ beads up to rotation as $2^4 / 4 = 4$ . The true number is $6$ . What exactly goes wrong?
- A.Some colourings are fixed by non-trivial rotations, so their orbits have fewer than $4$ elements; dividing by $4$ undercounts those orbits.
- B.The rotation group has $8$ elements, not $4$ .
- C.Two colourings that are rotations of each other were counted as different.
- D.Nothing: the student forgot to round up $4$ to the next integer.
5.
Glaisher's bijection merges equal odd parts: $m$ copies of an odd number $k$ become the parts $2^{a} k$ for the powers $2^a$ in the binary expansion of $m$ . What is the image of the partition $3 + 3 + 3 + 1 + 1$ of $11$ ?
- A. $6 + 3 + 2$
- B. $9 + 2$
- C. $6 + 3 + 1 + 1$
- D. $8 + 2 + 1$
6.
Which exponential generating function counts the permutations of $\{1, \dots, n\}$ all of whose cycles have odd length?
- A. $\displaystyle \exp\Big(\sum_{k \text{ odd}} \frac{x^k}{k}\Big) = \sqrt{\frac{1 + x}{1 - x}}$
- B. $\displaystyle \frac{1}{1 - x}$
- C. $\displaystyle \exp\Big(x + \frac{x^3}{3!} + \frac{x^5}{5!} + \cdots\Big) = e^{\sinh x}$
- D. $\displaystyle \sum_{k \text{ odd}} \frac{x^k}{k}$
7.
In the proof of Burnside's lemma we used $\sum_{x \in X} |G_x| = |G| \cdot |X/G|$ . Which fact justifies this step?
- A.The orbit–stabiliser theorem $|G_x| \cdot |G \cdot x| = |G|$ , after which each orbit contributes $\sum_{x \in O} 1/|O| = 1$ .
- B.Lagrange's theorem: $|G_x|$ divides $|G|$ .
- C.Every stabiliser has the same size.
- D.Double counting the pairs $(g, x)$ with $g \cdot x = x$ .
8.
Mathlib writes fixedBy X g for the fixed set of g, stabilizer G x for the stabiliser and orbitRel.Quotient G X for the set of orbits. Which statement is Burnside's lemma (true for every finite group acting on a finite set)?
- A.∑ g : G, Fintype.card (fixedBy X g) = Fintype.card (orbitRel.Quotient G X) * Fintype.card G
- B.∑ g : G, Fintype.card (fixedBy X g) = Fintype.card (orbitRel.Quotient G X)
- C.Fintype.card (orbitRel.Quotient G X) = Fintype.card X / Fintype.card G
- D.∑ x : X, Fintype.card (stabilizer G x) = Fintype.card G
9.
Write necklaces(n, k) returning the number of necklaces of $n$ beads in $k$ colours up to rotation, using Corollary 8: $\frac1n \sum_{d \mid n} \varphi(d)\, k^{n/d}$ . Write your own totient function phi(d), and return an int.
Computational — Practice

Answer key — Enumerative combinatorics

1.
$D(4) = 3(2 + 1) = 9$ and $D(5) = 4(9 + 2) = 44$ . Check with the formula: $120\big(\frac12 - \frac16 + \frac1{24} - \frac1{120}\big) = 60 - 20 + 5 - 1 = 44$ , and $120/e \approx 44.15$ rounds to $44$ .
2.
$7$ , $6+1$ , $5+2$ , $4+3$ , $4+2+1$ : five. The partitions into odd parts are $7$ , $5+1+1$ , $3+3+1$ , $3+1+1+1+1$ , $1^7$ — also five, as Euler's theorem predicts. Glaisher's map pairs them: $5+1+1 \mapsto 5+2$ , $3+3+1 \mapsto 6+1$ , $3+1^4 \mapsto 4+3$ , $1^7 \mapsto 4+2+1$ .
3.
The identity fixes $3^5 = 243$ colourings, and each of the other four rotations fixes only the $3$ constant ones. By Burnside's lemma there are $\frac{243 + 4 \cdot 3}{5} = \frac{255}{5} = 51$ necklaces. Equivalently, $N(5, 3) = \frac15\big(\varphi(1) 3^5 + \varphi(5) 3^1\big)$ .
4.
Orbits have size $|G|/|G_x|$ , so colourings with symmetry have small orbits. Here the orbits are $\{RRRR\}$ , $\{WWWW\}$ , $\{RWRW, WRWR\}$ and three orbits of size $4$ (one red bead, one white bead, two adjacent red beads): $6$ in all. Burnside's lemma gives $\frac{16 + 2 + 4 + 2}{4} = 6$ .
5.
Three copies of $3$ : $3 = 2 + 1$ , giving parts $2 \cdot 3 = 6$ and $1 \cdot 3 = 3$ . Two copies of $1$ : $2 = 2^1$ , giving the part $2$ . Image: $6 + 3 + 2$ . Going back, $6 = 2 \cdot 3$ splits into two $3$ s, $3$ stays, and $2 = 2 \cdot 1$ splits into two $1$ s.
6.
A permutation with odd cycles is a set of odd cycles. There are $(k - 1)!$ cycles on a $k$ -set, so the connected pieces have EGF $\sum_{k \text{ odd}} (k-1)! \frac{x^k}{k!} = \sum_{k \text{ odd}} \frac{x^k}{k} = \frac12 \log \frac{1 + x}{1 - x}$ . By the exponential formula the answer is $\exp$ of this, $\sqrt{(1 + x)/(1 - x)}$ . Its coefficients times $n!$ are $1, 1, 1, 3, 9, 45, 225, \dots$ .
7.
By orbit–stabiliser, $|G_x| = |G| / |G \cdot x|$ . So $\sum_x |G_x| = |G| \sum_x \frac{1}{|G \cdot x|}$ , and grouping the $x$ by orbits, each orbit $O$ contributes $|O| \cdot \frac{1}{|O|} = 1$ . The sum is $|G| \cdot |X/G|$ .
8.
Statement a. For the trivial action of a group of order 2 on a single point: the fixed-point sum is $2$ , there is $1$ orbit, and $1 \cdot 2 = 2$ , consistent with a; b gives $2 = 1$ , false. Statement c is the naive count, and d holds only for a single orbit.
9.
```
from math import gcd

def phi(d):
    return sum(1 for a in range(1, d + 1) if gcd(a, d) == 1)

def necklaces(n, k):
    total = sum(phi(d) * k ** (n // d) for d in range(1, n + 1) if n % d == 0)
    return total // n
```
The division is exact because the sum equals $\sum_r |\mathrm{Fix}(\rho^r)| = n \cdot (\text{number of orbits})$ — so an inexact division would reveal a bug.