Partition identities

This article needs more work.

Please help by expanding it!

The partition identities, which stipulate that the number of restricted partitions with condition A is equal to the number of restricted partitions with condition B, can be proved by bijective proofs (one-to-one pairings of two sets) with the merging/splitting technique, although Euler used generating functions.

Euler's partition identity

The original partition identity is Euler's partition identity

$p(n~|~{\rm {odd~parts}})=p(n~|~{\rm {distinct~parts}}),\,n\,\geq \,1.\,$

Euler pair theorem

Theorem (I. Schur)

$p(n~|~{\rm {parts}}\in N)=p(n~|~{\rm {distinct~parts}}\in M),\,n\,\geq \,1,\,$

where $\scriptstyle N\,$ is any set of positive integers s.t. the ratio of two elements of $\scriptstyle N\,$ is never a power of two, and $\scriptstyle M\,$ is the set of all elements of $\scriptstyle N\,$ and all their multiples by powers of two.

Euler's pentagonal number theorem

Theorem (Euler)

$p(n~|~{\rm {even~number~of~distinct~parts~}})=p(n~|~{\rm {odd~number~of~distinct~parts~}})~+~e(n)\,$

where

$e(n)={\begin{cases}(-1)^{j}&{\text{if }}n={\frac {j(3j-1)}{2}}\,\equiv \,q_{j}{\text{ for some }}j\in \mathbb {Z} ,\\0&{\text{otherwise}}.\end{cases}}\,$

The numbers $\scriptstyle n\,=\,{\frac {j(3j-1)}{2}}\,\equiv \,q_{j},\,j\,\in \,\mathbb {Z} \,$ are the generalized pentagonal numbers, with $\scriptstyle j\,$ going through the integer sequence (A001057).

{0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6, 7, -7, 8, -8, 9, -9, 10, -10, 11, -11, 12, -12, 13, -13, 14, -14, 15, -15, 16, -16, 17, -17, 18, -18, 19, -19, 20, -20, 21, -21, 22, -22, 23, -23, 24, -24, 25, -25, 26, -26, ...}

giving the sequence of generalized pentagonal numbers $\scriptstyle q_{j}\,$ (A001318)

{0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, 176, 187, 210, 222, 247, 260, 287, 301, 330, 345, 376, 392, 425, 442, 477, 495, 532, 551, 590, 610, 651, 672, 715, ...}

For nonnegative integer $\scriptstyle j\,$, the regular pentagonal numbers are obtained.

Euler's pentagonal number theorem implies

$\sum _{j=0}^{\infty }(-1)^{j}~{\big [}p(n-q_{j})+p(n-q_{-j}){\big ]}=\sum _{j=0}^{\infty }(-1)^{j}{\bigg [}p{\big (}n-{\tfrac {j(3j-1)}{2}}{\big )}+p{\big (}n-{\tfrac {(-j)(3(-j)-1)}{2}}{\big )}{\bigg ]}=p(n)+\sum _{j=1}^{\infty }(-1)^{j}{\bigg [}p{\big (}n-{\tfrac {j(3j-1)}{2}}{\big )}+p{\big (}n-{\tfrac {j(3j+1)}{2}}{\big )}{\bigg ]}=0\,$

which begets a finite (since $\scriptstyle p(n)\,=\,0\,$ for $\scriptstyle n\,<\,0\,$) recursive formula for the partition function

$p(n)=\sum _{j=1}^{\infty }(-1)^{j-1}{\big [}p(n-q_{j})+p(n-q_{-j}){\big ]}=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-\cdots \,$

where $\scriptstyle q_{j}\,$ is the generalized pentagonal number corresponding to $\scriptstyle j\,$.

The recurrence may be expressed with explicit finite bounds for the summation indexes $\scriptstyle j\,$

$p(n)=\sum _{j=1}^{{\big \lfloor }{\tfrac {1+{\sqrt {1+24n}}}{6}}{\big \rfloor }}(-1)^{j-1}~p{\big (}n-{\tfrac {j(3j-1)}{2}}{\big )}+\sum _{j=1}^{{\big \lfloor }{\tfrac {-1+{\sqrt {1+24n}}}{6}}{\big \rfloor }}(-1)^{j-1}~p{\big (}n-{\tfrac {j(3j+1)}{2}}{\big )}\,$

Partition identities

Conjugate pairs identities

$p(n~|~{\rm {greatest~part~is~}}k)=p(n~|~{\rm {number~of~parts~is~}}k),\,n\,\geq \,1.\,$

Ferrers graph transformation identities

$p(n~|~{\rm {greatest~part~is~}}k)=p(n-k~|~{\rm {all~parts}}\leq k),\,n\,\geq \,1.\,$

Congruences partition identities

Congruences mod 2 partition identity

$p(n~|~{\rm {even~parts}})=p(n~|~{\rm {even~number~of~each~part}}),\,n\,\geq \,1,\,$

or

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv 0{\pmod {2}}}}\})=p(n~|~{\rm {parts~occurrences}}\equiv 0{\pmod {2}}),\,n\,\geq \,1,\,$

