Pentagonal number theorem

From Wikipedia, the free encyclopedia

In mathematics, the pentagonal number theorem, originally due to Euler, relates the product and series representations of the Euler function. It states that

$\prod_{n=1}^\infty (1-x^n)=\sum_{k=-\infty}^\infty(-1)^kx^{k(3k-1)/2}.$

In other words,

$(1-x)(1-x^2)(1-x^3) \cdots = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \cdots.$

A striking feature of this expansion is the amount of cancellation in the product. The indices 1, 2, 5, 7, 12, ... appearing on the right hand side are called pentagonal numbers (or more accurately, generalized pentagonal numbers).

If we treat this series as a power series, the radius of convergence is 1. One may also ignore issues of convergence, in which case the theorem holds as a statement about formal power series.

1 A combinatorial proof
2 A proof by bijection
3 Example program
4 See also
5 Notes
6 External links

[edit] A combinatorial proof

The theorem can be given a combinatorial interpretation in terms of partitions. In particular, the left hand side is a generating function for the number of partitions of n into an even number of distinct parts minus the number of partitions of n into an odd number of distinct parts. (The article on unrestricted partition functions discusses this type of generating function.)

For example, the x⁵ coefficient is 1 because of there are two ways to split 5 into an even number of distinct parts (4+1 and 3+2), but only one way to do so for an odd number of distinct parts (5 itself).

This interpretation leads to an elegant proof of the identity via involution. Consider the Ferrers graph of any partition of n into distinct parts. For example, the diagram below shows n = 20 and the partition 20 = 7 + 6 + 4 + 3.

Let k be the number of elements in the smallest row of our graph. Let s be the number of elements in the rightmost 45 degree line of our graph (the dots which are red in the above diagram). In the diagram above, s = 2 and k = 3.

If k > s, we take the rightmost 45 degree line and move it to form a new row, as in the graph below.

If this is not the case (as in our newly formed graph where k = 2, s = 5) we reverse the process by moving the bottom row to form a new 45 degree line (in effect adding 1 element to each of the first k rows). In our case, this takes us back into the first graph.

A bit of thought shows that in fact applying this process twice brings us back to the original graph and the process always changes the parity of the number of rows. Thus this process (when it can be performed) enables us to pair off the Ferrers' graphs of partitions contributing 1 and -1 to the original sum. Everything cancels, UNLESS there are some cases where our operation cannot be performed. In fact, there are two of them.

1) k = s and the rightmost diagonal and bottom row meet. For example,

Attempting to perform the operation would lead us to:

which fails to change the parity of the number of rows, and is not reversible in the sense that performing the operation again does not take us back to the original graph. If there are k elements in the last row of the original graph, then

$n=k+(k+1)+(k+2)+\cdots+(2k-1)=\frac {k(3k-1)}{2}$

2) k = s+1 and the rightmost diagonal and bottom row meet. For example,

Our operation requires us to move the right diagonal to the bottom row, but that would lead to two rows of 3 elements, forbidden since we're counting partitions into distinct parts. This is the previous case but with one fewer row, so

$n=k+(k+1)+(k+2)+\cdots+(2k-2)=\frac{(k-1)(3k-2)}{2} =\frac{m(3m-1)}{2},$

where m=1-k (which is negative).

In summary, we have shown that partitions into an even number of distinct parts and an odd number of distinct parts exactly cancel each other out, except for pentagonal numbers, where there is exactly one case left over (which contributes a factor of (-1)^k). But this is precisely what the right side of the identity says should happen, so we are finished.

This gives a beautiful recurrence for calculating $p n$ , the number of partitions of n Partition function (number theory).

$p_n=p_{n-1}+p_{n-2}-p_{n-5}-p_{n-7}+\cdots$

or more formally,

$p_n=\sum_i {(-1)^{i-1}p_{n-q_i}}$

where the summation is over all (including negative) i and $q i$ is the $i t h$ pentagonal number calculated as above.

[edit] A proof by bijection

Another way of proving the identity is by observing its implications on certain sets of partitions. Start by noting that $\prod_{n\in\mathbb{N}} (1 - x^n)$ is the exact inverse (in terms of formal power series) of the well known generating function for the partiton function p(n), $\prod\limits_{k\in\mathbb{N}} (1 - x^k)^{-1} = \sum\limits_{n\in \mathbb{N}_0} p(n) x^n$ . This means that

