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.
Related lectures (1)
Pentagonal Number Theorem and Jacobi Identity
Covers the pentagonal number theorem, Jacobi identity, and modularity of eta and theta functions.
Related publications (2)
Computation of Al-Salam Carlitz and Askey-Wilson moments using Motzkin paths
In this paper we study the moments of polynomials from the Askey scheme, and we focus on Askey-Wilson polynomials. More precisely, we give a combinatorial proof for the case where d = 0. Their values have already been computed by Kim and Stanton in 2015, h ...
ELECTRONIC JOURNAL OF COMBINATORICS2021From Causal Consistency to Sequential Consistency in Shared Memory Systems
Sequential consistency and causal consistency constitute two of the main consistency criteria used to define the semantics of accesses in the shared memory model. An execution is sequentially consistent if all processes can agree on a same legal sequential ...
Springer-Verlag1995Related concepts (8)
Euler function
In mathematics, the Euler function is given by Named after Leonhard Euler, it is a model example of a q-series and provides the prototypical example of a relation between combinatorics and complex analysis. The coefficient in the formal power series expansion for gives the number of partitions of k. That is, where is the partition function. The Euler identity, also known as the Pentagonal number theorem, is is a pentagonal number.
Partition function (number theory)
In number theory, the partition function p(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4. No closed-form expression for the partition function is known, but it has both asymptotic expansions that accurately approximate it and recurrence relations by which it can be calculated exactly. It grows as an exponential function of the square root of its argument.
Q-Pochhammer symbol
In mathematical area of combinatorics, the q-Pochhammer symbol, also called the q-shifted factorial, is the product with It is a q-analog of the Pochhammer symbol , in the sense that The q-Pochhammer symbol is a major building block in the construction of q-analogs; for instance, in the theory of basic hypergeometric series, it plays the role that the ordinary Pochhammer symbol plays in the theory of generalized hypergeometric series.