# 3: Generating Functions

- Page ID
- 7151

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

**This textmap is stilll under construction. Please forgive us.**

- 3.4: Recurrence Relations
- A recurrence relation defines a sequence by expressing a typical term in terms of earlier terms. Note that some initial values must be specified for the recurrence relation to define a unique sequence. The starting index for the sequence need not be zero if it doesn't make sense or some other starting index is more convenient.

- 3.5: Catalan Numbers
- A rooted binary tree is a type of graph that is particularly of interest in some areas of computer science. The root is the topmost vertex. The vertices below a vertex and connected to it by an edge are the children of the vertex. It is a binary tree because all vertices have 0, 1, or 2 children. How many different rooted binary trees are there with n vertices? Let us denote this number by Cn; these are the Catalan numbers.