Pentagonal number theorem

Pentagonal number theorem

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.

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"5 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^{th} pentagonal number calculated as above.

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_{ninmathbb{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"), prodlimits_{kinmathbb{N (1 - x^k)^{-1} = sumlimits_{nin mathbb{N}_0} p(n) x^n. This means that

: left( sum_{n=0}^infty p(n) x^n ight) cdot left( sum_{n=0}^infty a_n x^n ight) = 1,

where "an" is the coefficient of "xn" in the expansion of our product. We thus have "a0" "p"(0) = "a0" = 1 and sum_{i=0}^n p(n-i) a_i = 0 for all ngeq 1 (which, of course, is a recurrence relation that defines the "ai" uniquely). It is now easy to find an equivalence to our identity in terms of sets of partitions [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.] . Indeed, if we are to find

:a_i := egin{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 igeq 1 (which is what we want to prove), we need, substituting this formula into our above recurrence relation for "ai", sum_i (-1)^i p(n - b_i) = 0, ("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

:sum_{i mbox{ even p(n - b_i) = sum_{i mbox{ odd p(n - b_i),

which transcribes in terms of sets of partitions as the fact that the sets :mathcal{X} := igcup_{i mbox{ even mathcal{P}(n-b_i) and mathcal{Y} := igcup_{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) i lambda : n-b_i = lambda_1 + lambda_2 + dotsb + lambda_ell to the partiton lambda' = varphi(lambda) where

: varphi(lambda) := egin{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_1end{cases}

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

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

ee 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.

Notes

External links

* [http://front.math.ucdavis.edu/math.HO/0510054 Euler and the pentagonal number theorem]
* [http://www.mathpages.com/home/kmath623/kmath623.htm On Euler's Pentagonal Theorem] at MathPages


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Pentagonal number — A pentagonal number is a figurate number that extends the concept of triangular and square numbers to the pentagon, but, unlike the first two, the patterns involved in the construction of pentagonal numbers are not rotationally symmetrical. The n …   Wikipedia

  • Fermat polygonal number theorem — In mathematics, the Fermat polygonal number theorem states: every positive integer is a sum of at most n n polygonal numbers. That is, every number can be written as the sum of at most three triangular numbers, or four square numbers, or five… …   Wikipedia

  • Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… …   Wikipedia

  • Partition (number theory) — Young diagrams associated to the partitions of the positive integers 1 through 8. They are so arranged that images under the reflection about the main diagonal of the square are conjugate partitions. In number theory and combinatorics, a… …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • Teorema del número pentagonal — En matemáticas, el teorema del número pentagonal, originalmente formulado por Leonhard Euler, da una equivalencia entre la representación en forma producto y de serie de la función de Euler. Se formula como: Leonhard Euler (1775) …   Wikipedia Español

  • Número pentagonal — Representación visual de los primeros números pentagonales. Un número pentagonal es un número figurado que extiende el concepto de número triangular y cuadrado al pentágono, pero, a diferencia de los dos primeros, los patrones utilizados en la… …   Wikipedia Español

  • number game — Introduction       any of various puzzles and games that involve aspects of mathematics.       Mathematical recreations comprise puzzles and games that vary from naive amusements to sophisticated problems, some of which have never been solved.… …   Universalium

  • number symbolism — Introduction       cultural associations, including religious, philosophic, and aesthetic, with various numbers.       Humanity has had a love hate relationship with numbers from the earliest times. Bones dating from perhaps 30,000 years ago show …   Universalium

  • 1 (number) — One redirects here. For other uses, see 1 (disambiguation). 1 −1 0 1 2 3 4 5 6 7 8 9 → List of numbers Integers …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”