FACTOID # 145: Three of the top ten countries for GDP per capita are island nations: Bermuda, Cayman Islands, and Iceland.
 
 Home   Encyclopedia   Statistics   Countries A-Z   Flags   Maps   Education   Forum   FAQ   About 
 
 
 
WHAT'S NEW
RECENT ARTICLES
More Recent Articles »
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > 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 For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... Leonhard Paul Euler (pronounced Oiler; IPA ) (April 15, 1707 – September 18 [O.S. September 7] 1783) was a pioneering Swiss mathematician and physicist, who spent most of his life in Russia and Germany. ... Modulus of phi on the complex plane, colored so that black=0, red=4 For other meanings, see Euler function (disambiguation). ...

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). A pentagonal number is a figurate number that represents a pentagon. ...


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. In mathematics, a power series (in one variable) is an infinite series of the form where the coefficients an, the center c, and the argument x are usually real or complex numbers. ... In mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of power series in settings that do not have natural notions of convergence. They are also useful to compactly describe sequences and to find closed formulas for recursively defined sequences; this is...

Contents

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.) Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. ... In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ... It has been suggested that this article or section be merged with Integer partition. ...


For example, the x5 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. In mathematics, an involution is a function that is its own inverse, so that f(f(x)) = x for all x in the domain of f. ... In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. ...

* * * * * * o
* * * * * o
* * * *
* * *

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. Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ...


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

* * * * * *
* * * * *
* * * *
* * *
o o

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. Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ... Image File history File links RedDot. ...


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: Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ... Image File history File links RedDot. ... Image File history File links RedDot. ...

* * * * * *
* * * * *
*

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 Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ... Image File history File links RedDot. ...

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 Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links GrayDot. ... Image File history File links RedDot. ...

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. A visual representation of the first six pentagonal numbers 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. ...


This gives a beautiful recurrence for calculating pn, the number of partitions of n Partition function (number theory). It has been suggested that this article or section be merged with Integer partition. ...

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 qi is the ith 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 right) cdot left( sum_{n=0}^infty a_n x^n right) = 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[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 igeq 1 (which is what we want to prove), we need, substituting this formula into our above recurrence relation for ai,

∑ ( − 1)ip(n − bi) = 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 − bi) = ∑ p(n − bi),
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.


Example program

Here is a simple Python program which computes partitions using the Pentagonal number theorem. Python is a high-level programming language first released by Guido van Rossum in 1991. ... 

 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

See also

The pentagonal number theorem occurs as a special case of the Jacobi triple product. In mathematics, the Jacobi triple product is a relation that re-expresses the Jacobi theta function, normally written as a series, as a 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. In mathematics, a q-series, also sometimes called a q-shifted factorial, is defined as It is usually considered first as a formal power series; it is also an analytic function of q, in the unit disc. ... The Dedekind eta function is a function defined on the upper half plane of complex numbers whose imaginary part is positive. ... A modular form is an analytic function on the upper half plane satisfying a certain kind of functional equation and growth condition. ... In mathematics, a q-series, also sometimes called a q-shifted factorial, is defined as It is usually considered first as a formal power series; it is also an analytic function of q, in the unit disc. ... The boundary of the Mandelbrot set is a famous example of a fractal. ... In mathematics, the modular group &#915; (Gamma) is a group that is a fundamental object of study in number theory, geometry, algebra, and many other areas of advanced mathematics. ... Initial image of a Mandelbrot set zoom sequence with continuously coloured environment The Mandelbrot set is a set of points in the complex plane that forms a fractal. ...


Notes

  1. ^ We write partitions as lambda : n = lambda_1 + lambda_2 + dotsb + lambda_ell with and denotes the set of all partitions of n.

External links

  • Euler and the pentagonal number theorem

  Results from FactBites:
 
NationMaster - Encyclopedia: Pentagonal number (357 words)
Pentagonal numbers should not be confused with centered pentagonal numbers.
Therefore the number of dots in the parallelogram is n(n+1), and the number of dots in the triangle is
Likewise in the case of square numbers, one can visualize that pentagonal numbers are constituted with triangular numbers: in particular, this sketch presents a pentagonal number of rank 5 as the sum of a triangular number of rank 5 and two triangular numbers of rank 4.
  More results at FactBites »


 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:
 


Lesson Plans | Student Area | Student FAQ | Reviews | Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 0825, t