§26.2 Basic Definitions

Notes:: Table 26.2.1 is from Abramowitz and Stegun (1964, Table 24.5).
Referenced by:: §32.14
Permalink:: http://dlmf.nist.gov/26.2

¶ Permutation

Keywords:: permutations

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

Keywords:: 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

Keywords:: lattice paths

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

Defines:: $\mathop{p\/}\nolimits\!\left(n\right)$ : total number of partitions of $n$
Keywords:: partitions

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.

Table 26.2.1: Partitions $\mathop{p\/}\nolimits\!\left(n\right)$ .

$n$	$\mathop{p\/}\nolimits\!\left(n\right)$	$n$	$\mathop{p\/}\nolimits\!\left(n\right)$	$n$	$\mathop{p\/}\nolimits\!\left(n\right)$
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

Symbols:: $\mathop{p\/}\nolimits\!\left(n\right)$ : total number of partitions of $n$ and $n$ : nonnegative integer
Keywords:: partitions
Referenced by:: ¶ ‣ §26.2, §26.2
Permalink:: http://dlmf.nist.gov/26.2.T1