Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ae

SYMMETRY AND UNIMODALITY IN THE q, x, y-HIT NUMBERS

Fred Butler

Department of Mathematics, West Virginia University P.O. Box 6310, Morgantown, WV 26506-6310

                            fbutler@math.wvu.edu

Abstract. We prove symmetry, and in some cases symmetry and unimodality, of polynomials related to the q, x, y-hit numbers introduced by Haglund. These results generalize theorems proven by Haglund for the q-hit numbers. We also apply one of these results to obtain a corollary concerning a generalization of the Eulerian numbers.

Résumé. Nous prouvons la symétrie et dans certains cas la symétrie et l’unimodalité des polynômes relatifs aux q, x, y nombres de contacts introduits par Haglund, généralisant ainsi certains théorèmes. Un de ces résultats nous permet d’obtenir un corollaire à propos d’une généralisation des nombres Eulériens.

1. Introduction

1.1. Preliminaries. We will use the notation SQ_{n} to denote the n × n square chess board. We will number the columns of SQ_{n} with 1 through n going from left to right across the bottom, and the rows of SQ_{n} with 1 through n going from bottom to top. We will label a square on SQ_{n} in column i row j with (i, j).

More generally, a board will be any subset of SQ_{n} for some n ∈ ℕ. A Ferrers board is a board with non-decreasing column heights from left to right, or more precisely a board of

Figure 1. The Ferrers board B(h_{1}, d_{1}; …; h_{t}, d_{t}).

the form {(i, j) ∈ SQ_{n}| 1 ≤ j ≤ b_{i}, 1 ≤ i ≤ n} where b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n}. We will denote the Ferrers board with column heights b_{1}, b_{2}, …, b_{n} by B(b_{1}, …, b_{n}). We will also specify a Ferrers board by its step heights and depths. The Ferrers board B(h_{1}, d_{1}; …; h_{t}, d_{t}) is shown in Figure 1. We will call B = B(b_{1}, …, b_{n}) = B(h_{1}, d_{1}; …; h_{t}, d_{t}) a regular Ferrers board if b_{i} ≥ i for 1 ≤ i ≤ n, or equivalently if h_{1} + ⋯ + h_{i} ≥ d_{1} + ⋯ + d_{i} for 1 ≤ i ≤ t as was defined in [9]. In this paper we will focus on regular Ferrers boards.

A rook placement on a board B ⊆ SQ_{n} is a subset of squares of B such that no two of these squares lie in the same row or the same column. As the name suggests, these squares represent positions on an n × n chess board where non-attacking rooks can be placed. Let r_{k}(B) denote the number of k rook placements on B, and let h_{n,k}(B) denote the number of n rook placements on SQ_{n} such that exactly k rooks lie on B. These are known as the kth rook number and the kth hit number, respectively, of the board B.

1.2. Cycle-counting q-rook theory. The cycle-counting q-rook numbers were first introduced in the unpublished work of Ehrenborg, Haglund, and Readdy [4], defined only for Ferrers boards. These rook numbers generalize both the q-rook numbers R_{k}(q, B) of Garsia and Remmel [5], and the cycle-counting rook numbers r_{k}(y, B) of Chung and Graham [2]. In order to describe them, we need to define the following three statistics.

The first statistic is denoted inv_{B}, a generalization of the number of inversions of a permutation. Given a placement P of rooks on a Ferrers board B ⊆ SQ_{n}, let each rook cancel all squares to the right in its row and below in its column. We can then define inv_{B}(P) to be the number of squares of B which neither contain a rook from P nor are cancelled.

The second statistic is denoted cyc, and is a generalization of the number of cycles of a permutation. Given a rook placement P on a board B ⊆ SQ_{n}, it is possible to associate to P a simple directed graph G_{P} on n vertices. This fact was first noted in [6] (see also [2] and [3]). There is an edge from i to j in G_{P} if and only if there is a rook from P on the square (i, j). We can then define cyc(P) to be the number of cycles in G_{P}.

