Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§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 σ can be thought of as a rearrangement of these integers where the integer in position j is σ(j). Thus 231 is the permutation σ(1)=2, σ(2)=3, σ(3)=1.

Cycle

Given a finite set S with permutation σ, a cycle is an ordered equivalence class of elements of S where j is equivalent to k if there exists an =(j,k) such that j=σ(k), where σ1=σ and σ is the composition of σ with σ-1. It is ordered so that σ(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 σ(1)=2,σ(2)=5, and σ(5)=1. 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 {0,1,2,}×{0,1,2.}. 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,}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 p(n). See Table 26.2.1 for n=0(1)50. For the actual partitions (π) 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.

Table 26.2.1: Partitions p(n).
n p(n) n p(n) n p(n)
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