where we have $\scriptstyle p({\frac {n}{2}})\,$ partitions for even $\scriptstyle n\,$ and 0 partitions for odd $\scriptstyle n\,$.

Congruences mod 3 partition identity

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv \pm 1{\pmod {3}}}}\})=p(n~|~{\rm {at~most~}}2{\rm {~of~each~part}}),\,n\,\geq \,1,\,$

or

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv \pm 1{\pmod {3}}}}\})=p(n~|~{\rm {parts~occurrences}}\leq 2),\,n\,\geq \,1,\,$

or

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv \pm 1{\pmod {3}}}}\})=p(n~|~{\rm {0{\mbox{-­­­­­­}}distinct~parts}}),\,n\,\geq \,1,\,$

where parts appearing at most twice are also called 0-distinct.

Congruences mod 4 partition identity

This is Euler's partition identity

$p(n~|~{\rm {odd~parts}})=p(n~|~{\rm {distinct~parts}}),\,n\,\geq \,1,\,$

or

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv \pm 1{\pmod {4}}}}\})=p(n~|~{\rm {parts~occurrences}}\leq 1),\,n\,\geq \,1,\,$

or

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv \pm 1{\pmod {4}}}}\})=p(n~|~{\rm {parts~differences}}\geq 1),\,n\,\geq \,1,\,$

or

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv \pm 1{\pmod {4}}}}\})=p(n~|~{\rm {1{\mbox{-­­­­­­}}distinct~parts}}),\,n\,\geq \,1,\,$

where parts differing by at least 1 are also called 1-distinct.

Congruences mod 5 partition identity

The congruences mod 5 partition identity was found independently by Leonard James Rogers in 1894 and Srinivasa Ramanujan in 1913.

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv \pm 1{\pmod {5}}}}\})=p(n~|~{\rm {parts~differences}}\geq 2),\,n\,\geq \,1,\,$

or

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\equiv \pm 1{\pmod {5}}}}\})=p(n~|~{\rm {2{\mbox{-­­­­­­}}distinct~parts}}),\,n\,\geq \,1,\,$

where parts differing by at least 2 are also called 2-distinct.

Congruences mod 6 partition NON-identity

You might have seen a pattern, but unfortunately things break down here!

Parity of number of odd parts partition identities

$p(n~|~{\rm {even~number~of~odd~parts}})=p(n~|~{\rm {distinct~parts,\,number~of~odd~parts~is~even}}),\,n\,\geq \,1.\,$

$p(n~|~{\rm {odd~number~of~odd~parts}})=p(n~|~{\rm {distinct~parts,\,number~of~odd~parts~is~odd}}),\,n\,\geq \,1.\,$

Noncongruences partition identities

Noncongruences mod 6 partition identity

The noncongruences mod 6 partition identity was found by Percy A. MacMahon in 1916.

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\not \equiv \pm 1{\pmod {6}}}}\})=p(n~|~{\rm {no~part~appears~exactly~once}}),\,n\,\geq \,1,\,$

or

$p(n~|~{\rm {parts}}\in \{{\rm {k~|~k\not \equiv \pm 1{\pmod {6}}}}\})=p(n~|~{\rm {parts~occurrences}}\neq 1),\,n\,\geq \,1.\,$

The uniqueness of binary representation partition identity

$p(n~|~{\rm {parts}}\in \{1\})=1=p(n~|~{\rm {distinct~powers~of~2}}),\,n\,\geq \,1.\,$

or

$p(n~|~{\rm {parts}}\in \{1\})=1=p(n~|~{\rm {count}}\in \{0,1\}{\rm {~of~parts}}\in \{{\rm {powers~of~2}}\}),\,n\,\geq \,1.\,$

The uniqueness of base k representation partition identity

$p(n~|~{\rm {parts}}\in \{1\})=1=p(n~|~{\rm {up~to~}}k-1{\rm {~of~any~powers~of~}}k),\,n\,\geq \,1.\,$

or

$p(n~|~{\rm {parts}}\in \{1\})=1=p(n~|~{\rm {count}}\in \{0,\ldots ,k-1\}{\rm {~of~parts}}\in \{{\rm {powers~of~k}}\}),\,k\,>\,1,\,n\,\geq \,1.\,$

Sequences

A000009 Expansion of

∏ ∞ m  = 1 (1 + x m)

; number of partitions of

n

into distinct parts; number of partitions of

n

into odd parts,

n   ≥   0

.

{1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260, 1426, 1610, 1816, 2048, ...}

A008284 Triangle of partition numbers:

T  (n, k) =

number of partitions of

n

in which the greatest part is

k, 1   ≤   k   ≤   n

. Also number of partitions of

n

into

k

positive parts (

1   ≤   k   ≤   n

).

{1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 3, 2, 1, 1, 1, 4, 5, 5, 3, 2, 1, 1, 1, 4, 7, 6, 5, 3, 2, 1, 1, 1, 5, 8, 9, 7, 5, 3, 2, 1, 1, 1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1, 1, 6, 12, 15, 13, 11, 7, ...}

See also

• Partitions
• Restricted partitions

• Composition identities