Parity Theorems for Statistics on Lattice Paths and Laguerre Configurations

Mark A. Shattuck and Carl G. Wagner Mathematics Department University of Tennessee Knoxville, TN 37996-1300 USA

                 shattuck@math.utk.edu
                  wagner@math.utk.edu

Abstract

We examine the parity of some statistics on lattice paths and Laguerre configurations, giving both algebraic and combinatorial treatments. For the former, we evaluate q-generating functions at q = −1; for the latter, we define appropriate parity-changing involutions on the associated structures. In addition, we furnish combinatorial proofs for a couple of related recurrences.

1 Introduction

To establish the familiar result that a finite nonempty set has equally many subsets of odd and of even cardinality it suffices either to set q = −1 in the generating function

∑_{S⊆[n]} q^{|S|} = ∑_{k=0}^{n} \binom{n}{k}q^{k} = (1 + q)^{n},  (1.1)

where [n] := {1, …, n}, or to observe that the map

S ↦ \begin{cases}S ∪ \{1\}, & if 1 ∉ S; \\ S − \{1\}, & if 1 ∈ S, \end{cases}  (1.2)

is a parity changing involution of 2^{[n]}.

With this simple example as a model, we analyze the parity of a well known statistic on lattice paths, as well as two statistics on what Garsia and Remmel [3] call Laguerre configurations, i.e., distributions of labeled balls to unlabeled, contents-ordered boxes. These statistics have in common the fact that their generating functions all involve q-binomial coefficients.

In §2 we evaluate such coefficients and their sums, known as Galois numbers, when q = −1, giving both algebraic and bijective proofs. We also give a bijective proof of a recurrence for Galois numbers, furnishing an elementary alternative to Goldman and Rota’s proof by the method of linear functionals [4]. In §3 we carry out a similar evaluation of the two types of q-Lah numbers that arise as generating functions for the aforementioned Laguerre configuration statistics. In addition, we supply a combinatorial proof of a recurrence for sums of Lah numbers.

The notational conventions of this paper are as follows: ℕ := {0, 1, 2, … }, ℙ := {1, 2, … },

[0] := ∅, and [n] := {1, …, n} for n ∈ ℙ. If q is an indeterminate, then 0_{q} := 0,

n_{q} := 1 + q + ⋯ + q^{n−1} if n ∈ ℙ, 0!_{q} := 1, n!_{q} := 1_{q}2_{q} ⋯ n_{q} if n ∈ ℙ, and

\binom{n}{k}_{q} := \begin{cases}\frac{n!_{q}}{k!_{q}(n−k)!_{q}} , & if 0 ≤ k ≤ n; \\ 0, & if k < 0 or 0 ≤ n < k. \end{cases}  (1.3)

Our notation in (1.3) for the q-binomial coefficient, which agrees with Knuth’s [5], has the advantage over the traditional notation \left[{n \atop k}\right] that it can be used to reflect particular values of the parameter q.

2 A Statistic on Lattice Paths

Let Λ(n, k) denote the set of (minimal) lattice paths from (0, 0) to (k, n−k), where 0 ⩽ k ⩽ n. Each λ ∈ Λ(n, k) corresponds to a sequential arrangement t_{1} ⋯ t_{n} of the multiset {1^{k}, 2^{n−k}}, with 1 representing a horizontal and 2 a vertical step. Hence, |Λ(n, k)| = \binom{n}{k}. Moreover, since the area α(λ) subtended by λ is equal to the number of inversions in the corresponding word (i.e., the number of ordered pairs (i, j) with 1 ⩽ i < j ⩽ n such that t_{i} > t_{j}), and since the q-binomial coefficient is the generating function for the statistic that records the number of inversions in such words [10, Prop. 1.3.17], it follows that

∑_{λ∈Λ(n,k)} q^{α(λ)} = \binom{n}{k}_{q},  (2.1)

a result that Berman and Fryer [1, p. 218] attribute to Polya. With

Λ(n) := ⋃_{0⩽k⩽n} Λ(n, k),  (2.2)

it follows that

