The Gaussian Coefficient Revisited

Richard Ehrenborg and Margaret A. Readdy Department of Mathematics University of Kentucky Lexington, KY 40506-0027 USA

               richard.ehrenborg@uky.edu
                margaret.readdy@uky.edu

Abstract

We give a new q-(1 + q)-analogue of the Gaussian coefficient, also known as the qbinomial which, like the original q-binomial \left[{n \atop k}\right]_{q}, is symmetric in k and n−k. We show this q-(1+q)-binomial is more compact than the one discovered by Fu, Reiner, Stanton, and Thiem. Underlying our q-(1 + q)-analogue is a Boolean algebra decomposition of an associated poset. These ideas are extended to the Birkhoff transform of any finite poset. We end with a discussion of higher analogues of the q-binomial.

1 Introduction

Inspired by work of Fu, Reiner, Stanton, and Thiem [2], Cai and Readdy [1] asked the following question. Given a combinatorial q-analogue

X(q) = ∑_{w∈X} q^{a(w)},

where X is a set of objects and a(·) is a statistic defined on the elements of X, when can one find a smaller set Y and two statistics s and t such that

X(q) = ∑_{w∈Y} q^{s(w)} · (1 + q)^{t(w)}.

Such an interpretation is called an q-(1 + q)-analogue. Examples of q-(1 + q)-analogues have been determined for the q-binomial by Fu et al. [2], and for the q-Stirling numbers of the first and second kinds by Cai and Readdy [1], who also gave poset and homotopy interpretations of their q-(1 + q)-analogues.

In 1916 MacMahon [3, 4, 5] observed that the Gaussian coefficient, also known as the q-binomial coefficient, is given by

\left[{n \atop k}\right]_{q} = ∑_{w∈Ω_{n,k}} q^{inv(w)}.

Here Ω_{n,k} = 𝔖(0^{n−k}, 1^{k}) denotes all permutations of the multiset {0^{n−k}, 1^{k}}, that is, all words w = w_{1} ⋯ w_{n} of length n with n − k zeroes and k ones, and inv(·) denotes the inversion statistic defined by inv(w_{1}w_{2} ⋯ w_{n}) = |{(i, j) : 1 ≤ i < j ≤ n, w_{i} > w_{j}}|. Fu et al. defined a subset Ω′_{n,k} ⊆ Ω_{n,k} and two statistics a and b such that

\left[{n \atop k}\right]_{q} = ∑_{w∈Ω′_{n,k}} q^{a(w)} · (1 + q)^{b(w)}.

In this paper we will return to the original study by Fu et al. of the Gaussian coefficient. We discover a more compact q-(1 + q)-analogue which, like the original Gaussian coefficient, is also symmetric in the variables k and n − k. See Corollary 6 and Theorem 12. This symmetry was missing in Fu et al.’s original q-(1 + q)-analogue. We give a Boolean algebra decomposition of the related poset Ω_{n,k}. Since this poset is a distributive lattice, in the last section we extend these ideas to poset decompositions of any distributive lattice and other analogues.

2 A poset interpretation

In this section we consider the poset structure on 0-1-words in Ω_{n,k}. For further poset terminology and background, we refer the reader to [6].

We begin by making the set of elements Ω_{n,k} into a graded poset by defining the cover relation to be

u ∘ 01 ∘ v ≺ u ∘ 10 ∘ v,

where ∘ denotes concatenation of words. The word 0^{n−k}1^{k} is the minimal element and the word 1^{k}0^{n−k} is the maximal element in the poset Ω_{n,k}. Furthermore, this poset is graded by the inversion statistic. This poset is simply the interval [ˆ0, x] of Young’s lattice, where the minimal element ˆ0 is the empty Ferrers diagram and x is the Ferrers diagram consisting of n − k columns and k rows.

An alternative description of the poset Ω_{n,k} is that it is isomorphic to the Birkhoff transform of the Cartesian product of two chains. Let C_{m} denote the m-element chain. The poset Ω_{n,k} is isomorphic to the distributive lattice of all lower order ideals of the product C_{n−k} × C_{k}, usually denoted by J(C_{n−k} × C_{k}).

Definition 1. Let Ω′′_{n,k} consist of all 0,1-words v = v_{1}v_{2} ⋯ v_{n} in Ω_{n,k} such that

v_{1} ≤ v_{2}, v_{3} ≤ v_{4}, …, v_{2·⌊n/2⌋−1} ≤ v_{2·⌊n/2⌋}.

Observe that when n is odd there is no condition on the last entry w_{n}. Define two maps ϕ and ψ on Ω_{n,k} by sending the word w = w_{1}w_{2} ⋯ w_{n} to