$\left( \sum_{n=0}^\infty p(n) x^n \right) \cdot \left( \sum_{n=0}^\infty a_n x^n \right) = 1,$

where a_n is the coefficient of xⁿ in the expansion of our product. We thus have a₀ p(0) = a₀ = 1 and $\sum_{i=0}^n p(n-i) a_i = 0$ for all $n\geq 1$ (which, of course, is a recurrence relation that defines the a_i uniquely). It is now easy to find an equivalence to our identity in terms of sets of partitions^[1]. Indeed, if we are to find

$a_i := \begin{cases}1 & \mbox{ if } i = \frac{1}{2}(3k^2 \pm k) \mbox{ and } k \mbox{ is even}\\ -1 & \mbox{ if } i = \frac{1}{2}(3k^2 \pm k) \mbox{ and } k \mbox{ is odd }\\ 0 & \mbox{ otherwise }\end{cases}$

for $i\geq 1$ (which is what we want to prove), we need, substituting this formula into our above recurrence relation for a_i,

∑	( − 1)ⁱp(n − b_i) = 0,
i

(n > 0 as before) where $b_i := \frac{1}{2}(3i^2+i)$ and i ranges over all values such that $b_i \leq n$ (both positive and negative, as to encompass both kinds of generalized pentagonal numbers). This in turn means that

∑	p(n − b_i) =	∑	p(n − b_i),
i even		i odd

which transcribes in terms of sets of partitions as the fact that the sets

$\mathcal{X} := \bigcup_{i \mbox{ even}} \mathcal{P}(n-b_i)$ and $\mathcal{Y} := \bigcup_{i \mbox{ odd}} \mathcal{P}(n-b_i)$

are of equal cardinality (using the same restrictions as before on i and n). All that remains to be done now is finding a bijection from one to the other and it is easy to check that the function φ from X to Y which maps the partition $\mathcal{P}(n-b_i) \ni \lambda : n-b_i = \lambda_1 + \lambda_2 + \dotsb + \lambda_\ell$ to the partiton $\lambda' = \varphi(\lambda)$ where

$\varphi(\lambda) := \begin{cases} \lambda' : n - b_{i-1} = (\ell + 3i -1) + (\lambda_1 - 1) + \dotsb + (\lambda_\ell - 1) &\mbox{ if } \ell+3i \geq \lambda_1\\ \\ \lambda' : n - b_{i+1} = (\lambda_2 + 1) + \dotsb + (\lambda_\ell + 1) + \underbrace{1+\dotsb+1}_{\lambda_1 - \ell - 3i - 1} &\mbox{ if } \ell+3i < \lambda_1 \end{cases}$

is actually an involution (and thus in particular a bijection), which proves our claim and the identity.

[edit] Example program

Here is a simple Python program which computes partitions using the Pentagonal number theorem.

pentagonal = lambda n : n*(3*n-1)/2

def generalised_pentagonal(n): # 0, 1, -1, 2, -2
    if n < 0: return 0
    if n%2 == 0: return pentagonal(n/2+1)
    else: return pentagonal(-(n/2+1))

pt = [1]
for n in range (1, 1000+1):
    r = 0
    f = -1
    i = 0
    while generalised_pentagonal(i) <= n:
        k = generalised_pentagonal(i)
        if k > n:
            break
        if i%2==0: f = -f
        r += f*pt[n - k]
        i += 1
    pt.append(r)

print pt

[edit] See also

The pentagonal number theorem occurs as a special case of the Jacobi triple product.

Q-series generalizes Euler's function, which is closely related to the Dedekind eta function, and occurs in the study of modular forms. The modulus of the Euler function (see Q-series for picture) shows the fractal modular group symmetry and occurs in the study of the interior of the Mandelbrot set.

[edit] Notes

^ We write partitions as $\lambda : n = \lambda_1 + \lambda_2 + \dotsb + \lambda_\ell$ with $\lambda_1 \geq \lambda_2 \geq \dotsb \geq \lambda_\ell$ and $\mathcal{P}(n)$ denotes the set of all partitions of $n$ .