The third statistic, denoted E, depends on the following fact. Given any placement P of j non-attacking rooks in columns 1 through i − 1 of a Ferrers board B (where j ≤ i − 1), it is an easy exercise to see that if b_{i} ≥ i then there is exactly one square in column i where placement of a rook will complete a new cycle in the digraph G_{P}. If b_{i} < i then there is no square where placing a rook will complete a new cycle. Note that a regular Ferrers board will have such a square in each of its columns (since b_{i} ≥ i for all 1 ≤ i ≤ n). Now for i with b_{i} ≥ i we can define s_{i}(P) to be the unique square which, considering only rooks from P in columns 1 through i − 1 of P, completes a new cycle. Then let E(P) be the number of i such that b_{i} ≥ i and there is no rook from P in column i on or above square s_{i}(P). For the rook placement P pictured in Figure 2, we see that inv_{B}(P) = 4, cyc(P) = 2, and E(P) = 2 (corresponding to i = 4 and i = 5).

We will use the common notation [x] = (1 − q^{x})/(1 − q) to denote the q-analog of the real number x, and [n]! to denote the product [n][n − 1] ⋯ [2][1], the q-analog of n!. For n, k ∈ ℕ we denote by \left[{n \atop k}\right] the q-analog of the binomial coefficient \binom{n}{k}, equal to

\frac{[n]!}{[k]![n − k]!} = \frac{[n][n − 1] ⋯ [n − k + 1]}{[k]!}

SYMMETRY AND UNIMODALITY IN THE q, x, y-HIT NUMBERS 3

Figure 2. The placement P on B and the associated digraph G_{P}.

for k ≤ n and equal to 0 for k > n. It is a well known fact that \left[{n \atop k}\right] is a polynomial in q. More generally for z ∈ ℂ we will write \left[{z \atop k}\right] for

\frac{[z][z − 1] ⋯ [z − k + 1]}{[k]!}.

As in [4], we now define the kth cycle-counting q-rook number of a Ferrers board B by the equation

R_{k}(y, q, B) = ∑_{P k rooks on B}[y]^{cyc(P)}q^{inv_{B}(P)+(y−1)E(P)},  (1)

where the sum is taken over all placements P of k non-attacking rooks on B. Letting y = 1 in (1) yields the q-rook numbers of [5], and letting q → 1 gives the cycle-counting rook numbers of [2]. The R_{k}(y, q, B) satisfy the useful equation

∑_{k=0}^{n} R_{n−k}(y, q, B)[z][z − 1] ⋯ [z − k + 1]

= ∏_{i with b_{i}≥i}[z + b_{i} − i + y] ∏_{i with b_{i}<i}[z + b_{i} − i + 1], (2)

a version of the well-known factorization theorems proven for the r_{k}(B) [7], R_{k}(q, B) [5], and r_{k}(y, B) [2].

Haglund [9, p. 449] further extended this model by defining the q, x, y-hit numbers algebraically by the equation

∑_{k=0}^{n} A_{n,k}(x, y, q, B)z^{k}

= ∑_{k=0}^{n} R_{n−k}(y, q, B)[x][x + 1] ⋯ [x + k − 1]z^{k} ∏_{i=k+1}^{n}(1 − zq^{x+i−1}). (3)

The A_{n,k}(x, y, q, B) generalize the a_{n,k}(x, y, B) also discussed in [9] (obtained by letting q → 1 in (3)), along with the q-hit numbers of Garsia and Remmel [5] (letting x = y = 1) and the cycle-counting hit numbers in the model of Chung and Graham [2] (when x = 1 and q → 1).

The case x = y is studied in [1], where for a regular Ferrers board B the combinatorial interpretation

A_{n,k}(y, y, q, B) = ∑_{P n rooks on SQ_{n}, n − k rooks on B} [y]^{cyc(P)}q^{(n−cyc(P))(y−1)+b_{n,B}(P)+E(P)}

is given. Here the sum is taken over all placements of n non-attacking rooks on SQ_{n} such that exactly n − k of the rooks lie on B. The statistic E is as defined above, and b_{n,B}(P) is the number of squares on SQ_{n} which neither contain a rook from P nor are cancelled, after applying the following cancellation scheme:

