# Negative *q*-Stirling numbers

Yue Cai, Margaret Readdy

► To cite this version:

Yue Cai, Margaret Readdy. Negative *q*-Stirling numbers. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.583-94, 10.46298/dmtcs.2503. hal-01337791

HAL Id: hal-01337791

https://hal.science/hal-01337791

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Negative *q*-Stirling numbers

Yue Cai¹† and Margaret Readdy¹‡

¹University of Kentucky, Department of Mathematics, Lexington, KY 40506 USA

**Abstract.** The notion of the negative *q*-binomial was recently introduced by Fu, Reiner, Stanton and Thiem. Mirroring the negative *q*-binomial, we show the classical *q*-Stirling numbers of the second kind can be expressed as a pair of statistics on a subset of restricted growth words. The resulting expressions are polynomials in *q* and (*q*+1). We extend this enumerative result via a decomposition of the Stirling poset, as well as a homological version of Stembridge's *q* = -1 phenomenon. A parallel enumerative, poset theoretic and homological study for the *q*-Stirling numbers of the first kind is done beginning with de Médicis and Leroux's rook placement formulation. Letting *t* = *q* + 1 we give a bijective combinatorial argument to the Viennot showing the (*q*, *t*)-Stirling numbers of the first and second kind are orthogonal.

**Résumé.** La notion de la *q*-binomial négative était introduit par Fu, Reiner, Stanton et Thiem. Réfléchissant la *q*-binomial négative, nous démontrons que les classiques *q*-nombres de Stirling de deuxième espèce peuvent exprimés comme une paire des statistiques sur un sous-ensemble des mots qui a de croissance restreinte. Les expressions résultants sont les polynômes en *q* et 1+*q*. Nous étendons cet résultat énumérative via d'une décomposition de la poset de Stirling, ainsi que d'une version homologique du *q* = -1 phénomène de Stembridge. Un parallèle énumérative, poset théoretique et étude homologique des *q*-nombres de Stirling de première espèce se fait en commençant par le formulation du placement des tours par suite des auteurs de Médicis et Leroux. On laisse *t* = 1 + *q* ce que donner les arguments combinatoires et bijectifs à la Viennot que démontrent que les (*q*, *t*)-nombres de Stirling de première et deuxième espèces sont orthogonaux.

**Keywords:** *q*-analogues, discrete Morse Theory, poset decomposition, algebraic complex, homology, orthogonality.

## 1 Introduction

The idea of *q*-analogues can be traced back to Euler in the 1700's who was studying *q*-series, especially specializations of theta functions. The Gaussian polynomial is given by $\begin{bmatrix} n \\ k \end{bmatrix}_q = \frac{[n]_q!}{[k]_q![n-k]_q!}$, where $[n]_q = 1 + q + \cdots + q^{n-1}$ and $[n]_q! = [1]_q \cdot [2]_q \cdots [n]_q$. A combinatorial interpretation due to MacMahon in 1916 [14, Page 315] is $\sum_{\pi \in \mathfrak{S}(0^{n-k}, 1^k)} q^{\mathrm{inv}(\pi)} = \begin{bmatrix} n \\ k \end{bmatrix}_q$. Here $\mathfrak{S}(0^{n-k}, 1^k)$ denotes the number of 0-1 bit strings consisting of $n-k$ zeroes and $k$ ones, and for $\pi = \pi_1 \cdots \pi_n \in \mathfrak{S}(0^{n-k}, 1^k)$ the number of inversions is $\mathrm{inv}(\pi) = |\{(i, j) : i < j \text{ and } \pi_i > \pi_j\}|$. The inversion statistic goes back to work of Cramer

<footnote>†Email: yue.cai@uky.edu. Partially supported by National Security Agency grant H98230-13-1-0280.</footnote>

<footnote>‡Email: readdy@ms.uky.edu. The second author would like to thank Princeton University where this research was completed. This work was partially supported by a grant from the Simons Foundation (#206001 to Margaret Readdy).</footnote>
(1750), Bézout (1764) and Laplace (1772). See the discussion in [17, Page 92]. Netto enumerated the elements of the symmetric group by the inversion statistic in 1901 [17, Chapter 4, Sections 54, 57], and in 1916 MacMahon [14, Page 318] gave the q-factorial expansion $\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)} = [n]_q!$.

The notion of the *negative q-binomial* has been recently introduced by Fu, Reiner, Stanton and Thiem [5]. It is defined by substituting $-q$ for $q$ in the Gaussian coefficient and adjusting the sign: $\begin{bmatrix} n \\ k \end{bmatrix}'_q = (-1)^{k(n-k)} \begin{bmatrix} n \\ k \end{bmatrix}_{-q}$. The negative q-binomial enjoys properties similar to that of the q-binomial: (i) it can be expressed as a generalized inversion number of a *subset* $\Omega(n, k)'$ of 0-1 bit strings in $\mathfrak{S}(0^{n-k}, 1^k)$:

