# §26.2 Basic Definitions

## Permutation

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

## Cycle

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 $\ell=\ell(j,k)$ such that $j=\sigma^{\ell}(k)$, where $\sigma^{1}=\sigma$ and $\sigma^{\ell}$ is the composition of $\sigma$ with $\sigma^{\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 $(1,2,5)$, $(3,6)$, and $(4)$. Here $\sigma(1)=2,\sigma(2)=5$, and $\sigma(5)=1$. The function $\sigma$ also interchanges 3 and 6, and sends 4 to itself.

## Lattice Path

A lattice path is a directed path on the plane integer lattice $\{0,1,2,\ldots\}\times\{0,1,2,\ldots\}$. 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,\dots\}^{k}$ so that each segment increases one coordinate by exactly one unit.

## Partition

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 $\mathop{p\/}\nolimits\!\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.