ϕ(w) = min(w_{1}, w_{2}), max(w_{1}, w_{2}), min(w_{3}, w_{4}), max(w_{3}, w_{4}), …,
ψ(w) = max(w_{1}, w_{2}), min(w_{1}, w_{2}), max(w_{3}, w_{4}), min(w_{3}, w_{4}), ….

The map ϕ sorts the entries in positions 1 and 2, 3 and 4, and so on. If n is odd, the entry w_{n} remains in the same position. Similarly, the map ψ sorts in reverse order each pair of positions. Note that the map ϕ maps Ω_{n,k} surjectively onto the set Ω′′_{n,k}.

We have the following Boolean algebra decomposition of the poset Ω_{n,k}.

Theorem 2. The distributive lattice Ω_{n,k} has the Boolean algebra decomposition

Ω_{n,k} = ⋃_{v∈Ω′′_{n,k}}[v, ψ(v)].

Proof. Observe that the maps ϕ and ψ satisfy the inequalities ϕ(w) ≤ w ≤ ψ(w). Furthermore, the fiber of the map ϕ : Ω_{n,k} ⟶ Ω′′_{n,k} is isomorphic to a Boolean algebra, that is, ϕ^{−1}(v) ≅ [v, ψ(v)].

For v ∈ Ω′′_{n,k} define the statistic

asc_{odd}(v) = |{i : v_{i} < v_{i+1}, i odd}|,

that is, asc_{odd}(·) enumerates the number of ascents in odd positions.

Corollary 3. The q-binomial is given by

\left[{n \atop k}\right]_{q} = ∑_{v∈Ω′′_{n,k}} q^{inv(v)} · (1 + q)^{asc_{odd}(v)}.  (1)

Proof. It is enough to observe that the sum of the inversion statistic over the elements in the fiber ϕ^{−1}(v) = [v, ψ(v)] for v ∈ Ω′′_{n,k} is given by q^{inv(v)} · (1 + q)^{asc_{odd}(v)}.

A geometric way to understand this q-(1 + q)-interpretation is to consider lattice paths from the origin (0, 0) to (n − k, k) which only use east steps (1, 0) and north steps (0, 1). Color the squares of this (n − k) × k board as a chessboard, where the square incident to the origin is colored white. The map ϕ in the proof of Theorem 2 corresponds to taking a lattice path where every time there is a north step followed by an east step that turns around a white square, we exchange these two steps. The statistic asc_{odd} enumerates the number of times an east step is followed by a north step when this pair of steps borders a white square.

Let er(n, k) denote the cardinality of the set Ω′′_{n,k}. Then we have Proposition 4. The cardinalities er(n, k) satisfy the recursion

er(n, k) = er(n − 2, k − 2) + er(n − 2, k − 1) + er(n − 2, k) for 0 ≤ k ≤ n and n ≥ 2,

with the boundary conditions er(0, 0) = er(1, 0) = er(1, 1) = 1 and er(n, k) = 0 whenever k > n, k < 0 or n < 0.

Proof. A word in Ω′′_{n,k} begins with either 00, 01 or 11, yielding the three cases of the recursion.

Directly we obtain the generating polynomial.

Theorem 5. The generating polynomial for er(n, k) is given by

∑_{k=0}^{n} er(n, k) · x^{k} = (1 + x + x^{2})^{⌊n/2⌋} · (1 + x)^{n−2·⌊n/2⌋}.

We end with a statement concerning the symmetry of the q-(1 + q)-binomial.

Corollary 6. The set of defining elements for the q-(1 + q)-binomial satisfy the following symmetric relation:

|Ω′′_{n,k}| = |Ω′′_{n,n−k}|.

Proof. This follows from the fact that the generating polynomial for er(n, k) is a product of palindromic polynomials, and thus is itself is a palindromic polynomial.

3 Analysis of the Fu–Reiner–Stanton–Thiem interpretation

A weak partition is a finite non-decreasing sequence of non-negative integers. A weak partition λ = (λ_{1}, …, λ_{n−k}) with n − k parts and each part at most k where λ_{1} ≤ ⋯ ≤ λ_{n−k} corresponds to a Ferrers diagram lying inside an (n − k) × k rectangle with column i having height λ_{i}. These weak partitions are in direct correspondence with the set Ω_{n,k}.

Fu, Reiner, Stanton, and Thiem used a pairing algorithm to determine a subset Ω′_{n,k} ⊆ Ω_{n,k} of 0-1-sequences to define their q-(1 + q)-analogue of the q-binomial; see [2, Proposition 6.1]. This translates into the following statement. The set Ω′_{n,k} is in bijection with weak partitions into n − k parts with each part at most k such that

