A Multi-set Identity for Partitions Amitai REGEV^{1} and Doron ZEILBERGER^{2}

Added Sept. 22, 2009 Guo-Niu Han kindly pointed out to us (something that we should have noticed ourselves if we would have been in the habit of reading carefully all the papers that we cite), that our main result is contained in [B.H.]. Introduction Given an integer-partition λ ⊢ n and a box (a cell) v = [i, j] ∈ λ it determines the arm length a_{v} (= λ_{i} − j), the leg length l_{v} (=λ′_{j} − i), and the left length f_{v} (= j − 1). Thus, for example, the hook length h_{v} is given by h_{v} = a_{v} + l_{v} + 1. Denote p_{v} = a_{v} + f_{v} + 1. C. Bessenrodt [B], and R. Bacher and L. Manivel [B.M] (see also [B.H]) proved the following identity:

(1)  ∑_{λ⊢n} ∑_{v∈λ} x^{h_{v}} = ∑_{λ⊢n} ∑_{v∈λ} x^{p_{v}},

which is equivalent to the multi-set identity:

(2)  ⋃_{λ⊢n}{h_{v} | v ∈ λ} = ⋃_{λ⊢n}{p_{v} | v ∈ λ}.

In this note we prove the following refinement of (2). Fill v with a pair of numbers in two different ways: First Filling: Fill v with (a_{v}, l_{v}). Second Filling: Fill v with (a_{v}, f_{v}). This yields the following two multi-sets of pairs:

A_{1}(n) = ⋃_{λ⊢n}{(a_{v}, l_{v})|v ∈ λ} ,

A_{2}(n) = ⋃_{λ⊢n}{(a_{v}, f_{v})|v ∈ λ} .

1 Department of Theoretical Mathematics, Weizmann Institute of Science, Rehovot 76100, ISRAEL.

amitai dot regev at weizmann dot ac dot il , http://www.wisdom.weizmann.ac.il/˜ regev/ .

2 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . Supported in part by the USA National Science Foundation.

Theorem 1: For all non-negative integers n we have the multi-set identity,

A_{1}(n) = A_{2}(n).

The proof here is by applying the technique of generating functions. Theorem 1 indicates that for each n there is a map φ on the cells of the partitions of n, φ : v → φ(v), such that (a_{v}, f_{v}) = (a_{φ(v)}, l_{φ(v)}). The construction of an explicit such φ – for all n – would yield a bijective proof of Theorem 1.

The proof.

As usual, (z)_{a} := (1 − z)(1 − qz) ⋯ (1 − q^{a−1}z).

The proof would follow from the following two lemmas.

Lemma 1: Let M_{1}(c, d)(n) be the number of times the pair (c, d) shows up in A_{1}(n), then

∑_{n=0}^{∞} M_{1}(c, d)(n)q^{n} = \frac{q^{c+d+1}}{1 − q^{c+d+1}} · \frac{1}{(q)_{∞}} .  (1)

Lemma 2: Let M_{2}(c, d)(n) be the number of times the pair (c, d) shows up in A_{2}(n), then

∑_{n=0}^{∞} M_{2}(c, d)(n)q^{n} = \frac{q^{c+d+1}}{1 − q^{c+d+1}} · \frac{1}{(q)_{∞}} .  (2)

Proof of Lemma 2: M_{2}(c, d)(n) counts the number of Ferrers diagrams of n where one of the cells that has (right) arm c and left-arm d is marked. Obviously it belongs to a row of length c + d + 1, and each such row has exactly one such cell. Hence this is the same as counting the number of Ferrers diagrams of n where one of the rows of length c + d + 1 is marked. We can construct such a Ferrers diagram (with any number of cells) by first drawing that row of length c + d + 1 (weight q^{c+d+1}) then putting below it an arbitrary Ferrers diagram with largest part ≤ c + d + 1, whose generating function is 1/((1−q)(1−q^{2}) ⋯ (1−q^{c+d+1})), and then placing above the abovementioned fixed row any Ferrers diagram whose smallest part is ≥ c + d + 1, whose generating function is 1/((1−q^{c+d+1})(1−q^{c+d+2}) ⋯). Combining, we get that the generating function of such marked creatures, which is the left side of (2), is the right side of (2) .

Before proving Lemma 1 we have to recall certain basic facts from q-land.

Fact 1 (The q-Binomial Theorem [essentially Theorem 2.1 of [A]^{3} ]).

\frac{1}{(z)_{a+1}} = ∑_{j=0}^{∞} \frac{(q)_{a+j}}{(q)_{a}(q)_{j}} z^{j} .

3 But the “conditions” |q| < 1, |t| < 1, stated by Andrews, are, in our world-view, a category mistake.

(This is easily proved by induction on a).

When a = ∞ this simplifies to

Fact 2

\frac{1}{(z)_{∞}} = ∑_{j=0}^{∞} \frac{z^{j}}{(q)_{j}} .

Fact 3: The generating function for Ferrers diagrams bounded in an m by n rectangle is \frac{(q)_{m+n}}{(q)_{m}(q)_{n}}.

