It states that the number of partitions of an integer ${\displaystyle n}$  into parts not divisible by ${\displaystyle d}$  is equal to the number of partitions in which no part is repeated d or more times, which can be written formally as partitions of the form ${\displaystyle n=\lambda _{1}+\cdots +\lambda _{k}}$  where ${\displaystyle \lambda _{i}\geq \lambda _{i+1}}$  and ${\displaystyle \lambda _{i}\geq \lambda _{i+d-1}+1}$ .

When ${\displaystyle d=2}$  this becomes the special case known as Euler's theorem, that the number of partitions of ${\displaystyle n}$  into distinct parts is equal to the number of partitions of ${\displaystyle n}$  into odd parts.

In the following examples, we use the multiplicity notation of partitions. For example, ${\displaystyle 1^{4}2^{1}3^{2}}$  is a notation for the partition 1 + 1 + 1 + 1 + 2 + 3 + 3.

Example for d=2 (Euler's theorem case) edit

Among the 15 partitions of the number 7, there are 5, shown in bold below, that contain only odd parts (i.e. only odd numbers):

${\displaystyle \mathbf {7} ,6^{1}1^{1},5^{1}2^{1},\mathbf {5^{1}1^{2}} ,4^{1}3^{1},4^{1}2^{1}1^{1},4^{1}1^{3},\mathbf {3^{2}1^{1}} ,3^{1}2^{2},3^{1}2^{1}1^{2},\mathbf {3^{1}1^{4}} ,2^{3}1^{1},2^{2}1^{3},2^{1}1^{5},\mathbf {1^{7}} }$ 

If we count now the partitions of 7 with distinct parts (i.e. where no number is repeated), we also obtain 5:

${\displaystyle \mathbf {7} ,\mathbf {6^{1}1^{1}} ,\mathbf {5^{1}2^{1}} ,5^{1}1^{2},\mathbf {4^{1}3^{1}} ,\mathbf {4^{1}2^{1}1^{1}} ,4^{1}1^{3},3^{2}1^{1},3^{1}2^{2},3^{1}2^{1}1^{2},3^{1}1^{4},2^{3}1^{1},2^{2}1^{3},2^{1}1^{5},1^{7}}$ 

The partitions in bold in the first and second case are not the same, and it is not obvious why their number is the same.

Example for d=3 edit

Among the 11 partitions of the number 6, there are 7, shown in bold below, that contain only parts not divisible by 3:

${\displaystyle 6,\mathbf {5^{1}1^{1}} ,\mathbf {4^{1}2^{1}} ,\mathbf {4^{1}1^{2}} ,3^{2},3^{1}2^{1}1^{1},3^{1}1^{3},\mathbf {2^{3}} ,\mathbf {2^{2}1^{2}} ,\mathbf {2^{1}1^{4}} ,\mathbf {1^{6}} }$ 

And if we count the partitions of 6 with no part that repeats more than 2 times, we also obtain 7: ${\displaystyle \mathbf {6} ,\mathbf {5^{1}1^{1}} ,\mathbf {4^{1}2^{1}} ,\mathbf {4^{1}1^{2}} ,\mathbf {3^{2}} ,\mathbf {3^{1}2^{1}1^{1}} ,3^{1}1^{3},2^{3},\mathbf {2^{2}1^{2}} ,2^{1}1^{4},1^{6}}$ 

A proof of the theorem can be obtained with generating functions. If we note ${\displaystyle p_{d}(n)}$  the number of partitions with no parts divisible by d and ${\displaystyle q_{d}(n)}$  the number of partitions with no parts repeated more than d-1 times, then the theorem means that for all n ${\displaystyle p_{d}(n)=q_{d}(n)}$ . The uniqueness of ordinary generating functions implies that instead of proving that ${\displaystyle p_{d}(n)=q_{d}(n)}$  for all n, it suffices to prove that the generating functions of ${\displaystyle p_{d}(n)}$  and ${\displaystyle q_{d}(n)}$  are equal, i.e. that ${\displaystyle \sum _{n=0}^{\infty }p_{d}(n)x^{n}=\sum _{n=0}^{\infty }q_{d}(n)x^{n}}$ .

Each generating function can be rewritten as infinite products (with a method similar to the infinite product of the partition function) :

${\displaystyle \sum _{n=0}^{\infty }p_{d}(n)x^{n}=\prod _{n=1,d\nmid n}^{\infty }{\frac {1}{1-x^{n}}}}$  (i.e. the product of terms where n is not divisible by d).

${\displaystyle \sum _{n=0}^{\infty }q_{d}(n)x^{n}=\prod _{n=1}^{\infty }{\frac {1-x^{dn}}{1-x^{n}}}}$ 

If we expand the infinite product for ${\displaystyle q_{d}(n)}$ :

${\displaystyle \prod _{n=1}^{\infty }{\frac {1-x^{dn}}{1-x^{n}}}={\frac {1-x^{d}}{1-x}}{\frac {1-x^{2d}}{1-x^{2}}}\dots {\frac {1-x^{kd}}{1-x^{k}}}\dots }$ 

we see that each term in the numerator cancels with the corresponding multiple of d in the denominator. What remains after canceling all the numerator terms is exactly the infinite product for ${\displaystyle p_{d}(n)}$ .

Hence the generating functions for ${\displaystyle p_{d}(n)}$  and ${\displaystyle q_{d}(n)}$  are equal.

If instead of counting the number of partitions with distinct parts we count the number of partitions with parts differing by at least 2, a further generalization is possible. It was first discovered by Leonard James Rogers in 1894, and then independently by Ramanujan in 1913 and Schur in 1917, in what are now known as the Rogers-Ramanujan identities. It states that:

1) The number of partitions whose parts differ by at least 2 is equal to the number of partitions involving only numbers congruent to 1 or 4 (mod 5).

