# 1.   Combinatorial Structures and Ordinary Generating Functions

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

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