# 2.   Labelled Structures and Exponential Generating Functions

## 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.

## 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.