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