∑_{λ∈Λ(n)} q^{α(λ)} = G_{q}(n) := ∑_{k=0}^{n} \binom{n}{k}_{q}.  (2.3)

The polynomials G_{q}(n) have been termed Galois numbers by Goldman and Rota [4].

Let Λ_{r}(n) := {λ ∈ Λ(n) : α(λ) ≡ r (mod 2)}, and let Λ_{r}(n, k) := Λ(n, k) ∩ Λ_{r}(n). Clearly,

\binom{n}{k}_{−1} = |Λ_{0}(n, k)| − |Λ_{1}(n, k)|,  (2.4)

and

G_{−1}(n) = |Λ_{0}(n)| − |Λ_{1}(n)|.  (2.5)

In evaluating (2.4) and (2.5) we shall employ several alternative characterizations of \binom{n}{k}_{q}, namely, the recurrence

\binom{n}{k}_{q} = \binom{n − 1}{k − 1}_{q} + q^{k}\binom{n − 1}{k}_{q},  ∀n, k ∈ ℙ,  (2.6)

with \binom{n}{0}_{q} = δ_{n,0} and \binom{0}{k}_{q} = δ_{k,0}, ∀ n, k ∈ ℕ, the generating function

∑_{n⩾0} \binom{n}{k}_{q}x^{n} = \frac{x^{k}}{(1 − x)(1 − qx) ⋯ (1 − q^{k}x)},  ∀k ∈ ℕ,  (2.7)

and the summation formula

\binom{n}{k}_{q} = ∑_{\begin{matrix}d_{0}+d_{1}+···+d_{k}=n−k \\ d_{i}∈ℕ \end{matrix}}q^{d_{1}+2d_{2}+···+kd_{k}}.  (2.8)

See [11, pp. 201–202] for further details.

Setting q = −1 in (2.7) and treating separately the even and odd cases for k yields

Theorem 2.1. If 0 ⩽ k ⩽ n, then

\binom{n}{k}_{−1} = \begin{cases}0, & if n is even and k is odd; \\ \binom{⌊n/2⌋}{⌊k/2⌋}, & otherwise. \end{cases}  (2.9)

A straightforward application of (2.9) yields

Corollary 2.1.1. For all n ∈ ℕ,

G_{−1}(n) = 2^{⌈n/2⌉}.  (2.10)

The above results are well known and apparently very old. But the following bijective proofs of (2.9) and (2.10), which convey a more visceral understanding of these formulas, are, so far as we know, new.

Bijective proofs of Theorem 2.1 and Corollary 2.1.1.

As above, we represent a lattice path λ ∈ Λ(n) by a word t_{1}t_{2} ⋯ t_{n} in the alphabet {1, 2}, recalling that α(λ) is equal to the number of inversions in this word, which we also denote by α(λ). By (2.5), formula (2.10) asserts that

|Λ_{0}(n)| − |Λ_{1}(n)| = 2^{⌈n/2⌉}.  (2.11)

Our strategy for proving (2.11) is to identify a subset Λ_{0}^{+}(n) of Λ_{0}(n) having cardinality 2^{⌈n/2⌉}, along with an α-parity changing involution of Λ(n) − Λ_{0}^{+}(n). Let Λ_{0}^{+}(n) comprise those words λ = t_{1}t_{2} ⋯ t_{n} such that for i = 1, 2, …, ⌊n/2⌋,

t_{2i−1}t_{2i} = 11 or 22.  (2.12)

Clearly, Λ_{0}^{+}(n) ⊆ Λ_{0}(n) and |Λ_{0}^{+}(n)| = 2^{⌈n/2⌉}. If λ ∈ Λ(n) − Λ_{0}^{+}(n), let i_{0} be the smallest index for which (2.12) fails to hold and let λ′ be the result of switching t_{2i_{0}−1} and t_{2i_{0}} in λ. The map λ ↦ λ′ is clearly an α-parity changing involution of Λ(n) − Λ_{0}^{+}(n), which proves (2.11) and hence (2.10).

By (2.4), formula (2.9) asserts that

