## Posts Tagged ‘**partitions**’

## Enumerating permutations by number of inversions

We have previously given a proof of the identity

,

which is Euler’s Pentagonal Number Theorem. We now describe how to apply this formula to derive a formula for the number of permutations of elements with inversions. Let be a permutation of , written in the so-called “one line” notation. An inversion of is a pair such that and . Let denote the number of inversions of . Then we claim that the generating function of is

.

We prove this by induction on . For , we have one permutation with no inversions and one with one inversion, whence we obtain the generating function , as claimed.

Suppose the claim holds for and let be a permutation of . We create a new permutation by inserting into . If we insert after all elements of we have created no new inversions; if we insert after all but one element of we have created one new inversion; and in general, if we insert after all but elements of we create new inversions. Thus the number of permutations so created is enumerated by the generating function

,

as claimed. This completes the proof.

Let denote the coefficient of in ; i.e., is the number of permutations of elements with inversions. We wish to deduce a formula for . Since is the coefficient of in , it must also equal the coefficient of in the infinite product . By Euler’s Pentagonal Number Theorem, we have

.

Thus, is the coefficient of in . By the binomial theorem, we have

(recall that ). Thus, letting denote the pentagonal numbers, we obtain a term in by multiplying a term from by a term from . The coefficient of in is , and the coefficient of in is . Thus, the coefficient of is given by

,

where the sum is over all for which . This is the desired formula for the number of permutations of elements with inversions.

## Ramanujan’s partition congruences

Ramanujan proved several remarkable divisibility properties of the number (recall that these denote the number of partitions of a positive integer ). One such property is that is always a multiple of 5. The simplest proofs of this result of which I am aware make use of the following identity of Jacobi:

.

I do not feel sufficiently ambitious to derive Jacobi’s identity here, so we shall assume it without proof and proceed accordingly, this time following Berndt, *Number Theory in the Spirit of Ramanujan*. Let us begin with the identity

.

Multiplying both sides by gives

,

which we may rewrite as

.

However, by the binomial theorem we have

,

where the mod 5 notation means the coefficients of on each side of the equivalence are congruent modulo 5. We therefore conclude that

,

which in turn implies that

.

To show that is a multiple of 5 it therefore suffices to show that the coefficients of in the above expression are multiples of 5. Consider then the righthand side of the equivalence. We have

,

where we have used Euler’s Pentagonal Number Theorem to obtain the first sum and Jacobi’s Identity to obtain the second sum. Continuing, we have

.

The exponents of in the above sum are therefore multiples of 5 when is a multiple of 5. Observe that

,

so that is a multiple of 5 exactly when is a multiple of 5. However, can only be 0, 2, or 3 mod 5, and can only be 0, 1, or 4 mod 5. Thus, is a multiple of 5 exactly when both and are multiples of 5. However, if is a multiple of 5, then so must be. We therefore conclude that the coefficient of in —and hence in —is a multiple of 5. This implies that is a multiple of 5, as claimed.

## Integer partitions and Jacobi’s triple product

A partition of an positive integer is a representation of as a sum where the ‘s are positive integers. If denotes the number of such partitions of , where any two partitions differing only by the order of the summands are not considered distinct, then we have the formal identity

where we define ; or equivalently,

.

Partitions are conveniently represented graphically by means of a Ferrers diagram. If is a partition of where , then the corresponding Ferrers diagram consists of rows of dots: the first row consisting of dots, the second of dots, and so on. For example, the following Ferrers diagram represents the partition of 15 as 5 + 3 + 3 + 2 + 1 + 1.

Any introduction to the theory of partitions will include Euler’s Pentagonal Number Theorem and Jacobi’s Triple Product Theorem. We give a here a proof of both, following Aigner, *A Course in Enumeration*. We begin with the Triple Product Theorem:

.

Equivalently, we will show

.

Note that substituting for and for in the above gives the triple product formula. We begin by defining

,

where for all , is a power series in . To show that is well-defined, consider the coefficient of in . We obtain a term by a product of the form

where , , and . However, the number of choices for the ‘s and ‘s subject to these constraints is finite, so the coefficient of in is finite, and in particular, is a well-defined formal power series in .

Next we show that satisfies the functional equation . We have

.

Since we therefore have

.

It follows then that ; i.e, . We thus have

for and, similarly, since , we have

for . We thus have for all integers . It follows that

.

However, by our earlier discussion concerning the coefficients of in , and considering the case , we see that the coefficient of in the power series must be equal to the number of choices of ‘s and ‘s satisfying , , and . We claim that this is equal to the number of partitions of .

To see this, consider the Ferrers diagram of a particular partition of . Draw a line just below the main diagonal of the Ferrers diagram. The rows above the line drawn give the ‘s and the columns below the line drawn give the ‘s. It is not hard to see that the ‘s and ‘s so defined satisfy the required constraints, and furthermore, that this procedure gives a bijection between the set of Ferrers diagrams with dots and the set of choices of ‘s and ‘s subject to the above constraints.

We have therefore established that . However recall that . It follows that

.

Multiplying both sides by gives

which is the claimed identity. Finally, substituting for and for in the above yields

.

This is clearly equivalent to

,

which is Euler’s Pentagonal Number Theorem.