$$ \begin{bmatrix} n \\ k \end{bmatrix}'_q = \sum_{\omega \in \Omega(n,k)'} q^{a(\omega)} \cdot (q-1)^{p(\omega)}, \qquad (1.1) $$

for statistics $a(\omega)$ and $p(\omega)$ [5, Theorem 1], (ii) it counts a certain subset of the $k$-dimensional subspaces of $\mathbb{F}_q^n$ [5, Section 6.2], (iii) it reveals a representation theory connection with unitary subspaces and a two-variable version exhibits a cyclic sieving phenomenon [5, Sections 4, 5].

An important consequence of (1.1) is the classical Gaussian polynomial can be expressed as sum over a *subset* of 0-1 bit strings in terms of powers of $q$ and $1+q$ using the same statistics:

$$ \begin{bmatrix} n \\ k \end{bmatrix}_q = \sum_{\omega \in \Omega(n,k)'} q^{a(\omega)} \cdot (1+q)^{p(\omega)}. \qquad (1.2) $$

It is from this result that we springboard our work. More precisely,

**Goal 1.1** Given a q-analogue

$$ f(q) = \sum_{w \in S} q^{\sigma(w)}, $$

for some statistic $\sigma(\cdot)$, find a subset $T \subseteq S$ and statistics $A(\cdot)$ and $B(\cdot)$ so that the q-analogue may be expressed as

$$ f(q) = \sum_{w \in T} q^{A(w)} \cdot (1+q)^{B(w)}. $$

The overall goal is not only to discover more compact encodings of classical q-analogues, but to also understand them via enumerative, poset theoretic and topological viewpoints. In this paper we do exactly this for the q-Stirling numbers of the first and second kinds.

## 2 RG-words

Recall a *set partition* on the $n$ elements $\{1, 2, \dots, n\}$ is a decomposition of this set into mutually disjoint nonempty sets called blocks. Unless otherwise indicated, throughout all set partitions will be written in standard form, that is, a partition into $k$ blocks will be denoted by $\pi = B_1/B_2/\cdots/B_k$, where the blocks are ordered so that $\min(B_1) < \cdots < \min(B_k)$. We denote the set of all partitions of $\{1, \dots, n\}$ by $\Pi_n$.

Given a partition $\pi \in \Pi_n$, we encode it using a *restricted growth word* $w(\pi) = w_1 \cdots w_n$, where $w_i = j$ if the element $i$ occurs in the $j$th block $B_j$ of $\pi$. For example, the partition $\pi = 14/236/57$ has RG-word $w = w(\pi) = 1221323$. Restricted growth words are also known as restricted growth functions. They have been studied by Hutchinson [9] and Milne [15, 16].

Two facts about RG-words follow immediately from using the standard form for set partitions.
**Proposition 2.1** The following properties are satisfied by RG-words:

1. Any RG-word begins with the element 1.

2. For an RG-word $\omega$ let $\epsilon(j)$ be the smallest index such that $\omega_{\epsilon(j)} = j$. Then $\epsilon(1) < \epsilon(2) < \dots$.

The q-Stirling numbers of the second kind are defined by

$$S_q[n, k] = S_q[n-1, k-1] + [k]_q \cdot S_q[n-1, k], \text{ for } 1 \le k \le n, \qquad (2.1)$$

with boundary conditions $S_q[n, 0] = \delta_{n,0}$ and $S_q[0, k] = \delta_{0,k}$, where $\delta_{i,j}$ is the usual Kronecker delta function. Setting $q = 1$ gives the familiar Stirling number of the second kind $S(n, k)$ which enumerates the number of partitions $\pi \in \Pi_n$ with exactly $k$ blocks. There is a long history of studying set partition statistics [6, 13, 19] and q-Stirling numbers [1, 3, 7, 16, 25].

We begin by presenting a new statistic on RG-words which generate the q-Stirling numbers of the second kind. Let $\mathcal{R}(n, k)$ denote the set of all RG-words of length $n$ with maximum letter $k$. For $w \in \mathcal{R}(n, k)$, let $m_i = \max(w_1, \dots, w_i)$. Form the weight $\text{wt}(w) = \prod_{i=1}^n \text{wt}_i(w)$ where $\text{wt}_1(w) = 1$ and for $2 \le i \le n$, let

$$\text{wt}_i(w) = \begin{cases} q^{w_i-1} & \text{if } m_{i-1} \ge w_i, \\ 1 & \text{if } m_{i-1} < w_i. \end{cases} \qquad (2.2)$$

For example, $\text{wt}(1221323) = 1 \cdot 1 \cdot q^1 \cdot q^0 \cdot 1 \cdot q^1 \cdot q^2 = q^4$. In terms of set partitions, the weight of $\pi = B_1/B_2/\dots/B_k$ is $\text{wt}(\pi) = \prod_{j=1}^n q^{(j-1)\cdot(|B_j|-1)}$.

**Lemma 2.2** The q-Stirling number of the second kind is given by

$$S_q[n, k] = \sum_{w \in \mathcal{R}(n, k)} \text{wt}(w).$$

# 3 Allowable RG-words

Mirroring the negative q-binomial, in this section we define a subset of RG-words and two statistics $A(\cdot)$ and $B(\cdot)$ which generate the classical q-Stirling number of the second kind as a polynomial in $q$ and $1+q$. We will see in Sections 4 through 6 that this has poset and topological implications.

**Definition 3.1** An RG-word $w \in \mathcal{R}(n, k)$ is allowable if every even entry appears exactly once. Denote by $A(n, k)$ the set of all allowable RG-words in $\mathcal{R}(n, k)$.

Another way to state that $w \in \mathcal{R}(n, k)$ is an allowable RG-word is that it is an initial segment of the infinite word $w = u_1 \cdot 2 \cdot u_3 \cdot 4 \cdot u_5 \dots$, where $u_{2i-1}$ is a word on the alphabet of odd integers $\{1, 3, \dots, 2i-1\}$. In terms of set partitions, an RG-word is allowable if in the corresponding set partition every even indexed block is a singleton block.

For an RG-word $w = w_1 \cdots w_n$, let $m_i = \max(w_1, \dots, w_i)$. Define $\text{wt}'(w) = \prod_{i=1}^n \text{wt}'_i(w)$, where

$$\text{wt}'_i(w) = \begin{cases} q^{w_i-1} \cdot (1+q) & \text{if } m_{i-1} > w_i, \\ q^{w_i-1} & \text{if } m_{i-1} = w_i, \\ 1 & \text{if } m_{i-1} < w_i \text{ or } i=1. \end{cases} \qquad (3.1)$$
We decompose this weight statistic $wt'$ into two statistics on RG-words. Let

$$A_i(w) = \begin{cases} w_i - 1 & \text{if } m_{i-1} \ge w_i, \\ 0 & \text{if } m_{i-1} < w_i \text{ or } i = 1, \end{cases} \quad \text{and} \quad B_i(w) = \begin{cases} 1 & \text{if } m_{i-1} > w_i, \\ 0 & \text{otherwise.} \end{cases} \qquad (3.2)$$

Define

$$A(w) = \sum_{i=1}^{n} A_i(w) \quad \text{and} \quad B(w) = \sum_{i=1}^{n} B_i(w).$$

**Theorem 3.2** The q-Stirling numbers of the second kind can be expressed as a weighting over the set of allowable RG-words as follows:

$$S_q[n, k] = \sum_{w \in \mathcal{A}(n,k)} \mathrm{wt}'(w) = \sum_{w \in \mathcal{A}(n,k)} q^{A(w)} \cdot (1+q)^{B(w)}. \qquad (3.3)$$

**Proposition 3.3** The number of allowable words satisfies the recurrence

$$|\mathcal{A}(n, k)| = |\mathcal{A}(n-1, k-1)| + \lceil k/2 \rceil \cdot |\mathcal{A}(n-1, k)| \text{ for } n \ge 1 \text{ and } 1 \le k \le n,$$

with the boundary conditions $|\mathcal{A}(n, 0)| = \delta_{n,0}$.

Topological implications of Theorem 3.2 will be discussed in Section 6.

# 4 The Stirling poset of the second kind

In order to understand the q-Stirling numbers more deeply, we give a poset structure on $\mathcal{R}(n, k)$, which we call the Stirling poset of the second kind, denoted by $\Pi(n, k)$, as follows. For $v, w \in \mathcal{R}(n, k)$ let $v = v_1v_2 \cdots v_n \prec w$ if $w = v_1v_2 \cdots (v_i + 1) \cdots v_n$ for some index $i$. It is clear that if $v \prec w$ then $wt(w) = q \cdot wt(v)$, where the weight is as defined in (2.2). The Stirling poset of the second kind is graded by the degree of the weight $wt$. Thus the rank of the poset $\Pi(n, k)$ is $(n-k)(k-1)$ and its rank generating function is given by $S_q[n, k]$. For basic terminology regarding posets, we refer the reader to Stanley's treatise [21, Chapter 3]. See Figure 1 for an example of the Stirling poset of the second kind.

We next review the notion of a Morse matching [12]. This will enable us to find a natural decomposition of the Stirling poset of the second kind, and to later be able to draw homological conclusions. A partial matching on a poset $P$ is a matching on the underlying graph of the Hasse diagram of $P$, that is, a subset $M \subseteq P \times P$ satisfying (i) the ordered pair $(a, b) \in M$ implies $a \prec b$, and (ii) each element $a \in P$ belongs to at most one element in $M$. When $(a, b) \in M$, we write $u(a) = b$ and $d(b) = a$. A partial matching on $P$ is acyclic if there does not exist a cycle

$$a_1 \prec u(a_1) \succ a_2 \prec u(a_2) \succ \cdots \succ a_n \prec u(a_n) \succ a_1$$

with $n \ge 2$, and the elements $a_1, a_2, \dots, a_n$ distinct.

We define a matching $M$ on the Stirling poset $\Pi(n, k)$ in the following manner. Let $w_i$ be the first entry in $w = w_1w_2 \cdots w_n \in \mathcal{R}(n, k)$ such that $w$ is weakly decreasing, that is, $w_1 \le w_2 \le \cdots \le w_{i-1} \ge w_i$ and where we require the inequality $w_{i-1} \ge w_i$ to be strict unless both $w_{i-1}$ and $w_i$ are even. We have two subcases. If $w_i$ is even then let $d(w) = w_1w_2 \cdots w_{i-1}(w_i - 1)w_{i+1} \cdots w_n$. Immediately we have $wt(d(w)) = q^{-1} \cdot wt(w)$. Otherwise, if $w_i$ is odd then let $u(w) = w_1w_2 \cdots w_{i-1}(w_i + 1)w_{i+1} \cdots w_n$ and we have $wt(u(w)) = q \cdot wt(w)$. If $w$ is an allowable word which is weakly increasing, then $w$ is unmatched in the poset. Again, we refer to Figure 1.
<figure><img src="image_2.png" /><figcaption>**Fig. 1:** The matching of the Stirling poset Π(5, 3). The matched elements are indicated by arrows. The rank generating function for this poset is $S_q[5, 3] = 6 + 8q + 7q^2 + 3q^3 + q^4$.</figcaption></figure>

**Lemma 4.1** For the partial matching M described on the poset Π(n, k) the unmatched words U(n, k) are of the form

$$w = \begin{cases} u_1 \cdot 2 \cdot u_3 \cdot 4 \cdot u_5 \cdot 6 \cdots u_{k-1} \cdot k & \text{for } k \text{ even,} \\ u_1 \cdot 2 \cdot u_3 \cdot 4 \cdot u_5 \cdot 6 \cdots k-1 \cdot u_k & \text{for } k \text{ odd,} \end{cases} \quad (4.1)$$

where $u_{2i-1} = (2i - 1)^{j_i}$, that is, $u_{2i-1}$ is a word consisting of $j_i \ge 1$ copies of the odd integer $2i - 1$.

As an example, the unmatched words in Π(5, 3) are 12333, 11233 and 11123, and their total weight is $1 + q^2 + q^4$. See Figure 1.

**Lemma 4.2** Let a and b be two distinct elements in the Stirling poset of the second kind Π(n, k) such that $a \prec u(a) \succ b \prec u(b)$. Then the element a is lexicographically larger than the element b.

From Lemma 4.2 we have the following result.

**Theorem 4.3** The matching M described for Π(n, k) is an acyclic matching, that is, it is a discrete Morse matching.

# 5 Decomposition of the Stirling poset

We next decompose the Stirling poset Π(n, k) into Boolean algebras indexed by the allowable words. This gives a poset explanation for the factorization of the q-Stirling number $S_q[n, k]$ in terms of powers of q and 1 + q. To state this decomposition, we need two definitions. For $w \in A(n, k)$ an allowable word let $\text{Inv}_r(w) = \{i : w_j > w_i \text{ for some } j < i\}$ be the set of all indices in w that contribute to the right-hand element of an inversion pair. For $i \in \text{Inv}_r(w)$ such an entry $w_i$ must be odd since in a given allowable word any entry occurring to the left of an even entry must be strictly less than it. Finally, for
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** The decomposition of the Stirling poset Π(5, 3) into Boolean algebras $B_0$, $B_1$ and $B_2$. Based on the ranks of the minimal elements in each Boolean algebra, one can read the weight of the poset as $S_q[5, 3] = 1 + 2(1 + q) + 3(1 + q)^2 + q^2 + 3q^2(1 + q) + q^4$.</figcaption></figure>

$w \in \mathcal{A}(n, k)$ let $\alpha(w)$ be the word formed by incrementing each of the entries indexed by the set $\mathrm{Inv}_r(w)$ by one. Additionally, for $w \in \mathcal{A}(n, k)$ and any $I \subseteq \mathrm{Inv}_r(w)$, the word formed by incrementing each of the entries indexed by the set $I$ by one are elements of $\mathcal{R}(n, k)$ since if $i \in \mathrm{Inv}_r(w)$ then there is an index $h < i$ with $w_h = w_i$. This follows from Proposition 2.1 part (ii).

**Theorem 5.1** *The Stirling poset of the second kind Π(n, k) can be decomposed as the disjoint union of Boolean intervals*

$$ \Pi(n, k) = \bigcup_{w \in \mathcal{A}(n,k)} [w, \alpha(w)]. $$

Furthermore, if an allowable word $w \in \mathcal{A}(n, k)$ has weight $\mathrm{wt}'(w) = q^i \cdot (1+q)^j$, then the rank of the element $w$ is $i$ and the interval $[w, \alpha(w)]$ is isomorphic to the Boolean algebra on $j$ elements.

See Figure 2 for an example of this decomposition.

# 6 Homological $q = -1$ phenomenon

Stembridge's $q = -1$ phenomenon [22, 23], and the more general cyclic sieving phenomenon of Reiner, Stanton and White [18] counts symmetry classes in combinatorial objects by evaluating their $q$-generating series at a primitive root of unity. Recently Hersh, Shareshian and Stanton [8] have given a homological interpretation of the $q = -1$ phenomenon by viewing it as an Euler characteristic computation on a chain complex supported by a poset. In the best scenario, the homology is concentrated in dimensions of the same parity and one can identify a homology basis. For further information about algebraic discrete Morse theory, see [10, 11, 20].
We will see the graded poset $\Pi(n, k)$ supports an algebraic complex $(C, \partial)$. The aforementioned matching for $\Pi(n, k)$ (Theorem 4.3) is a discrete Morse matching for this complex. Hence using standard discrete Morse theory [4], we can give a basis for the homology.

We now review the relevant background. We follow [8] here. See also [10, 20]. Let $P$ be a graded poset and $W_i$ denote the rank $i$ elements. We say the poset $P$ supports a chain complex $(C, \partial)$ of $\mathbb{F}$-vector spaces $C_i$ if each $C_i$ has basis indexed by the rank $i$ elements $W_i$ and $\partial_i : W_i \to W_{i-1}$ is a boundary map. Furthermore, for $x \in W_i$ and $y \in W_{i-1}$ the coefficient $\partial_{x,y}$ of $y$ in $\partial_i(x)$ is zero unless $y <_P x$.

For $w \in \Pi(n, k)$, let $E(w) = \{i : w_i$ is even and $w_j = w_i$ for some $j < i\}$ be the set of all indices of repeated even entries in the word $w$. Define the boundary map $\partial$ on the elements of $\Pi(n, k)$ by $\partial(w) = \sum_{j=1}^r (-1)^{j-1} \cdot w_1 \cdots w_{i_{j-1}} \cdot (w_{i_j} - 1) \cdot w_{i_j+1} \cdots w_n$, where $E(w) = \{i_1 < i_2 < \cdots < i_r\}$. For example, if $w = 122344$ then $E(122344) = \{3, 6\}$ and $\partial(122344) = 121344 - 122343$. With this definition of the boundary operator $\partial$, we have the following lemma.

**Lemma 6.1** The map $\partial$ is a boundary map on the algebraic complex $(C, \partial)$ with the poset $\Pi(n, k)$ as support.

**Lemma 6.2** The weighted generating function of the unmatched words $U(n, k)$ in $\Pi(n, k)$ is given by the $q^2$-binomial coefficient

$$ \sum_{u \in U(n,k)} \mathrm{wt}(u) = \left[ \begin{matrix} n-1-\lfloor \frac{k}{2} \rfloor \\ \lfloor \frac{k-1}{2} \rfloor \end{matrix} \right]_{q^2}. $$

Notice that when we substitute $q^2 = 1$, the $q^2$-binomial coefficient reduces to the number of unmatched words.

We will need a lemma due to Hersh, Shareshian and Stanton [8, Lemma 3.2]. This is part (ii) of the original statement of the lemma.

**Lemma 6.3 (Hersh–Shareshian–Stanton)** Let $P$ be a graded poset supporting an algebraic complex $(C, \partial)$ and assume $P$ has a Morse matching $M$ such that for all matched pair $(y, x)$ with $y < x$, one has $\partial_{x,y} \in \mathbb{F}^*$. If all unmatched poset elements occur in ranks of the same parity, then $\dim(H_i(C, d)) = |P^{\mathrm{unm}}|$, that is, the number of unmatched elements of rank $i$.

**Theorem 6.4** For the algebraic complex $(C, \partial)$ supported by the Stirling poset $\Pi(n, k)$, a basis for the integer homology is given by the increasing allowable RG-words in $\mathcal{A}(n, k)$. Furthermore, we have

$$ \sum_{i \ge 0} \dim(H_i(C, \partial; \mathbb{Z})) \cdot q^i = \left[ \begin{matrix} n-1-\lfloor \frac{k}{2} \rfloor \\ \lfloor \frac{k-1}{2} \rfloor \end{matrix} \right]_{q^2}. $$

# 7 $q$-Stirling numbers of the first kind: Combinatorial interpretation

The (unsigned) $q$-Stirling number of the first kind is defined by the recurrence formula

$$ c_q[n, k] = c_q[n-1, k-1] + [n-1]_q \cdot c_q[n-1, k], \qquad (7.1) $$

where $c_q[n, 0] = \delta_{n,0}$ and $[m]_q = 1 + q + \cdots + q^{m-1}$. When $q = 1$, the Stirling number of the first kind $c(n, k)$ enumerates permutations in the symmetric group $S_n$ having exactly $k$ disjoint cycles. A combinatorial way to express $q$-Stirling numbers of the first kind is via rook placements; see de Médicis and Leroux [2]. Throughout a staircase chessboard of length $m$ is a board with $m-i$ squares in the $i$th row for $i = 1, \dots, m-1$ and each row of squares is left-justified.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Computing the q-Stirling number of the first kind $c_q[4, 2]$ using $Q(4, 2)$.</figcaption></figure>

**Definition 7.1** Let $\mathcal{P}(m, n)$ be the set of all ways to place $n$ rooks onto a staircase chessboard of length $m$ so that no two rooks are in the same column. For any rook placement $T \in \mathcal{P}(m, n)$, denote by $s(T)$ the number of squares to the south of the rooks in $T$.

**Theorem 7.2 (de Médicis-Leroux)** The $q$-Stirling number of the first kind is given by

$$c_q[n, k] = \sum_{T \in \mathcal{P}(n, n-k)} q^{s(T)}.$$

We now define a subset $Q(n, n-k)$ of rook placements in $\mathcal{P}(n, n-k)$ so that the $q$-Stirling number of the first kind $c_q[n, k]$ can be expressed as a statistic on the subset involving $q$ and $1+q$.

**Definition 7.3** Given any staircase chessboard, assign it a chequered pattern such that every other antidiagonal strip of squares is shaded, beginning with the lowest antidiagonal. Let $Q(m, n) = \{T \in \mathcal{P}(m, n) : \text{all rooks are placed in shaded squares}\}$. For any $T \in Q(m, n)$, let $r(T)$ denote the number of rooks in $T$ that are not in the first row. For $T \in Q(m, n)$, define the weight to be $\text{wt}(T) = q^{s(T)} \cdot (1+q)^{r(T)}$.

**Theorem 7.4** The $q$-Stirling number of the first kind is given by

$$c_q[n, k] = \sum_{T \in Q(n, n-k)} \text{wt}(T) = \sum_{T \in Q(n, n-k)} q^{s(T)} \cdot (1+q)^{r(T)}.$$

See Figure 3 for the computation of $c_q[4, 2]$ using allowable rook placements on length 4 shaded staircase boards. When we substitute $q = -1$ into the $q$-Stirling number of the first kind, the weight $\text{wt}(T)$ of a rook placement $T$ will be 0 if there is a rook in $T$ that is not in the first row. Hence the Stirling number of the first kind $c_q[n, k]$ evaluated at $q = -1$ counts the number of rook placements in $Q(n, n-k)$ such that all of the rooks occur in the first row.

**Corollary 7.5** The $q$-Stirling number of the first kind $c_q[n, k]$ evaluated at $q = -1$ gives the number of rook placements in $Q(n, n-k)$ where all of the rooks occur in the first row, that is,

$$c_q[n, k]|_{q=-1} = \binom{|n/2|}{n-k}.$$

# 8 Structure and topology of Stirling poset of the first kind

We define a poset structure on rook placements on a staircase shape board. For rook placements $T$ and $T'$ in $\mathcal{P}(m, n)$, let $T \prec T'$ if $T'$ can be obtained from $T$ by either moving a rook to the left (west) or up (north) by one square. We call this poset the Stirling poset of the first kind and denote it by $\Gamma(m, n)$. It is
<figure><img src="image_5.png" /><figcaption>Fig. 4: The matching on $\Gamma(4, 2)$. There is one unmatched rook placement on rank 2.</figcaption></figure>

straightforward to check that the poset $\Gamma(m, n)$ is graded of rank $(m-1) + (m-2) + \cdots + (m-n) = m \cdot n - \binom{n+1}{2}$ and its rank generating function is $c_q[m, m-n]$. See Figure 4 as an example.

We wish to study the topological properties of the Stirling poset of the first kind. To do so, we define a matching $M$ on the poset as follows. Given any rook placement $T \in \Gamma(m, n)$, let $r$ be the first rook (reading from left to right) that is not in a shaded square of the first row. Match $T$ to $T'$ where $T'$ is obtained from $T$ by moving the rook $r$ one square down if $r$ is not in a shaded square, or one square up if $r$ is in a shaded square but not in the first row. It is straightforward to check that the unmatched rook placements are the ones with all of the rooks occur in the shaded squares of the first row.

As an example, the matching for $\Gamma(4, 2)$ is shown in Figure 4, where an upward arrow indicates a matching and other edges indicate the remaining cover relations. Observe the unmatched rook placements are the ones with all the rooks occurring in the shaded squares of the first row. By the way a chessboard is shaded, the unmatched rook placements only appear in even ranks in the poset.

We have the $q$-analogue of Corollary 7.5

**Theorem 8.1** For the Stirling poset of the first kind $\Gamma(m, n)$, the generating function for unmatched rook placements is

$$ \sum_{\substack{T \in \mathcal{P}(m,n) \\ T \text{ unmatched}}} \mathrm{wt}(T) = q^{n(n-1)} \cdot \left[ \binom{\left\lfloor \frac{m+1}{2} \right\rfloor}{n} \right]_{q^2}. $$

Using a similar gradient path argument as for $\Pi(n, k)$, we have the following result.

**Theorem 8.2** The matching $M$ on the Stirling poset of the first kind $\Gamma(m, n)$ is an acyclic matching.

Next we give a decomposition of the Stirling poset of the first kind $\Gamma(m, n)$ into Boolean algebras indexed by the allowable rook placements. This will lead to a boundary map on the algebraic complex
with $\Gamma(m, n)$ as the support. For any $T \in \mathcal{Q}(m, n)$, let $\alpha(T)$ be the rook placement obtained by shifting every rook that is not in the first row up by one. Then we have

**Theorem 8.3** The Stirling poset of the first kind $\Gamma(m, k)$ can be decomposed as disjoint union of Boolean intervals

$$ \Gamma(m, n) = \bigcup_{T \in \mathcal{Q}(m,n)} [T, \alpha(T)]. $$

Furthermore, if $T \in \mathcal{Q}(m, n)$ has weight $\mathrm{wt}(T) = q^i \cdot (1+q)^j$, then the rank of the element $T$ is $i$ and the interval $[T, \alpha(T)]$ is isomorphic to the Boolean algebra on $j$ elements.

Given a rook placement $T \in \Gamma(m, n)$, let $N(T) = \{r_1, r_2, \dots, r_s\}$ be the set of all rooks in $T$ that are not in shaded squares, where the rooks $r_i$ are labeled from left to right. Then

**Lemma 8.4** The map $\partial(T) = \sum_{r_i \in N(T)} (-1)^{i-1} \cdot T_{r_i}$ defined on the algebraic complex supported by the Stirling poset of the first kind $\Gamma(m, n)$, is a boundary map, where $T_{r_i}$ is the rook placement obtained by moving the rook $r_i$ in $T$ down by one square.

Applying Theorem 8.1, Theorem 8.2 and Lemma 8.4 to Lemma 6.3, we have the following result.

**Theorem 8.5** For the algebraic complex $(\mathcal{C}, \partial)$ supported by the Stirling poset of the first kind $\Gamma(m, n)$, a basis for the integer homology is given by the rook placements in $\mathcal{P}(m, n)$ having all of the rooks occur in shaded squares of the first row. Furthermore,

$$ \sum_{i \ge 0} \dim(H_i(\mathcal{C}, \partial; \mathbb{Z})) \cdot q^i = q^{n(n-1)} \cdot \left\lfloor \frac{\frac{m+1}{2}}{n} \right\rfloor_{q^2}. $$

# 9 Generating function and orthogonality

In [24] Viennot has some beautiful results in which he gave combinatorial bijections for orthogonal polynomials and their moment generating functions. One well-known relation between the ordinary signed Stirling numbers of the first kind and Stirling numbers of the second kind is their orthogonality. A bijective proof of the orthogonality of their $q$-analogues via 0-1 tableaux was given by de Médicis and Leroux [2, Proposition 3.1].

There are a number of two-variable Stirling numbers of the second kind using bistatistics on RG-words and rook placements. See [25] and the references therein. Letting $t = 1 + q$ we define $(q, t)$-analogues of the Stirling numbers of the first and second kind. We show orthogonality holds combinatorially for the $(q, t)$-version of the Stirling numbers via a sign-reversing involution on ordered pairs of rook placements and RG-words.

**Definition 9.1** Define the $(q, t)$-Stirling numbers of the first and second kind by

$$ s_{q,t}[n, k] = (-1)^{n-k} \cdot \sum_{T \in \mathcal{Q}(n-1, n-k)} q^{s(T)} \cdot t^{r(T)} \quad \text{and} \quad S_{q,t}[n, k] = \sum_{w \in \mathcal{A}(n,k)} q^{A(w)} \cdot t^{B(w)}. $$
For what follows, let

$$ [k]_{q,t} = \begin{cases} (q^{k-2} + q^{k-4} + \dots + 1) \cdot t & \text{when } k \text{ is even,} \\ q^{k-1} + (q^{k-3} + q^{k-5} + \dots + 1) \cdot t & \text{when } k \text{ is odd.} \end{cases} \qquad (9.1) $$

**Corollary 9.2** The $(q, t)$-analogue of Stirling numbers of the first and second kind satisfy the following recurrences:

$$ s_{q,t}[n,k] = s_{q,t}[n-1,k-1] - [n-1]_{q,t} \cdot s_{q,t}[n-1,k] \quad \text{for } n \ge 1 \text{ and } 1 \le k \le n, \qquad (9.2) $$

and

$$ S_{q,t}[n,k] = S_{q,t}[n-1,k-1] + [k]_{q,t} \cdot S_{q,t}[n-1,k] \quad \text{for } n \ge 1 \text{ and } 1 \le k \le n \qquad (9.3) $$

with initial conditions $s_{q,t}[n, 0] = \delta_{n,0}$ and $S_{q,t}[n, 0] = \delta_{n,0}$.

Recall the generating polynomials for $q$-Stirling numbers are $(x)_{n,q} = \sum_{k=0}^{n} s_q[n,k] \cdot x^k$ and $x^n = \sum_{k=0}^{n} S_q[n,k] \cdot (x)_{k,q}$, where $(x)_{k,q} = \prod_{m=0}^{k-1} (x - [m]_q)$. We can generalize these to $(q, t)$-polynomials.

**Theorem 9.3** The generating polynomials for the $(q, t)$-Stirling numbers are

$$ (x)_{n,q,t} = \sum_{k=0}^{n} s_{q,t}[n,k] \cdot x^k \quad \text{and} \quad x^n = \sum_{k=0}^{n} S_{q,t}[n,k] \cdot (x)_{k,q,t}, $$

$$ \text{where } (x)_{k,q,t} = \prod_{m=0}^{k-1} (x - [m]_{q,t}). $$

**Theorem 9.4** The $(q, t)$-Stirling numbers are orthogonal, that is, for $m \le n$,

$$ \sum_{k=m}^{n} s_{q,t}[n,k] \cdot S_{q,t}[k,m] = \delta_{m,n} \quad \text{and} \quad \sum_{k=m}^{n} S_{q,t}[n,k] \cdot s_{q,t}[k,m] = \delta_{m,n}. $$

Furthermore, this orthogonality holds bijectively.

## Acknowledgements

The authors thank Dennis Stanton for conversations when this project was being initiated. They also thank Richard Ehrenborg, who provided many helpful comments on the write-up.

## References

[1] L. CARLITZ, On abelian fields, *Trans. Amer. Math. Soc.* **35** (1933), 122-136.

[2] A. DE MÉDICIS AND P. LEROUX, A unified combinatorial approach for $q$- (and $p, q$-) Stirling numbers, *J. Statist. Plann. Inference* **34** (1993), 89-105.
[3] R. EHRENBORG AND M. READDY, Juggling and applications to $q$-analogues, *Discrete Math.* **157** (1996), 107–125.

[4] R. FORMAN, A user's guide to discrete Morse theory, *Sem. Lothar. Combin.* **48** (2002), Art. B48c, 35 pp.

[5] S. FU, V. REINER, D. STANTON AND N. THIEM, The negative $q$-binomial, *Electronic Journal of Combinatorics* **19** (2012), P36.

[6] A. M. GARSIA AND J. B. REMMEL, $q$-counting rook configurations and a formula of Frobenius, *J. Combin. Theory Ser. A* **41** (1986), 246–275.

[7] H. W. GOULD, The $q$-Stirling numbers of the first and second kinds, *Duke Math. J.* **28** (1961), 281–289.

[8] P. HERSH, J. SHARESHIAN AND D. STANTON, The $q = -1$ phenomenon via homology concentration, *J. Comb.* **5** (2014), 167–194.

[9] G. HUTCHINSON, Partitioning algorithms for finite sets, *Comm. ACM* **6** (1963), 613–614.

[10] M. JÖLLENBECK AND V. WELKER, Minimal resolutions via algebraic discrete Morse theory, *Mem. Amer. Math. Soc.* **197** (2009), no. 923, 74 pp.

[11] D. KOZLOV, Discrete Morse theory for free chain complexes, *C. R. Math. Acad. Sci. Paris* **340** (2005), no. 12, 867–872.

[12] D. KOZLOV, “Combinatorial Algebraic Topology,” *Algorithms and Computation in Mathematics* (Volume. 21), Springer, 2008.

[13] P. LEROUX, Reduced matrices and $q$-log-concavity properties of $q$-Stirling Numbers, *J. Combin. Theory Ser. A* **54** (1990), 64–84.

[14] P. A. MACMAHON, Two applications of general theorems in combinatory analysis, *Proc. London Math. Soc.* **15** (1916), 314–321.

[15] S. MILNE, Restricted growth functions and incidence relations of the lattice of partitions of an $n$-set, *Advances in Math.* **26** (1977), 290–305.

[16] S. MILNE, A $q$-analog of restricted growth functions, Dobinski's equality, and Charlier polynomials, *Trans. Amer. Math. Soc.* **245** (1978), 89–118.

[17] E. NETTO, “Lehrbuch der Combinatorik,” Chelsea, New York, 1901.

[18] V. REINER, D. STANTON AND D. WHITE, The cyclic sieving phenomenon, *J. Combin. Theory Ser. A* **108** (2004), 17–50.

[19] G.-C. ROTA, The number of partitions of a set, *Amer. Math. Monthly* **71** (1964), 498–504.

[20] E. SKÖLDBERG, Morse theory from an algebraic viewpoint, *Trans. Amer. Math. Soc.* **358** (2006), 115–129.

[21] R. P. STANLEY, “Enumerative Combinatorics, Vol. I, 2nd edition,” Cambridge Studies in Advanced Mathematics (No. 49), Cambridge University Press, 2012.

[22] J. STEMBRIDGE, Some hidden relations involving the ten symmetry classes of plane partitions, *J. Combin. Theory Ser. A* **68** (1994), 372–409.

[23] J. STEMBRIDGE, Canonical bases and self-evacuating tableaux, *Duke Math. J.* **82** (1996), 585–606.

[24] G. VIENNOT, A combinatorial theory for general orthogonal polynomials with extensions and applications, in *Polynômes Orthogonaux et Applications* (Bar-le-Duc, 1984), 139–157, *Lecture Notes in Mathematics Volume 1171*, Springer, Berlin, 1985.

[25] M. WACHS AND D. WHITE, $p, q$-Stirling numbers and set partition statistics, *J. Combin. Theory Ser. A* **56** (1991), 27–46.