A *permutation* is a one-to-one and onto function from a non-empty set to
itself. If the set consists of the integers 1 through $n$, a permutation
$\sigma $ can be thought of as a rearrangement of these integers where the
integer in position $j$ is $\sigma \left(j\right)$. Thus $231$ is the permutation
$\sigma \left(1\right)=2$, $\sigma \left(2\right)=3$, $\sigma \left(3\right)=1$.

Given a finite set $S$ with permutation $\sigma $, a *cycle* is an ordered
equivalence class of elements of $S$ where $j$ is equivalent to $k$ if
there exists an $\mathrm{\ell}=\mathrm{\ell}\left(j,k\right)$ such that $j={\sigma}^{\mathrm{\ell}}\left(k\right)$, where
${\sigma}^{1}=\sigma $ and ${\sigma}^{\mathrm{\ell}}$ is the composition of $\sigma $ with
${\sigma}^{\mathrm{\ell}-1}$. It is ordered so that $\sigma \left(j\right)$ follows $j$. If, for
example, a permutation of the integers 1 through 6 is denoted by $256413$,
then the cycles are $\left(1,2,5\right)$, $\left(3,6\right)$, and $\left(4\right)$.
Here $\sigma \left(1\right)=2,\sigma \left(2\right)=5$, and $\sigma \left(5\right)=1$. The function $\sigma $
also interchanges 3 and 6, and sends 4 to itself.

A *lattice path* is a directed path on the plane integer lattice
$\left\{0,1,2,\mathrm{\dots}\right\}\times \left\{0,1,2.\mathrm{\dots}\right\}$.
Unless otherwise specified, it consists of horizontal segments corresponding to
the vector $\left(1,0\right)$ and vertical segments corresponding to the vector $\left(0,1\right)$.
For an example see Figure 26.9.2.

A *k-dimensional lattice path* is a directed path composed of segments
that connect vertices in ${\left\{0,1,2,\mathrm{\dots}\right\}}^{k}$ so that each segment increases
one coordinate by exactly one unit.

A *partition of a set* $S$ is an unordered collection of pairwise
disjoint nonempty sets whose union is $S$. As an example, $\left\{1,3,4\right\}$,
$\left\{2,6\right\}$, $\left\{5\right\}$ is a partition of $\left\{1,2,3,4,5,6\right\}$.

A *partition of a nonnegative integer* $n$ is an unordered collection of
positive integers whose sum is $n$. As an example, $\left\{1,1,1,2,4,4\right\}$ is a
partition of 13. The total number of partitions of $n$ is denoted by
$p\left(n\right)$. See Table 26.2.1 for $n=0\left(1\right)50$.
For the actual partitions ($\pi $) for $n=1\left(1\right)5$ see Table 26.4.1.

The integers whose sum is $n$ are referred to as the *parts* in the
partition. The example $\left\{1,1,1,2,4,4\right\}$ has six parts, three of which equal 1.

$n$ | $p\left(n\right)$ | $n$ | $p\left(n\right)$ | $n$ | $p\left(n\right)$ |
---|---|---|---|---|---|

0 | 1 | 17 | 297 | 34 | 12310 |

1 | 1 | 18 | 385 | 35 | 14883 |

2 | 2 | 19 | 490 | 36 | 17977 |

3 | 3 | 20 | 627 | 37 | 21637 |

4 | 5 | 21 | 792 | 38 | 26015 |

5 | 7 | 22 | 1002 | 39 | 31185 |

6 | 11 | 23 | 1255 | 40 | 37338 |

7 | 15 | 24 | 1575 | 41 | 44583 |

8 | 22 | 25 | 1958 | 42 | 53174 |

9 | 30 | 26 | 2436 | 43 | 63261 |

10 | 42 | 27 | 3010 | 44 | 75175 |

11 | 56 | 28 | 3718 | 45 | 89134 |

12 | 77 | 29 | 4565 | 46 | 1 05558 |

13 | 101 | 30 | 5604 | 47 | 1 24754 |

14 | 135 | 31 | 6842 | 48 | 1 47273 |

15 | 176 | 32 | 8349 | 49 | 1 73525 |

16 | 231 | 33 | 10143 | 50 | 2 04226 |