(1) each rook cancels all squares to the right in its row;

(2) each rook on B cancels all squares above it in its column (squares both on B and strictly above B);

(3) each rook on B which is also on a square which completes a cycle cancels all squares below it in its column as well;

(4) each rook off B cancels all squares below it but above B. While no combinatorial interpretation is known for the A_{n,k}(x, y, q, B) when x ≠ y, the author suspects that one exists similar to that given for the a_{n,k}(x, y, B) in [9, p. 418]. Such an interpretation would enhance the results that follow.

In Section 2 we sketch an easy proof of the symmetry and unimodality of A_{n,k}(a, b, q, B) for a, b ∈ ℕ. Our proof for regular Ferrers boards is a simplified version of that given in [10], for an analogous result concerning the q-hit numbers. We also deduce two corollaries in this section. In Section 3, we prove symmetry of the polynomial A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]! for any regular Ferrers board B = B(h_{1}, d_{1}; …; h_{t}, d_{t}). Finally in Section 4, we prove unimodality of A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]! for a certain class of regular Ferrers boards.

2. Symmetry and Unimodality of A_{n,k}(a, b, q, B)

If B = B(h_{1}, d_{1}; …; h_{t}, d_{t}) ⊆ SQ_{n} is a Ferrers board, let us denote by B − h_{p} − d_{p} the Ferrers board B(h_{1}, d_{1}; …; h_{p} − 1, d_{p} − 1; … h_{t}, d_{t}) ⊆ SQ_{n−1}, obtained from B by decreasing the pth step by 1. We will write Area(B) for the number of squares in the board B.

Suppose

f(q) = ∑_{i=M}^{N} a_{i}q^{i},

is a polynomial in q with a_{M}, a_{N} ≠ 0. We call M + N the virtual degree of f. We will say the polynomial f(q) is zsu(d) if either

(1) f(q) is identically zero, or

(2) f(q) is in ℕ[q], symmetric, and unimodal with virtual degree d.

Note that for s ∈ ℕ, q^{s} is zsu(2s) and [s] is zsu(s − 1). It is also easy to see that if f and g are polynomials which are both zsu(d), then f + g is also zsu(d). We will use the following lemmas to prove the main proposition of this section. A proof of Lemma 2.1 can be found in [11].

Lemma 2.1. If f is zsu(d) and g is zsu(e), then fg is zsu(d + e).

Lemma 2.2. Let B = B(h_{1}, d_{1}; …; h_{t}, d_{t}) ⊆ SQ_{n} be a regular Ferrers board, B − h_{t} − d_{t} ⊆ SQ_{n−1} as described earlier. Then

A_{n,k}(x, y, q, B) = [k + y + d_{t} − 1]A_{n−1,k}(x, y, q, B − h_{t} − d_{t})

+ q^{k+y+d_{t}−2}[n + x − y − d_{t} − k + 1]A_{n−1,k−1}(x, y, q, B − h_{t} − d_{t})

for any 1 ≤ k ≤ n.

Proof. Let p = t in Lemma 5.7 of [9]. □

The following is now a simple corollary of the above lemmas. We offer a brief sketch of the proof.

Proposition 2.3. Let B = B(h_{1}, d_{1}; …; h_{t}, d_{t}) ⊆ SQ_{n} be a regular Ferrers board, a, b ∈ ℕ. If n + a + 1 ≥ b + d_{t} + k, then A_{n,k}(a, b, q, B) is zsu(Area(B) + n(b + k − 1) + k(a − 1) − \binom{n+1}{2}) for 0 ≤ k ≤ n.

Proof. The proof is by induction on Area(B). When k = 0, we use Lemma 2.1 with (2) and (3) to prove that

A_{n,0}(a, b, q, B) = ∏_{i=1}^{n}[b_{i} − i + b],

