# Uniformly at Random

## Enumerating permutations by number of inversions

We have previously given a proof of the identity

$\prod_{i \geq 1}(1-q^i) = \sum_{n=-\infty}^\infty (-1)^n q^{(3n^2+n)/2}$,

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 $n$ elements with $k$ inversions. Let $p = p_1p_2 \cdots p_n$ be a permutation of $1,2,\ldots,n$, written in the so-called “one line” notation. An inversion of $p$ is a pair $(p_i,p_j)$ such that $i and $p_i>p_j$. Let $i(p)$ denote the number of inversions of $p$. Then we claim that the generating function $I_n$ of $i(p)$ is

$I_n(q) = \sum_{p \in S_n} q^{i(p)} = (1+q)(1+q+q^2)\cdots(1+q+\cdots+q^{n-1}) = \prod_{i=1}^n\frac{1-q^i}{1-q}$.

We prove this by induction on $n$. For $n=2$, we have one permutation with no inversions and one with one inversion, whence we obtain the generating function $I_2(q) = 1+q$, as claimed.

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

$I_{n-1}(q)\cdot(1+q+\cdots+q^{n-1}) = (1+q)(1+q+q^2)\cdots(1+q+\cdots+q^{n-1})$,

as claimed. This completes the proof.

Let $b(n,k)$ denote the coefficient of $q^k$ in $I_n(q)$; i.e., $b(n,k)$ is the number of permutations of $n$ elements with $k$ inversions. We wish to deduce a formula for $b(n,k)$. Since $b(n,k)$ is the coefficient of $q^k$ in $\prod_{i=1}^n\frac{1-q^i}{1-q} = (1-q)^{-n}\prod_{i=1}^n (1-q^i)$, it must also equal the coefficient of $q^k$ in the infinite product $(1-q)^{-n}\prod_{i \geq 1}(1-q^i)$. By Euler’s Pentagonal Number Theorem, we have

$(1-q)^{-n}\prod_{i \geq 1}(1-q^i) = (1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}$.

Thus, $b(n,k)$ is the coefficient of $q^k$ in $(1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}$. By the binomial theorem, we have

$(1-q)^{-n} = \sum_{h \geq 0} {n+h-1 \choose h}q^h$

(recall that ${-n \choose h} = (-1)^h {n+h-1 \choose h}$). Thus, letting $d_j = (3j^2+j)/2$ denote the pentagonal numbers, we obtain a term $q^k$ in $(1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{d_j}$ by multiplying a term $q^{k-d_j}$ from $(1-q)^{-n}$ by a term $q^{d_j}$ from $\sum_{j=-\infty}^\infty (-1)^j q^{d_j}$. The coefficient of $q^{k-d_j}$ in $(1-q)^{-n}$ is ${n+k-d_j-1 \choose k-d_j}$, and the coefficient of $q^{d_j}$ in $\sum_{j=-\infty}^\infty (-1)^j q^{d_j}$ is $(-1)^j$. Thus, the coefficient $b(n,k)$ of $q^k$ is given by

$b(n,k) = \sum_j (-1)^j {n+k-d_j-1 \choose k-d_j}$,

where the sum is over all $j$ for which $d_j \leq k$. This is the desired formula for the number of permutations of $n$ elements with $k$ inversions.

Written by uncudh

February 17, 2009 at 2:48 am

Posted in math

Tagged with , ,

## Ramanujan’s partition congruences

Ramanujan proved several remarkable divisibility properties of the number $p(n)$ (recall that these denote the number of partitions of a positive integer $n$). One such property is that $p(5n+4)$ 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:

$\sum_{n=-\infty}^\infty (-1)^n (2n+1) q^{n(n+1)/2} = \prod_{k \geq 1}(1-q^k)^3$.

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

$\sum_{n \geq 0} p(n) q^n = \prod_{k \geq 1}(1-q^k)^{-1}$.

Multiplying both sides by $q\prod_{k \geq 1}(1-q^{5k})$ gives

$\prod_{k \geq 1}(1-q^{5k})\sum_{n \geq 0} p(n) q^{n+1} = q\prod_{k \geq 1}(1-q^{5k})\prod_{k \geq 1}(1-q^k)^{-1}$,

which we may rewrite as

$\prod_{k \geq 1}(1-q^{5k})\sum_{n \geq 0} p(n) q^{n+1} = q\prod_{k \geq 1}(1-q^{5k})\prod_{k \geq 1}(1-q^k)^{-5}\prod_{k \geq 1}(1-q^k)^4$.

However, by the binomial theorem we have

$\prod_{k \geq 1}(1-q^{5k}) \equiv \prod_{k \geq 1}(1-q^k)^5 \pmod 5$,

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

$\prod_{k \geq 1}(1-q^{5k})\prod_{k \geq 1}(1-q^k)^{-5} \equiv 1 \pmod 5$,

which in turn implies that

$\prod_{k \geq 1}(1-q^{5k})\sum_{n \geq 0} p(n) q^{n+1} \equiv q\prod_{k \geq 1}(1-q^k)^4 \pmod 5$.

To show that $p(5n+4)$ is a multiple of 5 it therefore suffices to show that the coefficients of $q^{5n+5}$ in the above expression are multiples of 5. Consider then the righthand side of the equivalence. We have

$q\prod_{k \geq 1}(1-q^k)^4$

$= q\prod_{k \geq 1}(1-q^k)\prod_{k \geq 1}(1-q^k)^3$

$= q\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}\sum_{k=-\infty}^\infty (-1)^k (2k+1) q^{k(k+1)/2}$,

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

