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

§26.10 Integer Partitions: Other Restrictions

Contents

§26.10(i) Definitions

p(𝒟,n) denotes the number of partitions of n into distinct parts. pm(𝒟,n) denotes the number of partitions of n into at most m distinct parts. p(𝒟k,n) denotes the number of partitions of n into parts with difference at least k. p(𝒟3,n) denotes the number of partitions of n into parts with difference at least 3, except that multiples of 3 must differ by at least 6. p(𝒪,n) denotes the number of partitions of n into odd parts. p(S,n) denotes the number of partitions of n into parts taken from the set S. The set {n1|n±j(modk)} is denoted by Aj,k. The set {2,3,4,} is denoted by T. If more than one restriction applies, then the restrictions are separated by commas, for example, p(𝒟2,T,n). See Table 26.10.1.

26.10.1 p(𝒟,0)=p(𝒟k,0)=p(S,0)=1.
Table 26.10.1: Partitions restricted by difference conditions, or equivalently with parts from Aj,k.
p(𝒟,n) p(𝒟2,n) p(𝒟2,T,n) p(𝒟3,n)
n and and and and
p(𝒪,n) p(A1,5,n) p(A2,5,n) p(A1,6,n)
0 1 1 1 1
1 1 1 0 1
2 1 1 1 1
3 2 1 1 1
4 2 2 1 1
5 3 2 1 2
6 4 3 2 2
7 5 3 2 3
8 6 4 3 3
9 8 5 3 3
10 10 6 4 4
11 12 7 4 5
12 15 9 6 6
13 18 10 6 7
14 22 12 8 8
15 27 14 9 9
16 32 17 11 10
17 38 19 12 12
18 46 23 15 14
19 54 26 16 16
20 64 31 20 18

§26.10(ii) Generating Functions

Throughout this subsection it is assumed that |q|<1.

26.10.2 n=0p(𝒟,n)qn=j=1(1+qj)=j=111-q2j-1=1+m=1qm(m+1)/2(1-q)(1-q2)(1-qm)=1+m=1qm(1+q)(1+q2)(1+qm-1),

where the last right-hand side is the sum over m0 of the generating functions for partitions into distinct parts with largest part equal to m.

26.10.3 (1-x)m,n=0pm(k,𝒟,n)xmqn=m=0k[km]qqm(m+1)/2xm=j=1k(1+xqj),
|x|<1,
26.10.4 n=0p(𝒟k,n)qn=1+m=1q(km2+(2-k)m)/2(1-q)(1-q2)(1-qm),

§26.10(iii) Recurrence Relations

26.10.6 p(𝒟,n)=1nt=1np(𝒟,n-t)j|tj oddj,

where the inner sum is the sum of all positive odd divisors of t.

26.10.7 (-1)kp(𝒟,n-12(3k2±k))={(-1)r,n=3r2±r,0,otherwise,

where the sum is over nonnegative integer values of k for which n-12(3k2±k)0.

26.10.8 (-1)kp(𝒟,n-(3k2±k))={1,n=12(r2±r),0,otherwise,

where the sum is over nonnegative integer values of k for which n-(3k2±k)0.

In exact analogy with (26.9.8), we have

26.10.9 pm(𝒟,n) =pm(𝒟,n-m)+pm-1(𝒟,n),
26.10.10 p(𝒟k,n) =pm(n-12km2-m+12km),

where the sum is over nonnegative integer values of m for which n-12km2-m+12km0.

26.10.11 p(S,n)=1nt=1np(S,n-t)j|tjSj,

where the inner sum is the sum of all positive divisors of t that are in S.

§26.10(iv) Identities

Equations (26.10.13) and (26.10.14) are the Rogers–Ramanujan identities. See also §17.2(vi).

26.10.12 p(𝒟,n)=p(𝒪,n),
26.10.13 p(𝒟2,n)=p(A1,5,n),
26.10.15 p(𝒟3,n)=p(A1,6,n).

Note that p(𝒟3,n)p(𝒟3,n), with strict inequality for n9. It is known that for k>3, p(𝒟k,n)p(A1,k+3,n), with strict inequality for n sufficiently large, provided that k=2m-1,m=3,4,5, or k32; see Yee (2004).

§26.10(v) Limiting Form

26.10.16 p(𝒟,n)πn/3(768n3)1/4,
n.

§26.10(vi) Bessel-Function Expansion

26.10.17 p(𝒟,n)=πk=1A2k-1(n)(2k-1)24n+1I1(π2k-124n+172),

where I1(x) is the modified Bessel function (§10.25(ii)), and

26.10.18 Ak(n)=1<hk(h,k)=1πf(h,k)-(2πnh/k),

with

26.10.19 f(h,k)=j=1k[[2j-12k]][[h(2j-1)k]],

and

26.10.20 [[x]]={x-x-12,x,0,x.

The quantity Ak(n) is real-valued.