1.   Combinatorial Structures and Ordinary Generating Functions



I.1 Symbolic enumeration methods


I.2 Admissible constructions and specificationsInteger compositions


I.3 Integer compositions and partitions


I.4 Words and regular languages


I.5 Tree structures


I.6 Additional constructions


I.7 Perspective



Selected Exercises

Note I.23

Alice, Bob, and coding bounds. Alice wants to communicate $n$ bits of information to Bob over a channel (a wire, an optic fibre) that transmits 0,1-bits but is such that any occurrence of 11 terminates the transmission. Thus, she can only send on the channel an encoded version of her message (where the code is of some length $\ell\ge n$) that does not contain the pattern 11.


Note I.43

Fast determination of the Cayley-Polya numbers. Logarithmic differentiation of $H(z)$ provides for the $H_n$ a recurrence by which one computes $H_n$ in time polynomial in $n$. (Note: a similar technique applies to the partition numbers $P_n$.)


Selected Experiments

Program I.1

Determine the choice of four coins that maximizes the number of ways to change a dollar.


Program I.2

Write programs that estimate the rate of growth of the Cayley numbers and the partition numbers ($H_n/H_{n-1}$ and $P_n/P_{n-1}$). See Note I.43.