which is zsu(Area(B) + n(b − 1) − \binom{n+1}{2}). We then use Lemma 2.2, Lemma 2.1, and the fact that two polynomials which are zsu(d) sum to another polynomial which is zsu(d) for the case when k > 0. Note the assumption n + a + 1 ≥ b + d_{t} + k is necessary to ensure that the factor [n + a − b − d_{t} − k + 1] in the recurrence is a polynomial in q.

□

An immediate corollary is the following.

Corollary 2.4. For any regular Ferrers board B ⊆ SQ_{n} and m ∈ ℕ, the polynomial

∑_{P n rooks on SQ_{n}, n − k rooks on B} [m]^{cyc(P)}q^{(m−cyc(P))(y−1)+b_{n,B}(P)+E(P)}

is zsu(Area(B) + n(m + k − 1) + k(m − 1) − \binom{n+1}{2}).

Proof. Let x = y = m in Proposition 2.3, and use the combinatorial interpretation for A_{n,k}(y, y, q, B) given in Section 1.2. Note that assuming B is a regular Ferrers board, we always have n + m + 1 ≥ m + d_{t} + k. This is because the last d_{t} columns of B have height n, so in a placement of n non-attacking rooks on SQ_{n} with k rooks off B, we must have n − d_{t} ≥ k. □

A cycle-counting version of the Eulerian numbers is given in [1], defined by the equation

Ẽ_{n,k}(y, q) = ∑_{σ∈S_{n}, des(σ)=k−1}[y]^{rlmin(σ)}q^{(n−rlmin(σ))(y−1)+maj(σ)}.  (4)

Here des(σ) denotes the number of descents, and rlmin(σ) the number of right-to-left minima, in the permutation σ. A right-to-left minimum of σ_{1}σ_{2} ⋯ σ_{n} is an entry σ_{i} which is smaller than σ_{j} for all j > i (so for example rlmin(51243) = 3, corresponding to the right-to-left minima 3, 2, and 1). Note that right-to-left minima have the same overall distribution as cycles in S_{n}, justifying the term “cycle-counting.” It was proven in [1] that

Ẽ_{n,k}(y, q) = A_{n,k−1}(y, y, q, 𝕋_{n}),  (5)

where 𝕋_{n} = B(1, 2, …, n) denotes the triangular Ferrers board. In light of (5) and Proposition 2.3, the following can be easily proven.

Corollary 2.5. For m ∈ ℕ, the polynomial

∑_{σ∈S_{n}, des(σ)=k−1}[m]^{rlmin(σ)}q^{(n−rlmin(σ))(m−1)+maj(σ)}

is zsu(n(m + k − 2) + (k − 1)(m − 1)).

3. Symmetry of A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]!

In this section we prove a more general symmetry result for all regular Ferrers boards, namely the symmetry of the polynomial

\frac{A_{n,k}(a, b, q, B)}{∏_{i=1}^{t}[d_{i}]!},

where B = B(h_{1}, d_{1}; …; h_{t}, d_{t}). Throughout the rest of the paper we will use the notation H_{i} for the partial sum h_{1} + ⋯ + h_{i}, and D_{i} for d_{1} + ⋯ + d_{i}. We have the following lemmas.

Lemma 3.1. Let B = B(b_{1}, …, b_{n}) = B(h_{1}, d_{1}; …; h_{t}, d_{t}) be a regular Ferrers board, j ∈ ℕ. Then

\frac{∏_{i=1}^{n}[j + b_{i} − i + y]}{∏_{i=1}^{t}[d_{i}]!} = ∏_{i=1}^{t} \left[{j + H_{i} − D_{i−1} + y − 1 \atop d_{i}}\right].

Proof. We see that

∏_{i=1}^{n}[j + b_{i} − i + y] = ∏_{i=1}^{t} ([j + H_{i} − D_{i−1} + y − 1][(j + H_{i} − D_{i−1} + y − 1) − 1]

⋯ [(j + H_{i} − D_{i−1} + y − 1) − d_{i} + 1]).

Thus

\frac{∏_{i=1}^{n}[j + b_{i} − i + y]}{∏_{i=1}^{t}[d_{i}]!}

