Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Pentagonal number theorem
Summary
In mathematics, the pentagonal number theorem, originally due to Euler, relates the product and series representations of the Euler function. It states that
In other words,
The exponents 1, 2, 5, 7, 12, ... on the right hand side are given by the formula gk = k(3k − 1)/2 for k = 1, −1, 2, −2, 3, ... and are called (generalized) pentagonal numbers . (The constant term 1 corresponds to .)
This holds as an identity of convergent power series for , and also as an identity of formal power series.
A striking feature of this formula is the amount of cancellation in the expansion of the product.
The identity implies a recurrence for calculating , the number of partitions of n:
or more formally,
where the summation is over all nonzero integers k (positive and negative) and is the kth generalized pentagonal number. Since for all , the apparently infinite series on the right has only finitely many non-zero terms, enabling an efficient calculation of p(n).
The theorem can be interpreted combinatorially 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. Each partition of n into an even number of distinct parts contributes +1 to the coefficient of xn; each partition into an odd number of distinct parts contributes −1. (The article on unrestricted partition functions discusses this type of generating function.)
For example, the coefficient of x5 is +1 because 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 (the one-part partition 5). However, the coefficient of x12 is −1 because there are seven ways to partition 12 into an even number of distinct parts, but there are eight ways to partition 12 into an odd number of distinct parts, and 7 − 8 = −1.
This interpretation leads to a proof of the identity by canceling pairs of matched terms (involution method).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.