Uniformly at Random

Posts Tagged ‘partitions

Enumerating permutations by number of inversions

with 2 comments

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<j 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

leave a comment »

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

leave a comment »

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.

Ferrers diagram

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.

Bijection

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 ,