= ∏_{i=1}^{t} \frac{[j + H_{i} − D_{i−1} + y − 1] ⋯ [(j + H_{i} − D_{i−1} + y − 1) − d_{i} + 1]}{[d_{i}]!},

which is

∏_{i=1}^{t} \left[{j + H_{i} − D_{i−1} + y − 1 \atop d_{i}}\right]

by definition. □

Lemma 3.2. Let B = B(b_{1}, …, b_{n}) = B(h_{1}, d_{1}; …; h_{t}, d_{t}) ⊆ SQ_{n} be a regular Ferrers board. Then

\frac{A_{n,k}(x, y, q, B)}{∏_{i=1}^{t}[d_{i}]!} = ∑_{j=0}^{k} \left[{n + x \atop k − j}\right]\left[{x + j − 1 \atop j}\right](−1)^{k−j}q^{\binom{k−j}{2}} ∏_{i=1}^{t} \left[{j + H_{i} − D_{i−1} + y − 1 \atop d_{i}}\right].

Proof. By Lemma 5.1 of [9], we have

A_{n,k}(x, y, q, B) = ∑_{j=0}^{k} \left[{n + x \atop k − j}\right]\left[{x + j − 1 \atop j}\right](−1)^{k−j}q^{\binom{k−j}{2}} ∏_{i=1}^{n}[j + b_{i} − i + y].

The lemma now follows trivially from Lemma 3.1. □

We can now prove the following.

Theorem 3.3. Let B = B(h_{1}, d_{1}; …; h_{t}, d_{t}) be a regular Ferrers board (so H_{i} ≥ D_{i} for 1 ≤ i ≤ t). Let a, b ∈ ℕ with a ≥ b ≥ 1, and set

L_{k}^{a,b}(B) = Area(B) + n(b − 1) + k(n + a − 1) − ∑_{i=1}^{t} d_{i}D_{i}.

Then A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]! is either zero or symmetric with virtual degree L_{k}^{a,b}(B).

Proof. By Lemma 3.2, A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]! =

∑_{j=0}^{k} \left[{n + a \atop k − j}\right]\left[{a + j − 1 \atop j}\right](−1)^{k−j}q^{\binom{k−j}{2}} ∏_{i=1}^{t} \left[{j + H_{i} − D_{i−1} + b − 1 \atop d_{i}}\right],

which is a polynomial in q (the first two q-binomial coefficients in each summand are clearly polynomials, and the third is since H_{i} ≥ D_{i} ≥ D_{i−1} and b ≥ 1). Using the fact that \left[{r \atop s}\right] is symmetric with virtual degree s(r − s) and Lemma 2.1, we see that each term on the right side above has virtual degree (k − j)(n + a − k + j) + j(a − 1) + (k − j)(k − j − 1) + ∑_{i=1}^{t} d_{i}(j + H_{i} − D_{i} + b − 1) (which is exactly L_{k}^{a,b}(B)). We then conclude that if A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]! is non-zero, then it is symmetric with virtual degree L_{k}^{a,b}(B). □

4. Unimodality of A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]!

In this section we give some sufficient conditions on the regular Ferrers board B for the polynomial of the previous section to also be unimodal. Let us first define some more notation.

Suppose we have integers h_{1}, …, h_{t}, d_{1}, …, d_{t}, and e_{1}, …, e_{t} with d_{i} ∈ ℙ, h_{i} ∈ ℕ, and 0 ≤ e_{i} ≤ d_{i}. We will denote the vector (e_{1}, e_{2}, …, e_{t}) by e⃗. We will continue to denote the partial sum h_{1} + ⋯ + h_{i} by H_{i}, d_{1} + ⋯ + d_{i} by D_{i}, and we will also let E_{i} = e_{1} +⋯+e_{i}. We make the convention that H_{0} = D_{0} = E_{0} = 0. For fixed h_{1}, …, h_{t} and d_{1}, …, d_{t} we can define

P (e⃗, x, y) = ∏_{i=1}^{t} \left[{H_{i} − D_{i−1} + E_{i−1} + y − 1 \atop d_{i} − e_{i}}\right]\left[{D_{i} + D_{i−1} − H_{i} − E_{i−1} + x − y \atop e_{i}}\right]

