What's New
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.9 Integer Partitions: Restricted Number and Part Size

Contents

§26.9(i) Definitions

pk(n) denotes the number of partitions of n into at most k parts. See Table 26.9.1.

26.9.1 pk(n)=p(n),
kn.

Unrestricted partitions are covered in §27.14.

Table 26.9.1: Partitions pk(n).
n k
0 1 2 3 4 5 6 7 8 9 10
0 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1
2 0 1 2 2 2 2 2 2 2 2 2
3 0 1 2 3 3 3 3 3 3 3 3
4 0 1 3 4 5 5 5 5 5 5 5
5 0 1 3 5 6 7 7 7 7 7 7
6 0 1 4 7 9 10 11 11 11 11 11
7 0 1 4 8 11 13 14 15 15 15 15
8 0 1 5 10 15 18 20 21 22 22 22
9 0 1 5 12 18 23 26 28 29 30 30
10 0 1 6 14 23 30 35 38 40 41 42

A useful representation for a partition is the Ferrers graph in which the integers in the partition are each represented by a row of dots. An example is provided in Figure 26.9.1.

Figure 26.9.1: Ferrers graph of the partition 7+4+3+3+2+1.

The conjugate partition is obtained by reflecting the Ferrers graph across the main diagonal or, equivalently, by representing each integer by a column of dots. The conjugate to the example in Figure 26.9.1 is 6+5+4+2+1+1+1. Conjugation establishes a one-to-one correspondence between partitions of n into at most k parts and partitions of n into parts with largest part less than or equal to k. It follows that pk(n) also equals the number of partitions of n into parts that are less than or equal to k.

pk(m,n) is the number of partitions of n into at most k parts, each less than or equal to m. It is also equal to the number of lattice paths from (0,0) to (m,k) that have exactly n vertices (h,j), 1hm, 1jk, above and to the left of the lattice path. See Figure 26.9.2.

