Proof of a Conjecture of Amitai Regev About Hook Multi-Sets Doron ZEILBERGER^{1}

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). 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 ∈ λ} .

The purpose of this short note is to prove Amitai Regev[R]’ intriguing Conjecture: For all non-negative integers n, A_{1}(n) = A_{2}(n). As usual, (z)_{a} := (1 − z)(1 − qz) ⋯ (1 − q^{a−1}z). The conjecture 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) .

1 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 . Sept. 13, 2009. Exclusive to the Personal Journal of Ekhad and Zeilberger and arxiv.org . Supported in part by the NSF.

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

Fact 1 (The q-Binomial Theorem)

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

(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}}.

(Let’s recall the proof 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.)

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.

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

[R] A. Regev, private communication .