This is Proposition 1.3.19 in [St] and Theorem 3.1 of [A]. Here is a proof by induction of this elementary fact. Let the generating function be F (m, n; q). Consider the last cell of the top row. If it is occupied, the generating function of these diagrams is q^{n}F (m−1, n) (remove the fully-occupied top row), if it is not, it is F (m, n − 1) (delete the empty rightmost column), getting the recurrence F (m, n; q) = q^{n}F (m − 1, n; q) + F (m, n − 1; q). Then verify that the same recurrence is satisfied by \frac{(q)_{m+n}}{(q)_{m}(q)_{n}}, and check the trivial initial conditions m = 0 and n = 0.

By sending n to infinity we obtain

Fact 4: The generating function for Ferrers diagrams with parts bounded by m is \frac{1}{(q)_{m}}. By conjugation, this is also the generating function for Ferrers diagrams with at most m parts.

Proof of Lemma 1: The left-side of (1) is the generating function for Ferrers diagrams where one hook with arm-length c and leg-length d is marked. Let’s figure out the generating function (weight-enumerator) for all such (c, d)-hook-marked Ferrers diagrams.

Suppose the corner of that hook is at cell (i + 1, j + 1) (i.e. the (i + 1)-row and the (j + 1)-column). Here 0 ≤ i < ∞ and 0 ≤ j < ∞. Let’s look at its anatomy. It consists of seven parts. (See diagram in http://www.math.rutgers.edu/˜ zeilberg/mamarim/mamarimhtml/TemunaFerrers.html ).

1. Strictly left of and above cell (i+1, j +1). This is a fully occupied i by j rectangle with weight q^{ij}.

2. Above the arm (of length c + 1). This is a fully occupied i by c + 1 rectangle with weight q^{(c+1)i}.

3. To the left of the leg (of length d + 1). This is a fully occupied d + 1 by j rectangle with weight q^{(d+1)j} .

4. The Ferrers diagram with ≤ i rows lying above and to the right of the arm. By Fact 4, the generating function of this is 1/(q)_{i}.

5. The Ferrers diagram with ≤ j columns lying below and to the left of the leg. By Fact 4, the generating function of this is 1/(q)_{j}.

6. The hook itself. This gives generating function q^{c+d+1}.

7. The Ferrers diagram formed inside the hook, i.e. lying below the arm and to the right of the leg. By Fact 3 its generating function is \frac{(q)_{c+d}}{(q)_{c}(q)_{d}}. Combining, we see that the generating function for these (c, d)-hook-marked Ferrers diagrams is

\frac{(q)_{c+d}}{(q)_{c}(q)_{d}} · q^{c+d+1} · q^{ij+i(c+1)+j(d+1)} · \frac{1}{(q)_{i}} · \frac{1}{(q)_{j}} .

Summing over all 0 ≤ i, j < ∞, we get that the generating function on the left of (1) equals

\frac{(q)_{c+d}}{(q)_{c}(q)_{d}} q^{c+d+1} ∑_{i=0}^{∞} ∑_{j=0}^{∞} q^{ij+i(c+1)+j(d+1)} \frac{1}{(q)_{i}} \frac{1}{(q)_{j}}

= \frac{(q)_{c+d}}{(q)_{c}(q)_{d}} q^{c+d+1} ∑_{i=0}^{∞} \frac{1}{(q)_{i}} q^{i(c+1)} ∑_{j=0}^{∞} q^{j(i+d+1)} \frac{1}{(q)_{j}}

= \frac{(q)_{c+d}}{(q)_{c}(q)_{d}} q^{c+d+1} ∑_{i=0}^{∞} \frac{1}{(q)_{i}} q^{i(c+1)} \frac{1}{(q^{d+i+1})_{∞}} ,

by Fact 2 with z = q^{d+i+1}. This, in turn, equals

\frac{(q)_{c+d}}{(q)_{c}} q^{c+d+1} ∑_{i=0}^{∞} q^{i(c+1)} \frac{1}{(q)_{∞}} \frac{(q^{i+1})_{d}}{(q)_{d}}

= \frac{q^{c+d+1}}{(q)_{∞}} \frac{(q)_{c+d}}{(q)_{c}} ∑_{i=0}^{∞} q^{i(c+1)} \frac{(q)_{i+d}}{(q)_{d}(q)_{i}}

= \frac{q^{c+d+1}}{(q)_{∞}} \frac{(q)_{c+d}}{(q)_{c}} \frac{1}{(q^{c+1})_{d+1}} ,

by Fact 1 with z = q^{c+1}. Finally, this equals

= \frac{q^{c+d+1}}{(q)_{∞}} · \frac{(1 − q)(1 − q^{2}) ⋯ (1 − q^{c+d})}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{c+d+1})} = \frac{q^{c+d+1}}{(q)_{∞}} · \frac{1}{(1 − q^{c+d+1})} .

Reference

[A] G. Andrews, The Theory of Partitions, Cambridge University Press (1984).

[B] C. Bessenrodt, On hooks of Young diagrams, Ann. of Comb., 2 (1998), pp. 103-110. [B.M] R. Bacher and L. Manivel, Hooks and powers of parts in partitions, Sem. Lothar. Combin. Vol 47, article B47d, (2001) 11 pages. [B.H] C. Bessenrodt and G.N Han, Symmetry distribution between hook length and part length for partitions, Discrete Mathematics (online 4 June 2009).

[St] R. Stanley, Enumerative Combinatorics I, Cambridge Studies in Advanced Mathematics 49 (1986).