(a) if k is even, each odd part has even multiplicity,

(b) if k is odd, each even part (including 0) has even multiplicity.

Definition 7. Let frst(n, k) be the cardinality of the set Ω′_{n,k}.

Lemma 8. The quantity frst(n, k) counts the number of weak partitions into n − k parts where each part is at most k and each odd part has even multiplicity.

Proof. When k is even there is nothing to prove. When k is odd, by considering the complement of weak partitions with respect to the rectangle of size (n − k) × k, we obtain a bijective proof. The same complement proof also shows the case when k is even holds.

Theorem 9. The frst-coefficients satisfy the recursion

frst(n, k) = \begin{cases}frst(n − 1, k − 1) + frst(n − 1, k), & if k is even; \\ frst(n − 2, k − 2) + frst(n − 2, k − 1) + frst(n − 2, k), & if k is odd; \end{cases}

where 0 ≤ k ≤ n and n ≥ 2 with the boundary conditions frst(0, 0) = frst(1, 0) = frst(1, 1) = 1 and frst(n, k) = 0 whenever k > n, k < 0 or n < 0.

Proof. We use the characterization in Lemma 8. When k is even there are two cases. If the last part is k, remove it to obtain a weak partition counted by frst(n − 1, k). If the last part is less than k, then the weak partition is counted by frst(n − 1, k − 1).

When k is odd there are three cases. If the last two parts are equal to k, then removing these two parts yields a weak partition counted by frst(n − 2, k). Note that we cannot have the last part equal to k and the next to last part less than k since k is odd. If the last part is equal to k − 1, we can remove it to obtain a weak partition counted by frst(n − 2, k − 1). Finally, if the last part is less than or equal to k − 2, the weak partition is counted by frst(n − 2, k − 2).

Remark 10. For k odd we have the shorter recursion frst(n, k) = frst(n − 1, k − 1) + frst(n − 2, k). However, we use the longer recursion in the proof of Theorem 12.

Lemma 11. The inequality frst(n, k) ≤ frst(n + 1, k + 1) holds.

Proof. The weak partitions which lie inside the rectangle (n−k)×k and satisfy the conditions of Lemma 8 are included among the weak partitions which lie inside the larger rectangle (n − k) × (k + 1) and satisfy the same conditions.

Theorem 12. For all 0 ≤ k ≤ n the inequality |Ω′′_{n,k}| = er(n, k) ≤ frst(n, k) = |Ω′_{n,k}| holds.

Proof. We proceed by induction on n. The induction base is n ≤ 3. Furthermore, the inequality holds when k is 0, 1, n − 1 and n. When k is odd we have that

er(n, k) = er(n − 2, k − 2) + er(n − 2, k − 1) + er(n − 2, k)
≤ frst(n − 2, k − 2) + frst(n − 2, k − 1) + frst(n − 2, k)
= frst(n, k).

1  1
1 1  1 1
1 1 1  1 1 1
1 2 2 1  1 2 2 1
1 2 4 2 1  1 2 3 2 1
1 3 6 5 3 1  1 3 5 5 3 1
1 3 9 8 8 3 1  1 3 6 7 6 3 1
1 4 12 14 16 9 4 1  1 4 9 13 13 9 4 1
1 4 16 20 30 19 13 4 1  1 4 10 16 19 16 10 4 1
1 5 20 30 50 39 32 14 5 1  1 5 14 26 35 35 26 14 5 1
1 5 25 40 80 69 71 36 19 5 1  1 5 15 30 45 51 45 30 15 5 1

Table 1: The frst- and er-triangles for n ≤ 10.

Similarly, when k is even we have

er(n, k) = er(n − 2, k − 2) + er(n − 2, k − 1) + er(n − 2, k)
≤ frst(n − 2, k − 2) + frst(n − 2, k − 1) + frst(n − 2, k)
≤ frst(n − 1, k − 1) + frst(n − 2, k − 1) + frst(n − 2, k)
= frst(n − 1, k − 1) + frst(n − 1, k)
= frst(n, k),

where the second inequality follows from Lemma 11. These two cases complete the induction hypothesis.

See Table 1 to compare the values of frst(n, k) and er(n, k) for n ≤ 10.

4 Concluding remarks

Is it possible to find a q-(1 + q)-analogue of the Gaussian coefficient which has the smallest possible index set? We believe that our analogue is the smallest, but cannot offer a proof of a minimality. Perhaps a more tractable question is to prove that the Boolean algebra decomposition of Ω_{n,k} is minimal.