|Λ_{0}(n, k)| − |Λ_{1}(n, k)| = \begin{cases}0, & if n is even and k is odd; \\ \binom{⌊n/2⌋}{⌊k/2⌋}, & otherwise. \end{cases}  (2.13)

To show (2.13), let Λ_{0}^{+}(n, k) = Λ_{0}^{+}(n) ∩ Λ(n, k). The cardinality of Λ_{0}^{+}(n, k) is given by the right-hand side of (2.13), and the restriction of the above map to Λ(n, k) − Λ_{0}^{+}(n, k) is again an involution and inherits the parity changing property. This proves (2.13), and hence (2.9). □

In tabulating the numbers \binom{n}{k}_{−1} it is of course more efficient to use the recurrence

\binom{n}{k}_{−1} = \binom{n − 1}{k − 1}_{−1} + (−1)^{k}\binom{n − 1}{k}_{−1},  (2.14)

representing the case q = −1 of (2.6).

Comparison of (2.9) with an evaluation of \binom{n}{k}_{−1} based on (2.8) yields a pair of interesting identities.

Corollary 2.1.2. If 1 ⩽ m ⩽ ⌊n/2⌋, then

∑_{j=0}^{n−2m}(−1)^{j}\binom{m + j − 1}{m − 1}\binom{n − m − j}{m} = \binom{⌊n/2⌋}{m},  (2.15)

and if 0 ⩽ m ⩽ ⌊(n − 1)/2⌋, then

∑_{j=0}^{n−2m−1}(−1)^{j}\binom{m + j}{m}\binom{n − m − j − 1}{m} = \begin{cases}0, & if n is even; \\ \binom{⌊n/2⌋}{m}, & if n is odd. \end{cases}  (2.16)

Proof. Setting q = −1 and k = 2m in (2.8) yields

\begin{aligned}\binom{n}{2m}_{−1} & = ∑_{d_{0}+d_{1}+···+d_{2m}=n−2m}(−1)^{d_{1}+d_{3}+···+d_{2m−1}} \\ & =_{(j=d_{1}+d_{3}+···+d_{2m−1})} ∑_{j=0}^{n−2m}(−1)^{j}\binom{m + j − 1}{m − 1}\binom{n − m − j}{m}, \end{aligned}

which implies (2.15) by (2.9), upon independently choosing the d_{i}’s of even index, which sum to n − 2m − j. Setting k = 2m + 1 yields

\begin{aligned}\binom{n}{2m + 1}_{−1} & = ∑_{d_{0}+d_{1}+···+d_{2m+1}=n−2m−1}(−1)^{d_{1}+d_{3}+···+d_{2m+1}} \\ & =_{(j=d_{1}+d_{3}+···+d_{2m+1})} ∑_{j=0}^{n−2m−1}(−1)^{j}\binom{m + j}{m}\binom{n − m − j − 1}{m}, \end{aligned}

which implies (2.16) by (2.9).

Corollary 2.1.1 above can also be proved by induction from the case q = −1 of the following recurrence for G_{q}(n):

Theorem 2.2. For all n ∈ ℙ,

G_{q}(n + 1) = 2G_{q}(n) + (q^{n} − 1)G_{q}(n − 1),  (2.17)

where G_{q}(0) = 1 and G_{q}(1) = 2.

Proof. Let a(n, i) := |{λ ∈ Λ(n) : α(λ) = i}|, where n ∈ ℕ and a(n, i) := 0 if i < 0. Showing (2.17) is equivalent to showing that

\begin{aligned}a(n + 1, i) & = 2a(n, i) + a(n − 1, i − n) − a(n − 1, i) \\ & = a(n, i) + (a(n, i) − a(n − 1, i)) + a(n − 1, i − n) \end{aligned}  (2.18)

for all i ∈ ℕ. As above, we represent a lattice path λ ∈ Λ(n + 1) by a word t_{1}t_{2} ⋯ t_{n+1} in the alphabet {1, 2}, recalling that α(λ) is equal to the number of inversions in this word.

