§26.2 Basic Definitions

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 (j)$. Thus $231$ is the permutation $\sigma (1)=2$, $\sigma (2)=3$, $\sigma (3)=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 }(j,k)$ such that $j={\sigma }^{\mathrm{\ell }}(k)$, where ${\sigma }^1=\sigma$ and ${\sigma }^{\mathrm{\ell }}$ is the composition of $\sigma$ with ${\sigma }^{\mathrm{\ell }-1}$. It is ordered so that $\sigma (j)$ 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 (1)=2,\sigma (2)=5$, and $\sigma (5)=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 $\{0,1,2,\mathrm{\dots }\}\times \{0,1,2,\mathrm{\dots }\}$. Unless otherwise specified, it consists of horizontal segments corresponding to the vector $(1,0)$ and vertical segments corresponding to the vector $(0,1)$. For an example see Figure 26.9.2.

A k-dimensional lattice path is a directed path composed of segments that connect vertices in ${\{0,1,2,\mathrm{\dots }\}}^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, $\{1,3,4\}$, $\{2,6\}$, $\{5\}$ is a partition of $\{1,2,3,4,5,6\}$.

A partition of a nonnegative integer $n$ is an unordered collection of positive integers whose sum is $n$. As an example, $\{1,1,1,2,4,4\}$ 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(1)50$. For the actual partitions ($\pi$) for $n=1(1)5$ see Table 26.4.1.

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