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. Then $$ 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 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.