2.   Labelled Structures and Exponential Generating Functions

II.1 Labelled classes

II.2 Admissible labelled constructions

II.3 Surjections, set partitions, and words

II.4 Alignments, permutations, and related structures

II.5 Labelled trees, mappings, and graphs

II.6 Additional constructions

II.7 Perspective

Selected Exercises

Note II.11

Balls switching chambers: the Ehrenfest model. Consider a system of two chambers $A$ and $B$ (also classically called "urns"). There are $N$ distinguishable balls, and, initially, chamber $A$ contains them all. At any instant $\frac{1}{2},\frac{3}{2},\ldots$, one ball is allowed to change from one chamber to the other. Let $E_{n}^{[\ell]}$ be the number of possible evolutions that lead to chamber $A$ containing $\ell$ balls at instant $n$ and $E^{[\ell]}(z)$ the corresponding EGF. Show that $$ E^{[\ell]}(z)=\binom{N}{\ell}(\cosh z)^\ell (\sinh z)^{N-\ell}, \qquad E^{[N]}(z)=(\cosh z)^N\equiv 2^{-N}(e^z+e^{-z})^N. $$ [Hint: the EGF $E^{[N]}$ enumerates mappings where each preimage has an even cardinality.] In particular, show that the probability that urn $A$ is again full at time $2n$ is $$ \frac{1}{2^NN^{2n}}\sum_{k=0}^{N} \binom{N}{k}(N-2k)^{2n}. $$ This famous model was introduced by Paul and Tatiana Ehrenfest in 1907, as a simplified model of heat transfer. It helped resolve the apparent contradiction between irreversibility in thermodynamics (the case $N\to\infty$) and recurrence of systems undergoing ergodic transformations (the case $N<\infty$).

Note II.31

Combinatorics of trigonometrics. Interpret $\tan{z\over 1-z}$, $\tan\tan z$, and $\tan(e^z-1)$ as EGFs of combinatorial classes.

Selected Experiments

Program II.1

Write a program to simulate the Ehrenfest mode (see Note II.11) and use it to plot the distribution of the number of balls in urn A after $10^3$, $10^4$ and $10^5$ steps when starting with $10^3$ balls in urn A and none in urn B.

Web Exercises


(E. Levin) Use analytic combinatorics to calculate a ~-approximation to the probability that a uniformly randomly chosen permutation of elements does not contain a 2-cycle.


Find a ~-approximation for the number of labeled ternary trees (rooted, ordered, each node has 0 or 3 children) whose labels increase on every path.