The term a(n + 1, i) thus counts all words of length n + 1 with i inversions. The term a(n, i) counts the subclass of such words for which t_{n+1} = 2. The term a(n, i) − a(n − 1, i) counts the subclass of such words for which t_{1} = t_{n+1} = 1. For deletion of t_{1} is a bijection from this subclass to the class of words u_{1}u_{2} ⋯ u_{n} with i inversions and u_{n} = 1, and there are clearly a(n, i) − a(n − 1, i) words of the latter type. Finally, the term a(n − 1, i − n) counts the subclass of words for which t_{1} = 2 and t_{n+1} = 1. For deletion of t_{1} and t_{n+1} is a bijection from this subclass to the class of words v_{1}v_{2} ⋯ v_{n−1} with i − n inversions (both classes being empty if i < n).

The above proof provides an elementary alternative to Goldman and Rota’s proof of (2.17) using the method of linear functionals [4].

3 Two Statistics on Laguerre Configurations

Let L(n, k) denote the set of distributions of n balls, labeled 1, 2, …, n, among k unlabeled, contents-ordered boxes, with no box left empty. Garsia and Remmel [3] term such distributions Laguerre configurations. If L(n, k) := |L(n, k)|, then L(n, 0) = δ_{n,0}, ∀ n ∈ ℕ, L(n, k) = 0 if 0 ⩽ n < k, and

L(n, k) = \frac{n!}{k!}\binom{n − 1}{k − 1},  1 ⩽ k ⩽ n.  (3.1)

The numbers L(n, k) are called Lah numbers, after Ivo Lah [6], who introduced them as the connection constants in the polynomial identities

x(x + 1) ⋯ (x + n − 1) = ∑_{k=0}^{n} L(n, k)x(x − 1) ⋯ (x − k + 1),  ∀n ∈ ℕ.  (3.2)

From (3.1) it follows that

∑_{n⩾k}L(n, k)\frac{x^{n}}{n!} = \frac{1}{k!} (\frac{x}{1 − x})^{k} ,  ∀k ∈ ℕ.  (3.3)

The Lah numbers also satisfy the recurrence relations

L(n, k) = L(n − 1, k − 1) + (n + k − 1)L(n − 1, k),  ∀n, k ∈ ℙ,  (3.4)

and

L(n, k) = \frac{n}{k}L(n − 1, k − 1) + nL(n − 1, k),  ∀n, k ∈ ℙ.  (3.5)

The set L(n) := ⋃_{k} L(n, k) comprises all distributions of n balls, labeled 1, 2, …, n, among n unlabeled, contents-ordered boxes. If L(n) := |L(n)|, it follows from (3.3) that

∑_{n⩾0}L(n)\frac{x^{n}}{n!} = e^{x/(1−x)},  (3.6)

and differentiating (3.6) yields [7, p. 171], [9, A000262]

Theorem 3.1. For all n ∈ ℙ,

L(n + 1) = (2n + 1)L(n) − (n^{2} − n)L(n − 1),  (3.7)

where L(0) = L(1) = 1.

Combinatorial proof of Theorem 3.1.

We’ll argue that the cardinality of L(n + 1) is given by the right-hand side of (3.7) when n ⩾ 1. Let us represent members of L(m) by partitions of [m] in which the elements of each block are ordered. As there are clearly L(n) members of L(n + 1) in which the singleton {n + 1} occurs, we need only show that the members of L(n + 1) in which the singleton {n + 1} doesn’t occur number 2nL(n) − n(n − 1)L(n − 1).

Suppose λ ∈ L(n) and consider the 2n members of L(n + 1) gotten from λ by inserting n + 1 either directly before or directly after an element of [n] within λ. Then 2nL(n) double counts members of L(n + 1) for which n + 1 is neither first nor last in its block and counts once all other members of L(n + 1) for which n + 1 goes in a block with at least one element of [n]. But there are n(n−1)L(n−1) configurations of the former type as seen upon choosing an element j of [n] to directly follow n + 1 and then inserting n + 1, j directly after an element of [n]−{j} in a Laguerre configuration of the set [n]−{j}. □

In what follows, we consider two statistics on Laguerre configurations.

3.1 The Statistic i