2) The number of partitions whose parts differ by at least 2 and with the smallest part at least 2 is equal to the number of partitions involving only numbers congruent to 2 or 3 (mod 5).

Example 1 edit

For example, there are only 3 partitions of 7, shown in bold below, into parts differing by at least 2 (note: if a number is repeated in a partition, it means a difference of 0 between two parts, hence the partition is not counted):

${\displaystyle \mathbf {7} ,\mathbf {6^{1}1^{1}} ,\mathbf {5^{1}2^{1}} ,5^{1}1^{2},4^{1}3^{1},4^{1}2^{1}1^{1},4^{1}1^{3},3^{2}1^{1},3^{1}2^{2},3^{1}2^{1}1^{2},3^{1}1^{4},2^{3}1^{1},2^{2}1^{3},2^{1}1^{5},1^{7}}$ 

And there are also only 3 partitions of 7 involving only the parts 1, 4, 6:

${\displaystyle 7,\mathbf {6^{1}1^{1}} ,5^{1}2^{1},5^{1}1^{2},4^{1}3^{1},4^{1}2^{1}1^{1},\mathbf {4^{1}1^{3}} ,3^{2}1^{1},3^{1}2^{2},3^{1}2^{1}1^{2},3^{1}1^{4},2^{3}1^{1},2^{2}1^{3},2^{1}1^{5},\mathbf {1^{7}} }$ 

Example 2 edit

For an example of the second statement of the Rogers-Ramanujan identities, we consider partitions of 7 with the further restriction of the smallest part at least 2, and there are only 2, shown in bold below:

${\displaystyle \mathbf {7} ,6^{1}1^{1},\mathbf {5^{1}2^{1}} ,5^{1}1^{2},4^{1}3^{1},4^{1}2^{1}1^{1},4^{1}1^{3},3^{2}1^{1},3^{1}2^{2},3^{1}2^{1}1^{2},3^{1}1^{4},2^{3}1^{1},2^{2}1^{3},2^{1}1^{5},1^{7}}$ 

And there are also only 2 partitions of 7 involving only the parts 2, 3, 7:

${\displaystyle \mathbf {7} ,6^{1}1^{1},5^{1}2^{1},5^{1}1^{2},4^{1}3^{1},4^{1}2^{1}1^{1},4^{1}1^{3},3^{2}1^{1},\mathbf {3^{1}2^{2}} ,3^{1}2^{1}1^{2},3^{1}1^{4},2^{3}1^{1},2^{2}1^{3},2^{1}1^{5},1^{7}}$ 

• D. H. Lehmer (1946). "Two nonexistence theorems on partitions". Bull. Amer. Math. Soc. 52 (6): 538–544. doi:10.1090/S0002-9904-1946-08605-X.