$q\prod_{k \geq 1}(1-q^k)^4$

$= \sum_{j=-\infty}^\infty\sum_{k=-\infty}^\infty(-1)^{j+k}(2k+1)q^{1+(3j^2+j)/2+k(k+1)/2}$.

The exponents of $q$ in the above sum are therefore multiples of 5 when $1+(3j^2+j)/2+k(k+1)/2$ is a multiple of 5. Observe that

$2(j+1)^2 + (2k+1)^2 = 8(1+(3j^2+j)/2+k(k+1)/2) - 10j^2 - 5$,

so that $1+(3j^2+j)/2+k(k+1)/2$ is a multiple of 5 exactly when $2(j+1)^2 + (2k+1)^2$ is a multiple of 5. However, $2(j+1)^2$ can only be 0, 2, or 3 mod 5, and $(2k+1)^2$ can only be 0, 1, or 4 mod 5. Thus, $2(j+1)^2 + (2k+1)^2$ is a multiple of 5 exactly when both $2(j+1)^2$ and $(2k+1)^2$ are multiples of 5. However, if $(2k+1)^2$ is a multiple of 5, then so must $2k+1$ be. We therefore conclude that the coefficient of $q^{5n+5}$ in $q\prod_{k \geq 1}(1-q^k)^4$—and hence in $\prod_{k \geq 1}(1-q^{5k})\sum_{n \geq 0} p(n) q^{n+1}$—is a multiple of 5. This implies that $p(5n+4)$ is a multiple of 5, as claimed.

Written by uncudh

November 24, 2008 at 4:50 pm

Posted in math

Tagged with ,

## Integer partitions and Jacobi’s triple product

A partition of an positive integer $n$ is a representation of $n$ as a sum $n = n_1 + n_2 + \cdots + n_k$ where the $n_i$‘s are positive integers. If $p(n)$ denotes the number of such partitions of $n$, where any two partitions differing only by the order of the summands are not considered distinct, then we have the formal identity

$\sum_{n \geq 0} p(n) q^m = (1+q+q^2+\cdots)(1+q^2+q^4+\cdots)(1+q^3+q^6+\cdots)\cdots$

where we define $p(0)=1$; or equivalently,

$\sum_{n \geq 0} p(n) q^m = \prod_{k \geq 1} (1-q^k)^{-1}$.

Partitions are conveniently represented graphically by means of a Ferrers diagram. If $n = n_1 + n_2 + \cdots + n_k$ is a partition of $n$ where $n_1 \geq n_2 \geq \cdots n_k \geq 1$, then the corresponding Ferrers diagram consists of $k$ rows of dots: the first row consisting of $n_1$ dots, the second of $n_2$ 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:

$\prod_{k \geq 1}(1+zq^{2k-1})(1+z^{-1}q^{2k-1})(1+q^{2k}) = \sum_{n=-\infty}^\infty z^nq^{n^2}$.

Equivalently, we will show

$\prod_{k \geq 1}(1+zq^k)(1+z^{-1}q^{k-1})(1+q^k) = \sum_{n=-\infty}^\infty z^nq^{n(n+1)/2}$.

Note that substituting $q^2$ for $q$ and $zq^{-1}$ for $z$ in the above gives the triple product formula. We begin by defining

$F(z) = \prod_{k \geq 1}(1+zq^k)(1+z^{-1}q^{k-1}) = \sum_{n=-\infty}^\infty G_n(q)z^n$,

where for all $n$, $G_n(q)$ is a power series in $q$. To show that $G_n(q)$ is well-defined, consider the coefficient of $z^nq^m$ in $F(z)$. We obtain a term $z^nq^m$ by a product of the form

$(zq^{r_1} \cdots zq^{r_{n+i}}) (z^{-1}q^{s_1} \cdots z^{-1}q^{s_i})$