Given a distribution δ ∈ L(n, k), let us represent the ordered contents of each box by a word in [n], and then arrange these words in a sequence W_{1}, …, W_{k} in decreasing order of their least elements. Replacing the commas in this sequence by zeros and counting inversions in the resulting single word yields the value i(δ), i.e.,

i(δ) = the number of inversions in W_{1}0W_{2}0 ⋯ 0W_{k−1}0W_{k}.  (3.8)

As an illustration, for the distribution δ ∈ L(9, 4) given by

\underline{3, 4, 9} \underline{8, 1} \underline{2, 6} \underline{7, 5} ,  (3.9)

we have i(δ) = 35, the number of inversions in the word 750349026081.

The statistic i is due to Garsia and Remmel [3], who show that the generating function

L_{q}(n, k) := ∑_{δ∈L(n,k)} q^{i(δ)} = q^{k(k−1)} \frac{n!_{q}}{k!_{q}} \binom{n − 1}{k − 1}_{q}, 1 ⩽ k ⩽ n.  (3.10)

Generalizing (3.4), the q-Lah number L_{q}(n, k) satisfies the recurrence

L_{q}(n, k) = q^{n+k−2}L_{q}(n − 1, k − 1) + (n + k − 1)_{q}L_{q}(n − 1, k), ∀n, k ∈ ℙ.  (3.11)

Garsia and Remmel also show that

x_{q}(x + 1)_{q} ⋯ (x + n − 1)_{q} = ∑_{k=1}^{n} L_{q}(n, k)x_{q}(x − 1)_{q} ⋯ (x − k + 1)_{q},  (3.12)

where x_{q} := (q^{x} − 1)/ (q − 1). It seems not to have been noted that (3.12) is equivalent to

x(qx + 1_{q}) ⋯ (q^{n−1}x + (n − 1)_{q}) = ∑_{k=1}^{n} L_{q}(n, k)x (\frac{x − 1_{q}}{q} ) ⋯ (\frac{x − (k − 1)_{q}}{q^{k−1}} ) , (3.13)

which generalizes (3.2).

Theorem 3.2. If 1 ≤ k ≤ n, then

L_{−1}(n, k) = δ_{n,k}.  (3.14)

Proof. Formula (3.14) is an immediate consequence of (3.10) and (2.9), upon considering even and odd cases for n, as j_{−1} = 0 if j is even (cf. [8]). For a bijective proof of (3.14), first note that L_{−1}(n, k) = |L_{0}(n, k)| − |L_{1}(n, k)|, where L_{r}(n, k) := {δ ∈ L(n, k) : i(δ) ≡ r (mod 2)}. Now L(n, n) consists of a single distribution δ, with i(δ) = n(n − 1) = the number of inversions in n0(n − 1)0 ⋯ 0201, whence |L_{0}(n, n)| = 1 and |L_{1}(n, n)| = 0. If 1 ⩽ k < n and δ ∈ L(n, k) gives rise to the sequence W_{1}, …, W_{k}, then locate the leftmost word W_{i} containing at least two letters and interchange its first two letters. The resulting map is a parity changing involution of L(n, k), whence |L_{0}(n, k)| − |L_{1}(n, k)| = 0.

Remark. Note that L(n, 1) = S_{n}, the set of permutations of [n], and so (3.10) is a generalization of the well known result that

∑_{π∈S_{n}} q^{i(π)} = n!_{q},  (3.15)

and (3.14) a generalization of the fact that among the permutations of [n], if n ⩾ 2, there are as many with an odd number of inversions as there are with an even number of inversions.

3.2 The Statistic w̃

As above, given δ ∈ L(n, k), we represent the ordered contents of each box by a word in [n]. Now, however, we arrange these words in a sequence W_{1}, …, W_{k} in increasing order of their initial elements, defining w̃(δ) by the formula

w̃(δ) = ∑_{i=1}^{k}(i − 1)(|W_{i}| − 1),  (3.16)