and prove the following lemmas.

Lemma 4.1. Let B = B(h_{1}, d_{1}; … h_{t−1}, d_{t−1}; h_{t}, d_{t}) ⊆ SQ_{n} be a regular Ferrers board, B′ = B(h_{1}, d_{1}; …; h_{t−1}, d_{t−1}) ⊆ SQ_{H_{t−1}}. Then

A_{n,k}(x, y, q, B) = [d_{t}]! ∑_{s=k−d_{t}}^{k} A_{H_{t−1},s}(x, y, q, B′)\left[{y + d_{t} + s − 1 \atop d_{t} − k + s}\right]

× \left[{n − y − d_{t} + x − s \atop k − s}\right]q^{(k−s)(y+k−1)}.

Proof. Let p = t in Corollary 5.10 of [9] and note that because B is a regular Ferrers board, H_{t} = D_{t} = n. □

Lemma 4.2. Let B = B(h_{1}, d_{1}; …; h_{t}, d_{t}) be a regular Ferrers board. Then

A_{n,k}(x, y, q, B) = ∏_{i=1}^{t}[d_{i}]! ∑_{e_{1}+···+e_{t}=k, 0≤e_{i}≤d_{i}} P (e⃗, x, y) ∏_{i=1}^{t} q^{e_{i}(H_{i}−D_{i}+E_{i}+y−1)}. (6)

Proof. By induction on t. When t = 1 we have that d_{1} = n, and Lemma 4.1 gives us

A_{n,k}(x, y, q, B) = [d_{1}]! ∑_{s=k−n}^{k} A_{0,s}(x, y, q, ∅)\left[{y + n + s − 1 \atop d_{1} − k + s}\right]

× \left[{n − y − n + x − s \atop k − s}\right] × q^{(k−s)(y+k−1)}. (7)

In this case we have that H_{1} = D_{1} = d_{1} = n and D_{0} = H_{0} = 0, so we get that the s = 0 term in (7) is equal to

[d_{1}]!\left[{H_{1} − D_{0} + y − 1 \atop d_{1} − k}\right]\left[{D_{1} + D_{0} − H_{1} + x − y \atop k}\right] × q^{k(H_{1}−D_{1}+k+y−1)}.  (8)

Note that by definition

A_{0,s}(x, y, q, ∅) = δ_{s,0},

so the only nonzero summand in (7) occurs when s = 0 and hence (8) is actually equal to (7). Finally if we recall that E_{1} = e_{1} and E_{0} = 0, we can rewrite (8) as

[d_{1}]! ∑_{e_{1}=k, 0≤e_{1}≤d_{1}} \left[{H_{1} − D_{0} + E_{0} + y − 1 \atop d_{1} − e_{1}}\right]

× \left[{D_{1} + D_{0} − H_{1} − E_{0} + x − y \atop e_{1}}\right] × q^{e_{1}(H_{1}−D_{1}+E_{1}+y−1)},

which is exactly of the form of (6).

For t > 1, Lemma 4.1 gives that

A_{n,k}(x, y, q, B) = [d_{t}]! ∑_{E_{t−1}=E_{t}−d_{t}}^{E_{t}} A_{H_{t−1},E_{t−1}}(x, y, q, B′)\left[{y + d_{t} + E_{t−1} − 1 \atop d_{t} − e_{t}}\right]

× \left[{n − y − d_{t} + x − E_{t−1} \atop e_{t}}\right] × q^{e_{t}(y+E_{t}−1)}. (9)

Here we are letting E_{t−1} = s and defining e_{t} = k − s and E_{t} = E_{t−1} + e_{t} = k. Since B is regular H_{t} = D_{t} = n, so H_{t} − D_{t−1} = D_{t} − D_{t−1} = d_{t} and (9) can be rewritten as

A_{n,k}(x, y, q, B) = [d_{t}]! ∑_{e_{t}=0}^{d_{t}} A_{H_{t−1},E_{t−1}}(x, y, q, B′)\left[{H_{t} − D_{t−1} + E_{t−1} + y − 1 \atop d_{t} − e_{t}}\right]

