# §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 , a permutation can be thought of as a rearrangement of these integers where the integer in position is . Thus 231 is the permutation , , .

## ¶ Cycle

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 256413, then the cycles are , , and 4. Here , and . The function also interchanges 3 and 6, and sends 4 to itself.

## ¶ Lattice Path

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.

## ¶ Partition

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.

Table 26.2.1: Partitions .
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