where |W_{i}| denotes the length of the word W_{i}. As an illustration, for the distribution δ ∈ L(9, 4) given above by (3.9), we have W_{1}, W_{2}, W_{3}, W_{4} = 26, 349, 75, 81 and w̃(δ) = 7. The statistic w̃ is an analogue of a now well known partition statistic first introduced by Carlitz [2] (see also [11]).

Theorem 3.3. The generating function

L̃_{q}(n, k) := ∑_{δ∈L(n,k)} q^{w̃(δ)} = \frac{n!}{k!}\binom{n − 1}{k − 1}_{q},  1 ⩽ k ⩽ n.  (3.17)

Proof. In running through δ ∈ L(n, k), we are running through all sequences of words W_{1}, …, W_{k} whose initial elements form an increasing sequence, and such that |W_{i}| = n_{i}, with ∑ n_{i} = n. For fixed such n_{1}, …, n_{k}, there are \binom{n}{k}(n − k)! such sequences, \binom{n}{k} being the number of ways to choose and place the initial elements, and (n − k)! the number of ways to place the remaining elements. By (3.16) and (2.8), it follows that

\begin{aligned}∑_{δ∈L(n,k)} q^{w̃(δ)} & = \binom{n}{k}(n − k)! ∑_{\begin{matrix}n_{1}+···+n_{k}=n \\ n_{i}∈ℙ \end{matrix}}q^{0(n_{1}−1)+1(n_{2}−1)+···+(k−1)(n_{k}−1)} \\ & = \frac{n!}{k!}\binom{n − 1}{k − 1}_{q}. \end{aligned}

From (3.17) and (2.7), it follows that

∑_{n⩾k} L̃_{q}(n, k)\frac{x^{n}}{n!} = \frac{1}{k!} \frac{x^{k}}{∏_{0⩽j⩽k−1}(1 − q^{j}x)}, ∀k ∈ ℕ,  (3.18)

which generalizes (3.3). The q-Lah number L̃_{q}(n, k) also satisfies the recurrence

L̃_{q}(n, k) = \frac{n}{k}L̃_{q}(n − 1, k − 1) + nq^{k−1}L̃_{q}(n − 1, k),  (3.19)

which generalizes (3.5).

Theorem 3.4. If 1 ≤ k ≤ n, then

L̃_{−1}(n, k) = \begin{cases}0, & if n is odd and k is even; \\ \frac{n!}{k!} \binom{⌊(n−1)/2⌋}{⌊(k−1)/2⌋}, & otherwise. \end{cases}  (3.20)

Proof. This follows immediately from (3.17) and (2.9), but the following bijective proof yields a deeper insight into this result: with L_{r}(n, k) := {δ ∈ L(n, k) : w̃(δ) ≡ r (mod 2)}, we have L̃_{−1}(n, k) = |L_{0}(n, k)| − |L_{1}(n, k)|. To prove (3.20) it thus suffices to identify a subset L_{0}^{+}(n, k) of L_{0}(n, k) such that

|L_{0}^{+}(n, k)| = \begin{cases}0, & if n is odd and k is even; \\ \frac{n!}{k!} \binom{⌊(n−1)/2⌋}{⌊(k−1)/2⌋}, & otherwise, \end{cases}  (3.21)

along with a parity changing involution of L(n, k) − L_{0}^{+}(n, k).

The set L_{0}^{+}(n, k) consists of those distributions whose associated sequences W_{1}, W_{2}, …, W_{k} satisfy

|W_{2i−1}| is odd and |W_{2i}| = 1, 1 ⩽ i ⩽ ⌊k/2⌋.  (3.22)

Clearly, L_{0}^{+}(n, k) = ∅ if n is odd and k is even. In the remaining cases, the factor n!/k! arises as the product \binom{n}{k}(n − k)!, just as it does in the proof of Theorem 3.3, and

\binom{⌊(n − 1)/2⌋}{⌊(k − 1)/2⌋} = |\{(n_{1}, …, n_{k}) : ∑ n_{i} = n, n_{2i−1} is odd,

and n_{2i} = 1, 1 ⩽ i ⩽ ⌊k/2⌋}| , (3.23)

upon halving compositions of an integer whose parts are all even.