\begin{picture}(170.0,110.0)(-25.0,0.0)\put(0.0,0.0){\circle*{2.0}}\put(20.0,0%
.0){\circle*{2.0}}\put(40.0,0.0){\circle*{2.0}}\put(60.0,0.0){\circle*{2.0}}%
\put(80.0,0.0){\circle*{2.0}}\put(100.0,0.0){\circle*{2.0}}\put(120.0,0.0){%
\circle*{2.0}}
\put(0.0,20.0){\circle*{2.0}}\put(20.0,20.0){\circle*{2.0}}\put(40.0,20.0){%
\circle*{2.0}}\put(60.0,20.0){\circle*{2.0}}\put(80.0,20.0){\circle*{2.0}}\put%
(100.0,20.0){\circle*{2.0}}\put(120.0,20.0){\circle*{2.0}}
\put(0.0,40.0){\circle*{2.0}}\put(20.0,40.0){\circle*{2.0}}\put(40.0,40.0){%
\circle*{2.0}}\put(60.0,40.0){\circle*{2.0}}\put(80.0,40.0){\circle*{2.0}}\put%
(100.0,40.0){\circle*{2.0}}\put(120.0,40.0){\circle*{2.0}}
\put(0.0,60.0){\circle*{2.0}}\put(20.0,60.0){\circle*{2.0}}\put(40.0,60.0){%
\circle*{2.0}}\put(60.0,60.0){\circle*{2.0}}\put(80.0,60.0){\circle*{2.0}}\put%
(100.0,60.0){\circle*{2.0}}\put(120.0,60.0){\circle*{2.0}}
\put(0.0,80.0){\circle*{2.0}}\put(20.0,80.0){\circle*{2.0}}\put(40.0,80.0){%
\circle*{2.0}}\put(60.0,80.0){\circle*{2.0}}\put(80.0,80.0){\circle*{2.0}}\put%
(100.0,80.0){\circle*{2.0}}\put(120.0,80.0){\circle*{2.0}}
\put(0.0,100.0){\circle*{2.0}}\put(20.0,100.0){\circle*{2.0}}\put(40.0,100.0){%
\circle*{2.0}}\put(60.0,100.0){\circle*{2.0}}\put(80.0,100.0){\circle*{2.0}}%
\put(100.0,100.0){\circle*{2.0}}\put(120.0,100.0){\circle*{2.0}}
\put(0.0,0.0){\line(1,0){4.0}}\put(8.0,0.0){\line(1,0){4.0}}\put(16.0,0.0){%
\line(1,0){4.0}}\put(24.0,0.0){\line(1,0){4.0}}\put(32.0,0.0){\line(1,0){4.0}}%
\put(40.0,0.0){\line(1,0){4.0}}\put(48.0,0.0){\line(1,0){4.0}}\put(56.0,0.0){%
\line(1,0){4.0}}\put(64.0,0.0){\line(1,0){4.0}}\put(72.0,0.0){\line(1,0){4.0}}%
\put(80.0,0.0){\line(1,0){4.0}}\put(88.0,0.0){\line(1,0){4.0}}\put(96.0,0.0){%
\line(1,0){4.0}}\put(104.0,0.0){\line(1,0){4.0}}\put(112.0,0.0){\line(1,0){4.0%
}}
\put(0.0,20.0){\line(1,0){4.0}}\put(8.0,20.0){\line(1,0){4.0}}\put(16.0,20.0){%
\line(1,0){4.0}}\put(24.0,20.0){\line(1,0){4.0}}\put(32.0,20.0){\line(1,0){4.0%
}}\put(40.0,20.0){\line(1,0){4.0}}\put(48.0,20.0){\line(1,0){4.0}}\put(56.0,20%
.0){\line(1,0){4.0}}\put(64.0,20.0){\line(1,0){4.0}}\put(72.0,20.0){\line(1,0)%
{4.0}}\put(80.0,20.0){\line(1,0){4.0}}\put(88.0,20.0){\line(1,0){4.0}}\put(96.%
0,20.0){\line(1,0){4.0}}\put(104.0,20.0){\line(1,0){4.0}}\put(112.0,20.0){%
\line(1,0){4.0}}
\put(0.0,40.0){\line(1,0){4.0}}\put(8.0,40.0){\line(1,0){4.0}}\put(16.0,40.0){%
\line(1,0){4.0}}\put(24.0,40.0){\line(1,0){4.0}}\put(32.0,40.0){\line(1,0){4.0%
}}\put(40.0,40.0){\line(1,0){4.0}}\put(48.0,40.0){\line(1,0){4.0}}\put(56.0,40%
.0){\line(1,0){4.0}}\put(64.0,40.0){\line(1,0){4.0}}\put(72.0,40.0){\line(1,0)%
{4.0}}\put(80.0,40.0){\line(1,0){4.0}}\put(88.0,40.0){\line(1,0){4.0}}\put(96.%
0,40.0){\line(1,0){4.0}}\put(104.0,40.0){\line(1,0){4.0}}\put(112.0,40.0){%
\line(1,0){4.0}}
\put(0.0,60.0){\line(1,0){4.0}}\put(8.0,60.0){\line(1,0){4.0}}\put(16.0,60.0){%
\line(1,0){4.0}}\put(24.0,60.0){\line(1,0){4.0}}\put(32.0,60.0){\line(1,0){4.0%
}}\put(40.0,60.0){\line(1,0){4.0}}\put(48.0,60.0){\line(1,0){4.0}}\put(56.0,60%
.0){\line(1,0){4.0}}\put(64.0,60.0){\line(1,0){4.0}}\put(72.0,60.0){\line(1,0)%
{4.0}}\put(80.0,60.0){\line(1,0){4.0}}\put(88.0,60.0){\line(1,0){4.0}}\put(96.%
0,60.0){\line(1,0){4.0}}\put(104.0,60.0){\line(1,0){4.0}}\put(112.0,60.0){%
\line(1,0){4.0}}
\put(0.0,80.0){\line(1,0){4.0}}\put(8.0,80.0){\line(1,0){4.0}}\put(16.0,80.0){%
\line(1,0){4.0}}\put(24.0,80.0){\line(1,0){4.0}}\put(32.0,80.0){\line(1,0){4.0%
}}\put(40.0,80.0){\line(1,0){4.0}}\put(48.0,80.0){\line(1,0){4.0}}\put(56.0,80%
.0){\line(1,0){4.0}}\put(64.0,80.0){\line(1,0){4.0}}\put(72.0,80.0){\line(1,0)%
{4.0}}\put(80.0,80.0){\line(1,0){4.0}}\put(88.0,80.0){\line(1,0){4.0}}\put(96.%
0,80.0){\line(1,0){4.0}}\put(104.0,80.0){\line(1,0){4.0}}\put(112.0,80.0){%
\line(1,0){4.0}}
\put(0.0,100.0){\line(1,0){4.0}}\put(8.0,100.0){\line(1,0){4.0}}\put(16.0,100.%
0){\line(1,0){4.0}}\put(24.0,100.0){\line(1,0){4.0}}\put(32.0,100.0){\line(1,0%
){4.0}}\put(40.0,100.0){\line(1,0){4.0}}\put(48.0,100.0){\line(1,0){4.0}}\put(%
56.0,100.0){\line(1,0){4.0}}\put(64.0,100.0){\line(1,0){4.0}}\put(72.0,100.0){%
\line(1,0){4.0}}\put(80.0,100.0){\line(1,0){4.0}}\put(88.0,100.0){\line(1,0){4%
.0}}\put(96.0,100.0){\line(1,0){4.0}}\put(104.0,100.0){\line(1,0){4.0}}\put(11%
2.0,100.0){\line(1,0){4.0}}
\put(0.0,0.0){\line(0,1){4.0}}\put(0.0,8.0){\line(0,1){4.0}}\put(0.0,16.0){%
\line(0,1){4.0}}\put(0.0,24.0){\line(0,1){4.0}}\put(0.0,32.0){\line(0,1){4.0}}%
\put(0.0,40.0){\line(0,1){4.0}}\put(0.0,48.0){\line(0,1){4.0}}\put(0.0,56.0){%
\line(0,1){4.0}}\put(0.0,64.0){\line(0,1){4.0}}\put(0.0,72.0){\line(0,1){4.0}}%
\put(0.0,80.0){\line(0,1){4.0}}\put(0.0,88.0){\line(0,1){4.0}}\put(0.0,96.0){%
\line(0,1){4.0}}
\put(20.0,0.0){\line(0,1){4.0}}\put(20.0,8.0){\line(0,1){4.0}}\put(20.0,16.0){%
\line(0,1){4.0}}\put(20.0,24.0){\line(0,1){4.0}}\put(20.0,32.0){\line(0,1){4.0%
}}\put(20.0,40.0){\line(0,1){4.0}}\put(20.0,48.0){\line(0,1){4.0}}\put(20.0,56%
.0){\line(0,1){4.0}}\put(20.0,64.0){\line(0,1){4.0}}\put(20.0,72.0){\line(0,1)%
{4.0}}\put(20.0,80.0){\line(0,1){4.0}}\put(20.0,88.0){\line(0,1){4.0}}\put(20.%
0,96.0){\line(0,1){4.0}}
\put(40.0,0.0){\line(0,1){4.0}}\put(40.0,8.0){\line(0,1){4.0}}\put(40.0,16.0){%
\line(0,1){4.0}}\put(40.0,24.0){\line(0,1){4.0}}\put(40.0,32.0){\line(0,1){4.0%
}}\put(40.0,40.0){\line(0,1){4.0}}\put(40.0,48.0){\line(0,1){4.0}}\put(40.0,56%
.0){\line(0,1){4.0}}\put(40.0,64.0){\line(0,1){4.0}}\put(40.0,72.0){\line(0,1)%
{4.0}}\put(40.0,80.0){\line(0,1){4.0}}\put(40.0,88.0){\line(0,1){4.0}}\put(40.%
0,96.0){\line(0,1){4.0}}
\put(60.0,0.0){\line(0,1){4.0}}\put(60.0,8.0){\line(0,1){4.0}}\put(60.0,16.0){%
\line(0,1){4.0}}\put(60.0,24.0){\line(0,1){4.0}}\put(60.0,32.0){\line(0,1){4.0%
}}\put(60.0,40.0){\line(0,1){4.0}}\put(60.0,48.0){\line(0,1){4.0}}\put(60.0,56%
.0){\line(0,1){4.0}}\put(60.0,64.0){\line(0,1){4.0}}\put(60.0,72.0){\line(0,1)%
{4.0}}\put(60.0,80.0){\line(0,1){4.0}}\put(60.0,88.0){\line(0,1){4.0}}\put(60.%
0,96.0){\line(0,1){4.0}}
\put(80.0,0.0){\line(0,1){4.0}}\put(80.0,8.0){\line(0,1){4.0}}\put(80.0,16.0){%
\line(0,1){4.0}}\put(80.0,24.0){\line(0,1){4.0}}\put(80.0,32.0){\line(0,1){4.0%
}}\put(80.0,40.0){\line(0,1){4.0}}\put(80.0,48.0){\line(0,1){4.0}}\put(80.0,56%
.0){\line(0,1){4.0}}\put(80.0,64.0){\line(0,1){4.0}}\put(80.0,72.0){\line(0,1)%
{4.0}}\put(80.0,80.0){\line(0,1){4.0}}\put(80.0,88.0){\line(0,1){4.0}}\put(80.%
0,96.0){\line(0,1){4.0}}
\put(100.0,0.0){\line(0,1){4.0}}\put(100.0,8.0){\line(0,1){4.0}}\put(100.0,16.%
0){\line(0,1){4.0}}\put(100.0,24.0){\line(0,1){4.0}}\put(100.0,32.0){\line(0,1%
){4.0}}\put(100.0,40.0){\line(0,1){4.0}}\put(100.0,48.0){\line(0,1){4.0}}\put(%
100.0,56.0){\line(0,1){4.0}}\put(100.0,64.0){\line(0,1){4.0}}\put(100.0,72.0){%
\line(0,1){4.0}}\put(100.0,80.0){\line(0,1){4.0}}\put(100.0,88.0){\line(0,1){4%
.0}}\put(100.0,96.0){\line(0,1){4.0}}
\put(120.0,0.0){\line(0,1){4.0}}\put(120.0,8.0){\line(0,1){4.0}}\put(120.0,16.%
0){\line(0,1){4.0}}\put(120.0,24.0){\line(0,1){4.0}}\put(120.0,32.0){\line(0,1%
){4.0}}\put(120.0,40.0){\line(0,1){4.0}}\put(120.0,48.0){\line(0,1){4.0}}\put(%
120.0,56.0){\line(0,1){4.0}}\put(120.0,64.0){\line(0,1){4.0}}\put(120.0,72.0){%
\line(0,1){4.0}}\put(120.0,80.0){\line(0,1){4.0}}\put(120.0,88.0){\line(0,1){4%
.0}}\put(120.0,96.0){\line(0,1){4.0}}
\put(-28.0,0.0){$(0,0)$}
\put(125.0,100.0){$(6,5)$}
\put(0.0,0.0){\line(0,1){20.0}}
\put(0.0,20.0){\line(1,0){40.0}}
\put(40.0,20.0){\line(0,1){20.0}}
\put(40.0,40.0){\line(1,0){20.0}}
\put(60.0,40.0){\line(0,1){20.0}}
\put(60.0,60.0){\line(1,0){40.0}}
\put(100.0,60.0){\line(0,1){40.0}}
\put(100.0,100.0){\line(1,0){20.0}}
\put(0.0,100.0){\circle*{5.0}}\put(20.0,100.0){\circle*{5.0}}\put(40.0,100.0){%
\circle*{5.0}}\put(60.0,100.0){\circle*{5.0}}\put(80.0,100.0){\circle*{5.0}}
\put(0.0,80.0){\circle*{5.0}}\put(20.0,80.0){\circle*{5.0}}\put(40.0,80.0){%
\circle*{5.0}}\put(60.0,80.0){\circle*{5.0}}\put(80.0,80.0){\circle*{5.0}}
\put(0.0,60.0){\circle*{5.0}}\put(20.0,60.0){\circle*{5.0}}\put(40.0,60.0){%
\circle*{5.0}}
\put(0.0,40.0){\circle*{5.0}}\put(20.0,40.0){\circle*{5.0}}
\end{picture}
Figure 26.9.2: The partition 5+5+3+2 represented as a lattice path. Magnify

Equations (26.9.2)–(26.9.3) are examples of closed forms that can be computed explicitly for any positive integer k. See Andrews (1976, p. 81).

26.9.2 p0(n)=0,
n>0,
26.9.3 p1(n) =1,
p2(n) =1+n/2,
p3(n) =1+n2+6n12.

§26.9(ii) Generating Functions

In what follows

26.9.4 [mn]q=j=1n1-qm-n+j1-qj,
n0,

is the Gaussian polynomial (or q-binomial coefficient); compare §§17.2(i)17.2(ii). In the present chapter mn0 in all cases. It is also assumed everywhere that |q|<1.

§26.9(iii) Recurrence Relations

26.9.8 pk(n)=pk(n-k)+pk-1(n);

equivalently, partitions into at most k parts either have exactly k parts, in which case we can subtract one from each part, or they have strictly fewer than k parts.

26.9.9 pk(n)=1nt=1npk(n-t)j|tjkj,

where the inner sum is taken over all positive divisors of t that are less than or equal to k.

§26.9(iv) Limiting Form

As n with k fixed,

26.9.10 pk(n)nk-1k!(k-1)!.