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

## I.2

(D. Carter) A*weighted tree*is a rooted ordered tree where each node is assigned a strictly positive integer weight. Find a ~-approximation for the total number of weighted trees of weight $N$.