Suppose now that δ ∈ L(n, k) − L_{0}^{+}(n, k) is associated with the sequence W_{1}, …, W_{k} and that i_{0} is the smallest index for which (3.22) fails to hold. If |W_{2i_{0}−1}| is even, take the last member of W_{2i_{0}−1} and place it at the end of W_{2i_{0}}. If |W_{2i_{0}−1}| is odd, whence |W_{2i_{0}}| ⩾ 2, take the last member of W_{2i_{0}} and place it at the end of W_{2i_{0}−1}. The resulting map is a parity changing involution of L(n, k) − L_{0}^{+}(n, k).

In tabulating the numbers L̃_{−1}(n, k) it is of course more efficient to use the recurrence

L̃_{−1}(n, k) = \frac{n}{k}L̃_{−1}(n − 1, k − 1) + (−1)^{k−1}nL̃_{−1}(n − 1, k),  (3.24)

representing the case q = −1 of (3.19). This yields the following table for 0 ⩽ k ⩽ n ⩽ 8:

Table 3.1: The numbers L̃_{−1}(n, k) for 0 ⩽ k ⩽ n ⩽ 8.
k = 0  1  2  3  4  5  6  7  8
n = 0  1
1  0  1
2  0  2  1
3  0  6  0  1
4  0  24  12  4  1
5  0 120  0  40  0  1
6  0 720 360 240  60  6  1
7  0 5040  0 2520  0 126  0  1
8  0 40320 20160 20160 5040 1008 168  8  1

The row sums of Table 3.1 correspond to the quantities L̃_{−1}(n) [9, A089656], where

L̃_{q}(n) := ∑_{δ∈L(n)} q^{w̃(δ)} = ∑_{k} L̃_{q}(n, k).  (3.25)

We have been unable to find a simple closed form or recurrence for L̃_{−1}(n). However, using the case q = −1 of formula (3.18), it is straightforward to show that

∑_{n⩾0} L̃_{−1}(n)\frac{x^{n}}{n!} = cosh \frac{x}{\sqrt{1 − x^{2}}} + \frac{\sqrt{1 − x^{2}}}{1 − x} sinh \frac{x}{\sqrt{1 − x^{2}}} .  (3.26)

The values of L̃_{−1}(n) for 0 ⩽ n ⩽ 10 are as follows: 1, 1, 3, 7, 41, 161, 1387, 7687, 86865, 623233, 8682131.

4 Some Concluding Remarks

Reductions from q-binomial coefficients to ordinary binomial coefficients similar to those seen when q = −1 occur with higher roots of unity. For example, substituting q = ρ = \frac{−1+\sqrt{3}i}{2}, a third root of unity, and q = i, a fourth root of unity, into (2.7) and considering cases for k mod 3 and mod 4 yields

Theorem 4.1. If 0 ≤ k ≤ n, then

\binom{n}{k}_{ρ} = \begin{cases}\binom{⌊n/3⌋}{⌊k/3⌋}, & if n ≡ k (mod 3) or k ≡ 0 (mod 3); \\ − ρ^{2}\binom{⌊n/3⌋}{⌊k/3⌋}, & if n ≡ 2 (mod 3) and k ≡ 1 (mod 3); \\ 0, & otherwise. \end{cases}  (4.1)

and

Theorem 4.2. If 0 ≤ k ≤ n, then

\binom{n}{k}_{i} = \begin{cases}\binom{⌊n/4⌋}{⌊k/4⌋}, & if n ≡ k (mod 4) or k ≡ 0 (mod 4); \\ i\binom{⌊n/4⌋}{⌊k/4⌋}, & if n ≡ 3 (mod 4) and k ≡ 1, 2 (mod 4); \\ (1 + i)\binom{⌊n/4⌋}{⌊k/4⌋}, & if n ≡ 2 (mod 4) and k ≡ 1 (mod 4); \\ 0, & otherwise. \end{cases}  (4.2)

Bijective proof of Theorem 4.1.