We can extend these ideas involving a Boolean algebra decomposition to any distributive lattice. Let P be a finite poset and let A be an antichain of P such that there is no cover relation in A, that is, there is no pair of elements u, v ∈ A such that u ≺ v. We obtain a Boolean algebra decomposition of the Birkhoff transform J(P) by defining

J′′(P) = {I ∈ J(P) : the ideal I has no maximal elements in the antichain A}.

The two maps ϕ and ψ are now defined as

ϕ(I) = I − {a ∈ A : the element a is maximal in I},
ψ(I) = I ∪ {a ∈ A : I ∪ {a} ∈ J(P)}.

We have the following decomposition theorem. Theorem 13. For P any finite poset the distributive lattice J(P) has the Boolean algebra decomposition

J(P) = ⋃_{I∈J′′(P)}[I, ψ(I)].

Yet again, how can we select the antichain A such that the above decomposition A has the fewest possible terms? Furthermore, would this give the smallest Boolean algebra decomposition?

Another way to extend the ideas of Theorem 2 is as follows. Define Ω_{n,k}^{r} to be the set of all words v ∈ Ω_{n,k} satisfying the inequalities

v_{1} ≤ v_{2} ≤ ⋯ ≤ v_{r},
v_{r+1} ≤ v_{r+2} ≤ ⋯ ≤ v_{2r},
…,
v_{r·⌊n/r⌋−r+1} ≤ v_{r·⌊n/r⌋−r+2} ≤ ⋯ ≤ v_{r·⌊n/r⌋}.

For 1 ≤ i ≤ ⌊r/2⌋ define the statistics b_{i}(v) for v ∈ Ω_{n,k}^{r} to be

b_{i}(v) = |{j ∈ [⌊n/r⌋] : v_{rj−r+1} + v_{rj−r+2} + ⋯ + v_{rj} ∈ {i, r − i}}|.

Theorem 14. The distributive lattice Ω_{n,k} has the decomposition

Ω_{n,k} = ⋃_{v∈Ω_{n,k}^{r}} Ω_{r,1}^{b_{1}(v)} × Ω_{r,2}^{b_{2}(v)} × ⋯ × Ω_{r,⌊r/2⌋}^{b_{⌊r/2⌋}(v)}.

Corollary 15. The q-binomial is given by

\left[{n \atop k}\right]_{q} = ∑_{v∈Ω_{n,k}^{r}} q^{inv(v)} · \left[{r \atop 1}\right]_{q}^{b_{1}(v)} · \left[{r \atop 2}\right]_{q}^{b_{2}(v)} ⋯ \left[{r \atop ⌊r/2⌋}\right]_{q}^{b_{⌊r/2⌋}(v)}.

The least complicated case is when r = 3, where only one term appears in the above poset product. This term is Ω_{3,1} which is the three element chain C_{3}. The associated Gaussian coefficient is 1 + q + q^{2}. Thus Corollary 15 could be called a q-(1 + q + q^{2})-analogue in the case of r = 3. As an example, we have

\left[{6 \atop 3}\right]_{q} = 1 + q · (1 + q + q^{2})^{2} + q^{4} · (1 + q + q^{2})^{2} + q^{9}.

On a poset level this is a decomposition of J(C_{3} × C_{3}) into two one-element posets of rank 0 and rank 9, and two copies of C_{3} × C_{3}, where one has its minimal element of rank 1 and the other of rank 4.

5 Acknowledgments

The authors thank the referee for helpful comments. This work was partially supported by a grant from the Simons Foundation (#206001 to Margaret Readdy).

References

[1] Y. Cai and M. Readdy, q-Stirling numbers: A new view, preprint,

http://arxiv.org/abs/1506.03249, 2015.

[2] S. Fu, V. Reiner, D. Stanton, and N. Thiem, The negative q-binomial, Electron J. Combin. 19 (1) (2012), Paper #P36.

[3] P. A. MacMahon, The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913), 281–322. In Collected Papers. Vol. I: Combinatorics, MIT Press, 1978, pp. 508–549.

[4] P. A. MacMahon, Two applications of general theorems in combinatory analysis, Proc. London Math. Soc. 15 (1916), 314–321. In Collected Papers. Vol. I: Combinatorics, MIT Press, 1978, pp. 556–563.

[5] P. A. MacMahon, Combinatory Analysis, Chelsea Publishing Co., 1960.

[6] R. P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd edition. Cambridge University Press, 2012.

2010 Mathematics Subject Classification: Primary 06A07; Secondary 05A05, 05A10, 05A30. Keywords: q-analogue, Birkhoff transform, distributive lattice, poset decomposition.

Received May 19 2016, revised version received August 31 2016; September 8 2016. Published in Journal of Integer Sequences, September 11 2016.

Return to Journal of Integer Sequences home page.