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.Here is a first coding scheme: given the message $m=m_1m_2\cdots m_n$, where $m_j\in\{{\sf 0,1}\}$, apply the substitution: $\sf 0\mapsto \sf 00$ and $\sf 1\mapsto\sf 10$; terminate the transmission by sending $\sf 11$. This scheme has $\ell=2n+O(1)$, and we say that its rate is 2. Can one design codes with better rates? with rates arbitrarily close to 1, asymptotically?
Let $\cal C$ be the class of allowed code words. For words of length $n$, a code of length $L\equiv L(n)$ is achievable only if there exists a one-to-one mapping from $\{0,1\}^n$ into $\bigcup_{j=0}^L \cal C_j$, i.e., $2^n\le \sum_{j=0}^L C_j$. Find the OGF of $\cal C$ and use it to show that \[ L(n) \ge \lambda n +O(1), \qquad \lambda=\frac{1}{\log_2 \varphi}\doteq 1.440420, \quad \varphi=\frac{1+\sqrt{5}}{2}.\] Thus no code can achieve a rate better than $1.44$; i.e., a loss of at least 44% is unavoidable.
Note I.43
Fast determination of the Cayley-Polya numbers. Use logarithmic differentiation of $H(z)$ to provide for the $H_n$ a recurrence that can serve as the basis for computing $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 a program that estimates the rate of growth of the Cayley numbers ($H_n/H_{n-1}$). See Note I.43.
Program I.3
Write a program that estimates the rate of growth of the partition numbers ($P_n/P_{n-1}$). See Note I.43.
Web Exercises
I.1
(R. Brott) Give a ~-approximation for the number of ways to express $N$ as the sum of 1, 2, and 4 (unordered). For example, there are four such ways for $N=4$: 1+1+1+1, 1+1+2, 2+2, and 4.