× \left[{D_{t} + D_{t−1} − H_{t} − E_{t−1} + x − y \atop e_{t}}\right] × q^{e_{t}(H_{t}−D_{t}+E_{t}+y−1)}.

By the inductive hypothesis, the above is equal to

[d_{t}]! ∑_{e_{t}=0}^{d_{t}} \{ ∏_{i=1}^{t−1}[d_{i}]! ∑_{e_{1}+···+e_{t−1}=E_{t−1}, 0≤e_{i}≤d_{i}} ∏_{i=1}^{t−1} \left[{H_{i} − D_{i−1} + E_{i−1} + y − 1 \atop d_{i} − e_{i}}\right]

× \left[{D_{i} + D_{i−1} − H_{i} − E_{i−1} + x − y \atop e_{i}}\right]q^{e_{i}(H_{i}−D_{i}+E_{i}+y−1)}\}

× \left[{H_{t} − D_{t−1} + E_{t−1} + y − 1 \atop d_{t} − e_{t}}\right]\left[{D_{t} + D_{t−1} − H_{t} − E_{t−1} + x − y \atop e_{t}}\right]q^{e_{t}(H_{t}−D_{t}+E_{t}+y−1)},

which is

∏_{i=1}^{t}[d_{i}]! ∑_{e_{1}+···+e_{t}=k, 0≤e_{i}≤d_{t}} P (e⃗, x, y) ∏_{i+1}^{t} q^{e_{i}(H_{i}−D_{i}+E_{i}+y−1)},

as desired. □

Lemma 4.3. Let B = B(h_{1}, d_{1}; …; h_{t}, d_{t}) be a regular Ferrers board, a, b ∈ ℕ with a ≥ b ≥ 1. Let e_{i}, d_{i}, h_{i}, E_{i}, D_{i}, and H_{i} be as in the definition of P (e⃗, x, y). Assume that B is such that d_{i−1}+d_{i} ≥ h_{i} for 1 ≤ i ≤ t (where d_{0} := 0). If any of the numerators of the q-binomial coefficients in

P (e⃗, a, b) = ∏_{i=1}^{t} \left[{H_{i} − D_{i−1} + E_{i−1} + b − 1 \atop d_{i} − e_{i}}\right]\left[{D_{i} + D_{i−1} − H_{i} − E_{i−1} + a − b \atop e_{i}}\right]

are negative, then P (e⃗, a, b) = 0.

Proof. First note that H_{i} − D_{i−1} + E_{i−1} + b − 1 ≥ 0 for 1 ≤ i ≤ t, since H_{i} ≥ D_{i} ≥ D_{i−1} and b ≥ 1, so none of the numerators in the first q-binomial coefficient of the product are ever negative.

Now suppose that D_{k} + D_{k−1} − H_{k} − E_{k−1} + a − b < 0 for some k with 0 ≤ k ≤ t. Note D_{1} + D_{0} − H_{1} − E_{0} + a − b = d_{1} − h_{1} + a − b, and since we assumed d_{i−1} + d_{i} ≥ h_{i} (and in particular d_{1} ≥ h_{1}) and a ≥ b, we have that d_{1} − h_{1} + a − b ≥ 0. Thus we see that such a k must be greater than 2.

Now choose j such that D_{i} + D_{i−1} − H_{i} − E_{i−1} + a − b ≥ 0 for 1 ≤ i < j, but D_{j} +D_{j−1} −H_{j} −E_{j−1} +a−b < 0 (such a j exists because of the remarks in the previous paragraph). Then D_{j}+D_{j−1}−H_{j}−E_{j−1}+a−b < 0 implies D_{j}+D_{j−1}−H_{j}−E_{j−2}+a−b < e_{j−1}, which is equivalent to d_{j} + d_{j−1} − h_{j} + D_{j−1} + D_{j−2} − H_{j−1} − E_{j−2} + a − b < e_{j−1}, which implies D_{j−1} + D_{j−2} − H_{j−1} − E_{j−2} + a − b < e_{j−1} (since d_{j} + d_{j−1} ≥ h_{j}). Hence

