This site is supported by donations to The OEIS Foundation.

Partition identities

From OeisWiki
(Redirected from Euler's partition identity)
Jump to: navigation, search


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

Euler pair theorem

Theorem (I. Schur)

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

Euler's pentagonal number theorem

Theorem (Euler)

where

The numbers are the generalized pentagonal numbers, with 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 (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 , the regular pentagonal numbers are obtained.

Euler's pentagonal number theorem implies

which begets a finite (since for ) recursive formula for the partition function

where is the generalized pentagonal number corresponding to .

The recurrence may be expressed with explicit finite bounds for the summation indexes

Partition identities

Conjugate pairs identities

Ferrers graph transformation identities

Congruences partition identities

Congruences mod 2 partition identity

or

where we have partitions for even and 0 partitions for odd .

Congruences mod 3 partition identity

or

or

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

Congruences mod 4 partition identity

This is Euler's partition identity

or

or

or

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.

or

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

Noncongruences partition identities

Noncongruences mod 6 partition identity

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

or

The uniqueness of binary representation partition identity

or

The uniqueness of base k representation partition identity

or

Sequences

A000009 Expansion of

m  = 1
(1 + xm)
; 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