We modify the combinatorial argument used to establish (2.9). Instead of pairing members of Λ(n, k) of opposite α-parity, we partition a portion of Λ(n, k) into tripletons each of whose members have different α values mod 3. Each such tripleton contributes 0 towards the sum \binom{n}{k}_{ρ} = ∑_{λ∈Λ(n,k)} ρ^{α(λ)} since 1 + ρ + ρ^{2} = 0.

As before, we represent lattice paths by words in {1, 2}. Let Λ′(n, k) consist of those words λ = t_{1}t_{2} ⋯ t_{n} in Λ(n, k) satisfying

t_{3i−2} = t_{3i−1} = t_{3i},  1 ⩽ i ⩽ ⌊n/3⌋.  (4.3)

In all cases, the right-hand side of (4.1) above gives the net contribution of Λ′(n, k) towards \binom{n}{k}_{ρ}; note that members of Λ′(n, k) may end in either 12 or 21 if n ≡ 2 (mod 3) and k ≡ 1 (mod 3), hence the 1 + ρ = −ρ^{2} factor in this case.

Suppose now that λ = t_{1}t_{2} ⋯ t_{n} ∈ Λ(n, k)−Λ′(n, k), with i_{0} the smallest i for which (4.3) fails to hold. Group the three members of Λ(n, k) − Λ′(n, k) gotten by circularly permuting t_{3i_{0}−2}, t_{3i_{0}−1}, and t_{3i_{0}} within λ = t_{1}t_{2} ⋯ t_{n}, leaving the rest of λ undisturbed. Note that these three members of Λ(n, k) − Λ′(n, k) have different α values mod 3, which establishes (4.1). □

A similar proof, which involves partitioning members of Λ(n, k) according to their inv values mod 4, applies to (4.2), the details of which we leave as an exercise for interested readers.

If m ∈ ℙ and ω = e^{2πi/m}, a primitive m^{th} root of unity, examining (2.7) when q = ω reveals that \binom{n}{k}_{ω} is of the form β\binom{⌊n/m⌋}{⌊k/m⌋} for all n and k, where β is some complex number depending on the values of n and k mod m. Even though β can in general be expressed in terms of symmetric functions of certain m^{th} roots of unity, there does not appear to be a simple closed form for \binom{n}{k}_{ω} which generalizes (2.9), (4.1), and (4.2). Some particular cases are easily ascertained. For example, when m divides n, we have from (2.7),

\binom{n}{k}_{ω} = \begin{cases}\binom{n/m}{k/m}, & if m divides k; \\ 0, & otherwise. \end{cases}  (4.4)

When m is a prime, the combinatorial argument used for (4.1) readily generalizes to (4.4).

References

[1] G. Berman and K. Fryer, Introduction to Combinatorics, Academic Press, 1972.

[2] L. Carlitz, Combinatorial analysis notes, Duke University (1968).

[3] A. Garsia and J. Remmel, A combinatorial interpretation of q-derangement and q-Laguerre numbers, Europ. J. Combinatorics 1 (1980), 47–59.

[4] J. Goldman and G.-C. Rota, The number of subspaces of a vector space, in: W. Tutte, ed., Recent Progress in Combinatorics, Academic Press (1969), 75–83.

[5] D. Knuth, Two notes on notation, Amer. Math. Monthly 99 (1992), 403-422.

[6] I. Lah, Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik, Mitteilungsbl. Math. Statist. 7 (1955), 203–212.

[7] T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in: Proc. Symp. Pure Math., Vol. 19, American Mathematical Society (1971), 167–176.

[8] M. Schork, Fermionic relatives of Stirling and Lah numbers, J. Phys. A: Math. Gen. 36 (2003), 10391–10398.

[9] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences.

[10] R. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, 1986.

[11] C. Wagner, Generalized Stirling and Lah numbers, Discrete Math. 160 (1996), 199–218.

2000 Mathematics Subject Classification: Primary 05A99; Secondary 05A10 . Keywords: Laguerre configuration, Lah numbers, lattice paths, q-binomial coefficient.

(Concerned with sequences \underline{A000262} and \underline{A089656}.)

Received July 1 2005; revised version received October 18 2005. Published in Journal of Integer Sequences, October 20 2005.

Return to Journal of Integer Sequences home page.