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 , a permutation can be thought of as a rearrangement of these integers where the integer in position is . Thus is the permutation , , .
Given a finite set with permutation , a cycle is an ordered equivalence class of elements of where is equivalent to if there exists an such that , where and is the composition of with . It is ordered so that follows . If, for example, a permutation of the integers 1 through 6 is denoted by , then the cycles are , , and . Here , and . The function also interchanges 3 and 6, and sends 4 to itself.
A lattice path is a directed path on the plane integer lattice . Unless otherwise specified, it consists of horizontal segments corresponding to the vector and vertical segments corresponding to the vector . For an example see Figure 26.9.2.
A k-dimensional lattice path is a directed path composed of segments that connect vertices in so that each segment increases one coordinate by exactly one unit.
A partition of a set is an unordered collection of pairwise disjoint nonempty sets whose union is . As an example, , , is a partition of .
A partition of a nonnegative integer is an unordered collection of positive integers whose sum is . As an example, is a partition of 13. The total number of partitions of is denoted by . See Table 26.2.1 for . For the actual partitions () for see Table 26.4.1.
The integers whose sum is are referred to as the parts in the partition. The example has six parts, three of which equal 1.