\left[{D_{j−1} + D_{j−2} − H_{j−1} − E_{j−2} + a − b \atop e_{j−1}}\right] = 0,

since the numerator is non-negative by definition of j but less than the denominator, so the product P (e⃗, a, b) is 0 as well. □

We are now ready to prove the main theorem of this section, the unimodality of the A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]!.

Theorem 4.4. Let B = B(h_{1}, d_{1}; …; h_{t}, d_{t}) be a regular Ferrers board such that d_{i−1} + d_{i} ≥ h_{i} for 1 ≤ i ≤ t. Let a, b ∈ ℕ with a ≥ b ≥ 1, and set

L_{k}^{a,b}(B) = Area(B) + n(b − 1) + k(n + a − 1) − ∑_{i=1}^{t} d_{i}D_{i}

as before. Then A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]! is zsu(L_{k}^{a,b}(B)).

Proof. We apply Lemma 4.2, which says that

\frac{A_{n,k}(a, b, q, B)}{∏_{i=1}^{t}[d_{i}]!} = ∑_{e_{1}+···+e_{t}=k, 0≤e_{i}≤d_{i}} P (e⃗, a, b) ∏_{i=1}^{t} q^{e_{i}(H_{i}−D_{i}+E_{i}+b−1)},

and all of the terms on the right hand side above are in ℕ[q] by Lemma 4.3. Using the fact that \left[{r \atop s}\right] is zsu(s(r − s)) (for a proof of the unimodality see [8]) along with Lemma 2.1, each term above is zsu(∑_{i=1}^{t}{(d_{i} − e_{i})(H_{i} − D_{i} + E_{i} + b − 1) + e_{i}(D_{i} + D_{i−1} − H_{i} − E_{i} + a − b) + 2e_{i}(H_{i} − D_{i} + E_{i} + b − 1)}). A simple calculation shows this is the same zsu(L_{k}^{a,b}(B)). Thus A_{n,k}(a, b, q, B)/ ∏_{i=1}^{t}[d_{i}]! is zsu(L_{k}^{a,b}(B)) as well. □

References

[1] F. Butler. Rook theory and cycle-counting permutations statistics. Adv. in Appl. Math., 33:655– 675, 2004.

[2] F. Chung and R. Graham. On the cover polynomial of a digraph. J. Combin. Theory, Ser. B, 65:273–290, 1995.

[3] M. Dworkin. Factorization of the cover polynomial. J. Combin. Theory, Ser. B, 71:17–53, 1997.

[4] R. Ehrenborg, J. Haglund, and M. Readdy. Colored juggling patterns and weighted rook placements, 1996. Unpublished manuscript.

[5] A. Garsia and J. Remmel. q-Counting rook configurations and a formula of Frobenius. J. Combin. Theory, Ser. A, 41:246–275, 1986.

[6] I. Gessel. Generalized rook polynomials and orthogonal polynomials. In Dennis Stanton, editor, q-Series and Partitions, IMA Volumes in Mathematics and Its Applications, pages 159–167. Springer Verlag, 1989.

[7] J. Goldman, J. Joichi, and D. White. Rook theory I: Rook equivalence of Ferrers boards. Proc. Amer. Math. Soc., 52:485–492, 1975.

[8] F. Goodman and K. O’Hara. On the Gaussian polynomials. In Dennis Stanton, editor, q-Series and Partitions, IMA Volumes in Mathematics and Its Applications, pages 57–66. Springer Verlag, 1989.

[9] J. Haglund. Rook theory and hypergeometric series. Adv. in Appl. Math., 17:408–459, 1996.

[10] J. Haglund. q-Rook polynomials and matrices over finite fields. Adv. in Appl. Math., 20:450–487, 1998.

[11] R. Stanley. Log-concave and unimodal sequences in algebra, combinatorics, and geometry. Ann. NY Acad. Sci., 576:500–534, 1989.