Practice: Enumerative combinatorics

Enumerative combinatorics

Warm-upHuman

How many derangements (permutations with no fixed point) does a set of $5$ elements have?

Enumerative combinatorics

Warm-upHuman

How many partitions of $7$ into distinct parts are there?

Enumerative combinatorics

CoreHuman

How many necklaces of $5$ beads, each bead one of $3$ colours, are there up to rotation?

Enumerative combinatorics

CoreHuman

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?

Choose one

Some colourings are fixed by non-trivial rotations, so their orbits have fewer than

4

elements; dividing by

4

undercounts those orbits.The rotation group has

8

elements, not

4

.Two colourings that are rotations of each other were counted as different.Nothing: the student forgot to round up

4

to the next integer.

Enumerative combinatorics

CoreHuman

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$ ?

Choose one

6 + 3 + 2

9 + 2

6 + 3 + 1 + 1

8 + 2 + 1

Enumerative combinatorics

StretchHuman

Which exponential generating function counts the permutations of $\{1, \dots, n\}$ all of whose cycles have odd length?

Choose one

\displaystyle \exp\Big(\sum_{k \text{ odd}} \frac{x^k}{k}\Big) = \sqrt{\frac{1 + x}{1 - x}}

\displaystyle \frac{1}{1 - x}

\displaystyle \exp\Big(x + \frac{x^3}{3!} + \frac{x^5}{5!} + \cdots\Big) = e^{\sinh x}

\displaystyle \sum_{k \text{ odd}} \frac{x^k}{k}

Enumerative combinatorics

CoreHuman

In the proof of Burnside's lemma we used $\sum_{x \in X} |G_x| = |G| \cdot |X/G|$ . Which fact justifies this step?

Choose one

The orbit–stabiliser theorem

|G_x| \cdot |G \cdot x| = |G|

, after which each orbit contributes

\sum_{x \in O} 1/|O| = 1

.Lagrange's theorem:

|G_x|

divides

|G|

.Every stabiliser has the same size.Double counting the pairs

(g, x)

with

g \cdot x = x

.

Enumerative combinatorics

CoreFormal

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)?

Choose one

∑ g : G, Fintype.card (fixedBy X g) = Fintype.card (orbitRel.Quotient G X) * Fintype.card G∑ g : G, Fintype.card (fixedBy X g) = Fintype.card (orbitRel.Quotient G X)Fintype.card (orbitRel.Quotient G X) = Fintype.card X / Fintype.card G∑ x : X, Fintype.card (stabilizer G x) = Fintype.card G

Enumerative combinatorics

StretchComputational

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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.