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