$= z^{n+i} (q^{r_1} \cdots q^{r_{n+i}}) z^{-i} (q^{s_1} \cdots q^{s_i})$

$= z^n (q^{r_1} \cdots q^{r_{n+i}}) (q^{s_1} \cdots q^{s_i})$

where $r_1 > r_2 > \cdots > r_{n+i} \geq 1$, $s_1 > s_2 > \cdots > s_i \geq 0$, and $(r_1 + \cdots + r_{n+i}) + (s_1 + \cdots + s_i) = m$. However, the number of choices for the $r_j$‘s and $s_j$‘s subject to these constraints is finite, so the coefficient of $z^nq^m$ in $F(z)$ is finite, and in particular, $G_n(q)$ is a well-defined formal power series in $q$.

Next we show that $F$ satisfies the functional equation $F(qz) = z^{-1}q^{-1}F(z)$. We have

$F(qz) = \prod_{k \geq 1}(1+zq^{k+1})(1+z^{-1}q^{k-2})$

$= (1+zq)^{-1}(1+z^{-1}q^{-1}) \prod_{k \geq 1}(1+zq^k)(1+z^{-1}q^{k-1})$

$= (1+zq)^{-1}(1+z^{-1}q^{-1}) F(z) = z^{-1}q^{-1} F(z)$.

Since $F(z) = \sum_{n=-\infty}^\infty G_n(q)z^n$ we therefore have

$\sum_{n=-\infty}^\infty G_n(q)q^nz^n = z^{-1}q^{-1} \sum_{n=-\infty}^\infty G_n(q)z^n = \sum_{n=-\infty}^\infty G_n(q)q^{-1}z^{n-1}$.

It follows then that $G_{n-1}(q)q^{n-1} = G_n(q)q^{-1}$; i.e, $G_{n-1}(q)q^n = G_n(q)$. We thus have

$G_n(q) = q^n q^{n-1} \cdots q G_0(q) = q^{n(n+1)/2} G_0(q)$

for $n \geq 0$ and, similarly, since $G_{-n}(q) = q^{n-1}G_{-(n-1)}(q)$, we have

$G_{-n}(q) = q^{n-1} q^{n-2} \cdots q G_0(q) = q^{n(n-1)/2} G_0(q) = q^{-n(-n+1)/2} G_0(q)$

for $n \geq 0$. We thus have $G_n(q) = q^{n(n+1)/2} G_0(q)$ for all integers $n$. It follows that

$F(z) = \sum_{n=-\infty}^\infty G_n(q)z^n = G_0(q) \sum_{n=-\infty}^\infty q^{n(n+1)/2}z^n$.

However, by our earlier discussion concerning the coefficients of $z^nq^m$ in $F(z)$, and considering the case $n=0$, we see that the coefficient of $q^m$ in the power series $G_0(q)$ must be equal to the number of choices of $r_j$‘s and $s_j$‘s satisfying $r_1 > r_2 > \cdots > r_i \geq 1$, $s_1 > s_2 > \cdots > s_i \geq 0$, and $(r_1 + \cdots + r_i) + (s_1 + \cdots + s_i) = m$. We claim that this is equal to the number of partitions $p(m)$ of $m$.

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

We have therefore established that $G_0(q) = \sum_{m \geq 0} p(m)q^m$. However recall that $\sum_{m \geq 0} p(m)q^m = \prod_{k \geq 1} (1-q^k)^{-1}$. It follows that

$F(z) = G_0(q) \sum_{n=-\infty}^\infty z^nq^{n(n+1)/2} = \prod_{k \geq 1} (1-q^k)^{-1} \sum_{n=-\infty}^\infty z^nq^{n(n+1)/2}$.

Multiplying both sides by $\prod_{k \geq 1} (1-q^k)$ gives

$\prod_{k \geq 1} (1-q^k) F(z) = \sum_{n=-\infty}^\infty z^nq^{n(n+1)/2}$

which is the claimed identity. Finally, substituting $q^3$ for $q$ and $-q^{-1}$ for $z$ in the above yields

$\prod_{k \geq 1}(1-q^{3k-1})(1-q^{3k-2})(1-q^{3k}) = \sum_{n=-\infty}^\infty (-q)^{-n}q^{3n(n+1)/2} = \sum_{n=-\infty}^\infty (-1)^n q^{(3n^2+n)/2}$.

This is clearly equivalent to

$\prod_{k \geq 1}(1-q^k) = \sum_{n=-\infty}^\infty (-1)^n q^{(3n^2+n)/2}$,

which is Euler’s Pentagonal Number Theorem.

Written by uncudh

November 22, 2008 at 5:50 pm

Posted in math

Tagged with ,