TAOCP 7.2.1.4 Exercise 15

Section 7.2.1.4: Generating All Partitions

Exercise 15. [M20] [M20] (J. J. Sylvester.) Find a generating function for the number of partitions that are self-conjugate (namely, partitions such that α = αT ).

Verified: no
Solve time: 24m20s

Solution

Let $\alpha$ be a self-conjugate partition of $n$. Its Ferrers diagram is symmetric with respect to the main diagonal. For each cell $(i,i)$ on the diagonal, consider the hook consisting of that cell together with all cells to its right in row $i$ and all cells below it in column $i$. Because the diagram is symmetric, each such hook is determined entirely by its intersection with the diagonal structure, and these diagonal hooks are disjoint and cover all cells of the diagram.

If the diagonal has $d$ cells, then the $i$th diagonal hook has length

$$ h_i = 2a_i - 2i + 1, $$

where $a_i$ is the length of row $i$ of $\alpha$. Each $h_i$ is a positive odd integer, and the symmetry of the Ferrers diagram implies that

$$ h_1 > h_2 > \cdots > h_d, $$

since successive diagonal positions strictly decrease both row length and column length. Thus every self-conjugate partition determines a partition of $n$ into distinct odd parts.

Conversely, given a partition of $n$ into distinct odd parts

$$ n = (2b_1 - 1) + (2b_2 - 1) + \cdots + (2b_d - 1), \quad b_1 > b_2 > \cdots > b_d \ge 1, $$

one reconstructs a self-conjugate Ferrers diagram by placing diagonal hooks of lengths $2b_i - 1$ at diagonal positions and filling symmetrically. The reconstruction is unique because each hook determines exactly one diagonal cell and the symmetry condition forces all off-diagonal cells.

This establishes a bijection between self-conjugate partitions and partitions into distinct odd parts. Therefore the ordinary generating function for self-conjugate partitions is the generating function for partitions into distinct odd parts.

A partition into distinct odd parts uses each odd integer $2k-1$ at most once. The contribution of the part $2k-1$ is either absent or present once, giving a factor

$$ 1 + x^{2k-1}. $$

Independence over all odd parts yields the product

$$ \prod_{k \ge 1} (1 + x^{2k-1}). $$

Thus the generating function for self-conjugate partitions is

$$ \sum_{n \ge 0} s(n)x^n = \prod_{k \ge 1} (1 + x^{2k-1}), $$

where $s(n)$ denotes the number of self-conjugate partitions of $n$.

$$ \boxed{\prod_{k \ge 1} (1 + x^{2k-1})} $$