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
II.1
(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.