3: Generating Functions
( \newcommand{\kernel}{\mathrm{null}\,}\)
This textmap is stilll under construction. Please forgive us.
- 3.5: 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.6: 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.