% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \usepackage{fullpage} \usepackage{latexsym} \usepackage{color} \usepackage{enumerate} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \allowdisplaybreaks[1] \DeclareMathOperator{\NLRM}{NLRM} \DeclareMathOperator{\ls}{ls} \DeclareMathOperator{\un}{un} \DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\wt}{wt} \DeclareMathOperator{\Inv}{Inv} \DeclareMathOperator{\GF}{GF} \newcommand{\Ppp}{{\mathbb P}} \newcommand{\qchoose}[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{#3}} \newcommand{\rg}[2]{RG(#1,#2)} \newcommand{\allow}[2]{{\mathcal A}(#1,#2)} \newcommand{\hz}{\widehat{0}} \newcommand{\ho}{\widehat{1}} \newcommand{\join}{\vee} \newcommand{\negwt}{\wt'} \newcommand{\plusdots}{+ \cdots +} \newcommand{\timesdots}{\times \cdots \times} \newcommand{\disjointunion}{{\stackrel{\centerdot}{\bigcup}}} \newcommand{\bigcupdotalt}{\charfusion[\mathop]{\bigcup}{\cdot}} %attempt disjoint union \makeatletter \def\moverlay{\mathpalette\mov@rlay} \def\mov@rlay#1#2{\leavevmode\vtop{% \baselineskip\z@skip \lineskiplimit-\maxdimen \ialign{\hfil$\m@th#1##$\hfil\cr#2\crcr}}} \newcommand{\charfusion}[3][\mathord]{ #1{\ifx#1\mathop\vphantom{#2}\fi \mathpalette\mov@rlay{#2\cr#3} } \ifx#1\mathop\expandafter\displaylimits\fi} \makeatother %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf $q$-Stirling Identities Revisited} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Yue Cai\thanks{Supported by the Simons Foundation (grant \#206001) for two research visits to Princeton University to work with the second and third author.}\\ \small Department of Mathematics\\[-0.8ex] \small Texas A\&M University\\[-0.8ex] \small College Station, TX 77843-3368, U.S.A.\\ \small\tt ycai@math.tamu.edu\\ \and Richard Ehrenborg\thanks{Supported by NSA grant H98230-13-1-0280 and a grant from the Simons Foundation (\#429370 to Richard Ehrenborg).} \qquad Margaret Readdy\thanks{Supported by grants from the Simons Foundation (\#206001 and \#422467 to Margaret Readdy).}\\ \small Department of Mathematics\\[-0.8ex] \small University of Kentucky\\[-0.8ex] \small Lexington, KY 40506-0027, U.S.A.\\ \small\tt \{richard.ehrenborg,margaret.readdy\}@uky.edu } %% \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Feb 14, 2017}{Dec 29, 2017}\\ \small Mathematics Subject Classifications: 05A30, 05A19, 05E05, 06A07} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} We give combinatorial proofs of $q$-Stirling identities using restricted growth words. This includes a poset theoretic proof of Carlitz's identity, a new proof of the $q$-Frobenius identity of Garsia and Remmel and of Ehrenborg's Hankel $q$-Stirling determinantal identity. We also develop a two parameter generalization to unify identities of Mercier and include a symmetric function version. % keywords are optional \bigskip \noindent \textbf{Keywords:} $q$-analogues, $q$-Stirling numbers, restricted growth words, poset decomposition \end{abstract} \section{Introduction} \label{section_introduction} The classical Stirling number of the second kind $S(n,k)$ is the number of set partitions of $n$ elements into $k$ blocks. The Stirling numbers of the second kind first appeared in work of Stirling in 1730, where he gave the Newton expansion of the functions $f(z) = z^n$ in terms of the falling factorial basis~\cite[Page~8]{Stirling}. Kaplansky and Riordan~\cite{Kaplansky_Riordan} found the combinatorial interpretation that the Stirling number $S(n,k)$ enumerates the number %%% margie of ways to place $n-k$ non-attacking rooks on a triangular board of side length $n-1$. From later work of Garsia and Remmel, this is equivalent to the number of set partitions of $n$ elements into $k$ blocks~\cite{Garsia_Remmel}. The $q$-Stirling numbers of the second kind arose from Carlitz's development of a $q$-analogue of the Bernoulli numbers and is predated by a problem of his involving abelian groups~\cite{Carlitz,Carlitz_identity}. There is a long history of studying set partitions~\cite{Comtet,Garsia_Remmel,Leroux,Rota}, Stirling numbers of the second kind and their $q$-analogues~\cite{Carlitz, Ehrenborg_Readdy_juggling, Gould, Milne_q_analog, Wachs_White,White}. In the literature there are many identities involving Stirling and $q$-Stirling numbers of the second kind. Stirling identities which appear in Jordan's text~\cite{Jordan} have been transformed to $q$-identities by Ernst~\cite{Ernst} using the theory of Hahn--Cigler--Carlitz--Johnson, Carlitz--Gould and the Jackson $q$-derivative. Verde-Star uses the divided difference operator~\cite{Verde-Star} and the complete homogeneous symmetric polynomials in the indeterminates $x_k = 1 + q + \cdots + q^{k}$ in his work~\cite{Verde-Star_transformation}. The goal of this paper is to give bijective proofs of many of these $q$-Stirling identities as well as a number of new identities. Underlying these proofs is the theory of restricted growth words which we review in the next section. In Section~\ref{section_recurrence} we discuss recurrence structured $q$-Stirling identities, while in Section~\ref{section_generating_function} we focus on Gould's ordinary generating function for the $q$-Stirling number. A poset theoretic proof of Carlitz's identity is given in Section~\ref{section_poset_Carlitz}. Section~\ref{section_convolution} contains combinatorial proofs of the de M\'edicis--Leroux $q$-Vandermonde convolutions. We provide new proofs of Garsia and Remmel's $q$-analogue of the Frobenius identity and of Ehrenborg's Hankel $q$-Stirling determinantal identity in Sections~\ref{section_Frobenius} and~\ref{section_determinantal}. In Section~\ref{section_another_identity_from_Carlitz} we prove two identities of Carlitz each using a sign-reversing involution on $RG$-words. In Section~\ref{section_extension_of_Mercier} we prove two parameter $q$-Stirling identities, generalizing identities of Mercier and include a symmetric function reformulation. We end with concluding remarks. \section{Preliminaries} \label{section_preliminaries} A word $w = w_{1} w_{2} \cdots w_{n}$ of length $n$ where the entries are positive integers is called a {\em restricted growth word}, or {\em $RG$-word} for short, if $w_{i}$ is bounded above by $\max(0, w_{1}, w_{2}, \ldots, $ $w_{i-1}) + 1$ for all indices $i$. This class of words was introduced by Milne in the papers~\cite{Milne_restricted,Milne_q_analog}. The set of $RG$-words of length $n$ where the largest entry is $k$ is in bijective correspondence with set partitions of the set $\{1,2, \ldots, n\}$ into $k$ blocks. Namely, if $w_{i} = w_{j}$, place the elements $i$ and $j$ in the same block of the partition. To describe the inverse of this bijection, write the partition $\pi = B_{1} / B_{2} / \cdots / B_{k}$ in standard form, that is, with $\min(B_{1}) < \min(B_{2}) < \cdots < \min(B_{k})$. The associated $RG$-word is given by $w = w_1 \cdots w_n$ where $w_{i} = j$ if the entry $i$ appears in the $j$th block $B_{j}$ of $\pi$. %%% margie One way to obtain a $q$-analogue of Stirling numbers of the second kind is to introduce a weight on $RG$-words. Let $\rg{n}{k}$ denote the set of all $RG$-words of length $n$ with maximal entry~$k$. Observe that $\rg{n}{k}$ is the empty set if $n < k$. The set $\rg{n}{0}$ is also empty for $n > 0$ but the set $\rg{0}{0}$ is the singleton set consisting of the empty word $\epsilon$. Define the weight of $w = w_{1} w_{2} \cdots w_{n} \in \rg{n}{k}$ by \begin{equation} \wt(w) = q^{\sum_{i=1}^{n} (w_{i} - 1) - \binom{k}{2}} . \end{equation} The {\em $q$-Stirling numbers of the second kind} are given by \begin{equation} S_{q}[n,k] = \sum_{w \in \rg{n}{k}} \wt(w). \label{equation_rg_interpretation} \end{equation} See Cai and Readdy~\cite[Sections~2 and~3]{Cai_Readdy}. This definition satisfies the recurrence definition for $q$-Stirling numbers of the second kind originally due to Carlitz; see~\cite[pages~128--129]{Carlitz} and~\cite[Section~3]{Carlitz_identity}: \begin{equation*} \label{equation_Stirling2_recurrence} S_{q}[n,k] = S_{q}[n-1, k-1] + [k]_{q} \cdot S_{q}[n-1,k] \:\: \mbox{ for } 1 \leq k \leq n, \end{equation*} where $[k]_q = 1 + q + \cdots + q^{k-1}$. To see this, consider a word $w \in \rg{n}{k}$. If the last letter is a left-to-right maxima then the word $w$ is of the form $w = v \cdot k$ where $v \in \rg{n-1}{k-1}$, yielding the first term of the recurrence. Otherwise $w$ is of the form $w = v \cdot i$ where $v \in \rg{n-1}{k}$ and $1 \leq i \leq k$, which yields the second term of the recurrence. The boundary conditions $S_{q}[n,0] = \delta_{n,0}$ and $S_{q}[0,k] = \delta_{0,k}$ also follow from the interpretation~\eqref{equation_rg_interpretation}. For other weightings of $RG$-words which generate the $q$-Stirling numbers of the second kind, see~\cite{Milne_restricted_rank_row} and~\cite{Wachs_White}. For a word $w = w_{1} w_{2} \cdots w_{n}$ define the {\em length} of $w$ to be $\ell(w) = n$. Similarly, define the {\em $\ls$-weight} of $w$ to be $\ls(w) = q^{\sum_{i=1}^{n} (w_{i}-1)}$. This is a generalization of the $ls$-statistic of $RG$-words~\cite[Section~2]{Wachs_White}. The concatenation of two words $u$ and $v$ is denoted by $u \cdot v$. The word~$v$ is a {\em factor} of the word $w$ if one can write $w = u_{1} \cdot v \cdot v_{2}$. A word $v = v_{1} v_{2} \cdots v_{k}$ is a {\em subword} of~$w$ if there is a sequence $1 \leq i_{1} < i_{2} < \cdots < i_{k} \leq n$ such that $w_{i_{j}} = v_{j}$ for all $1 \leq j \leq k$. In other words, a factor of $w$ is a subword consisting of consecutive entries. For $S$ a set of positive integers, let $S^{k}$ denote the set of all words of length $k$ with entries in $S$. Furthermore, let $S^{*}$ denote the union $S^{*} = \bigcupdotalt_{k \geq 0} S^{k}$, that is, the set of all words with entries in $S$. Observe that when $S$ is the empty set then $S^{*}$ consists only of the empty word $\epsilon$. Let $[j,k]$ denote the interval $[j,k] = \{i \in \Ppp \: : \: j \leq i \leq k\}$. Recall the $q$-Stirling numbers of the second kind are specializations of the homogeneous symmetric function $h_{n-k}$: \begin{equation} S_{q}[n,k] = h_{n-k}([1]_{q}, [2]_{q}, \ldots, [k]_{q}). \label{equation_complete_symmetric_functions} \end{equation} See for instance~\cite[Chapter~I, Section~2, Example~11]{Macdonald}. This follows directly by observing that a word $w \in \rg{n}{k}$ has a unique expansion of the form \begin{equation} w = 1 \cdot u_{1} \cdot 2 \cdot u_{2} \cdots k \cdot u_{k} , \label{equation_expansion} \end{equation} where $u_{i}$ is a word in $[1,i]^{*}$. By summing over all words $u_{i}$ for $i = 1, \ldots, k$ such that the sum of their lengths is $\ell(u_{1}) + \ell(u_{2}) \plusdots \ell(u_{k}) = n-k$, equation~\eqref{equation_complete_symmetric_functions} follows. \section{Recurrence related identities} \label{section_recurrence} In this section we focus on recurrence structured identities for the $q$-Stirling numbers of the second kind. The proofs we provide here use the combinatorics of $RG$-words. We begin with Mercier's identity~\cite[Theorem~3]{Mercier_q_identities}. This is a $q$-analogue of Jordan~\cite[equation~9, page~187]{Jordan}. Mercier's original proof of Theorem~\ref{theorem_Mercier_recurrence} was by induction. Later a combinatorial proof using $0$-$1$ tableaux was given by de M\'edicis and Leroux~\cite{de_Medicis_Leroux_unified}. In the same paper, de M\'edicis and Leroux proved Theorems~\ref{theorem_de_Medicis_Leroux_recurrence} and \ref{theorem_de_Medicis_Leroux_recurrence_2} using $0$-$1$ tableaux. \begin{theorem}[Mercier, 1990] \label{theorem_Mercier_recurrence} For nonnegative integers $n$ and $k$, the following identity holds: \begin{equation} S_{q}[n+1, k+1] = \sum_{m = k}^{n} \binom{n}{m} \cdot q^{m-k} \cdot S_{q}[m,k] . \end{equation} \end{theorem} \begin{proof} When $n < k$ there is nothing to prove. For any word $w \in \rg{n+1}{k+1}$, suppose there are $m$ entries in $w$ that are not equal to one. Remove the $n+1-m$ entries equal to one in~$w$ and then subtract one from each of the remaining~$m$ entries to obtain a new word $u$. Observe $u \in \rg{m}{k}$ and $\wt(w) = q^{m-k} \cdot \wt(u)$. Conversely, given a word $u \in \rg{m}{k}$, one can first increase each of the $m$ entries by one and then insert $n+1-m$ ones into the word to obtain an $RG$-word $w \in \rg{n+1}{k+1}$. There are $\binom{n}{n-m} = \binom{n}{m}$ ways to insert the~$n+1-m$ ones since the first entry in an $RG$-word must be one. In other words, for any $u \in \rg{m}{k}$ we can obtain $\binom{n}{m}$ new $RG$-words in $\rg{n+1}{k+1}$ under the map described above, which gives the desired identity. \end{proof} Using similar ideas we also prove the following $q$-identity. It is a $q$-analogue of a result due to Jordan~\cite[equation~7, page~187]{Jordan}. \begin{theorem} \label{theorem_q_Jordan} For two non-negative integers $n$ and $m$, the following identity holds: \begin{equation} q^{n-m} \cdot S_{q}[n,m] = \sum_{k=m}^{n} (-1)^{n-k} \cdot \binom{n}{k} \cdot S_{q}[k+1,m+1] . \label{equation_alternating_sum} \end{equation} \end{theorem} \begin{proof} For a subset $A \subseteq \{2,3, \ldots, n+1\}$ observe that the sum over the weights of $RG$-words in the set $\rg{n+1}{m+1}$ with ones in the set of positions containing the set~$A$ is given by $S_{q}[n+1-|A|,m+1]$. Hence by inclusion-exclusion the right-hand side of equation~\eqref{equation_alternating_sum} is the sum of the weights of all words in $\rg{n+1}{m+1}$ %%% margie %%% where the only one is in the where the element $1$ only occurs in first position. This set of $RG$-words is also obtained by taking a word in $\rg{n}{m}$, adding one to each entry, which multiplies the weight by~$q^{n-m}$, and concatenating it with a one on the left. \end{proof} Theorems~\ref{theorem_de_Medicis_Leroux_recurrence} and \ref{theorem_de_Medicis_Leroux_recurrence_2} appear in~\cite[Propositions~2.3 and~2.5]{de_Medicis_Leroux_unified}. We now give straightforward proofs of each result using $RG$-words. \begin{theorem}[de M\'edicis--Leroux, 1993] \label{theorem_de_Medicis_Leroux_recurrence} For nonnegative integers $n$ and $k$, the following identity holds: \begin{equation} S_{q}[n+1, k+1] = \sum_{j = k} ^{n} [k+1]_{q}^{n-j} \cdot S_{q}[j,k]. \end{equation} \end{theorem} \begin{proof} Factor a word $w \in \rg{n+1}{k+1}$ as $w = x \cdot (k+1) \cdot y$ where $x \in \rg{j}{k}$ for some $j \geq k$ and $y$ belongs to $[1,k+1]^{*}$. The factor $y$ has length $n-j$. The sum of the weights of these words is $[k+1]_{q}^{n-j} \cdot S_{q}[j,k]$. The result follows by summing over all possible integers $j$. \end{proof} \begin{theorem}[de M\'edicis--Leroux, 1993] \label{theorem_de_Medicis_Leroux_recurrence_2} For nonnegative integers $n$ and $k$, the following identity holds: \begin{equation} (n-k)\cdot S_{q}[n,k] = \sum_{j = 1}^{n-k} S_{q}[n-j, k] \cdot ([1]_{q}^{j} + [2]_{q}^{j} + \cdots + [k]_{q}^{j}). \end{equation} \end{theorem} \begin{proof} For a word $w \in \rg{n}{k}$ consider factorizations $w = x \cdot y \cdot z$ with the following two properties: (1) the rightmost letter of the factor $x$, call this letter~$i$, is a left-to-right maxima of $x$, and (2) the word $y$ is non-empty and all letters of $y$ are at most~$i$. We claim that the number of such factorizations of $w$ is $n-k$. Let $s_{i}$ be the number of letters between the first occurrence of $i$ and the first occurrence of $i+1$, and let $s_{k}$ be the number of letters after the first occurrence of $k$. For a particular $i$, we have $s_{i}$ choices for the word $y$. But $\sum_{i=1}^{k} s_{i} = n-k$ since there are $n-k$ repeated letters in $w$. This completes the claim. Fix integers $1 \leq j \leq n-k$ and $1 \leq i \leq k$. Given a word $u \in \rg{n-j}{k}$, we can factor it uniquely as~$x \cdot z$, where the last letter of $x$ is the first occurrence of $i$ in the word~$u$. Pick $y$ to be any word of length $j$ with letters at most $i$. Finally, let $w = x \cdot y \cdot z$. Observe that this is a factorization satisfying the conditions from the previous paragraph. Furthermore, we have $\wt(w) = \wt(u) \cdot \ls(y)$. Summing over all words $u \in \rg{n}{k}$ and words $y \in [1,i]^{j}$ yields $S_{q}[n-j, k] \cdot [i]_{q}^{j}$. Lastly, summing over all $i$ and $j$ gives the desired equality. \end{proof} \section{Gould's generating function} \label{section_generating_function} Gould~\cite[equation~(3.4)]{Gould} gave an analytic proof for the ordinary generating function of the $q$-Stirling numbers of the second kind. Later Ernst~\cite[Theorem~3.22]{Ernst} gave a proof using the orthogonality of the $q$-Stirling numbers of the first and second kinds. Wachs and White~\cite{Wachs_White} stated a $p,q$-version of this generating function without proof. Here we prove Gould's $q$-generating function using $RG$-words. \begin{theorem}[Gould, 1961] The $q$-Stirling numbers of the second kind $S_{q}[n,k]$ have the generating function \begin{equation} \label{equation_generating_function} \sum_{n \geq k} S_{q}[n,k] \cdot t^{n} = \frac{t^k}{\prod_{i=1}^k (1-[i]_{q} \cdot t)}. \end{equation} \end{theorem} \begin{proof} The left-hand side of~\eqref{equation_generating_function} is the sum of over all $RG$-words $w$ of length at least $k$ with largest letter $k$ where each term is $\wt(w) \cdot t^{\ell(w)}$. Using the expansion in equation~\eqref{equation_expansion}, that is, $w = 1 \cdot u_{1} \cdot 2 \cdot u_{2} \cdots k \cdot u_{k}$ where $u_{i}$ is a word in $[1,i]^{*}$, observe the weight of $w$ factors as $\wt(w) = \ls(u_{1}) \cdot \ls(u_{2}) \cdots \ls(u_{k})$ whereas the term $t^{\ell(w)}$ factors as $t^{k} \cdot t^{\ell(u_{1})} \cdot t^{\ell(u_{2})} \cdots t^{\ell(u_{k})}$. Since there are no restrictions on the length of $i$th word $u_{i}$, all the words $u_{i}$ for $i = 1, \ldots, k$ together contribute the factor $1 + [i]_{q} \cdot t + [i]_{q}^{2} \cdot t^{2} + \cdots = 1/(1 - [i]_{q} \cdot t)$. By multiplying together all the contributions from all of the words $u_{i}$, the identity follows. \end{proof} \section{A poset proof of Carlitz's identity} \label{section_poset_Carlitz} In this section we state a poset decomposition theorem for the Cartesian product of chains. This decomposition implies Carlitz's identity. For basic poset terminology and background, we refer the reader to Stanley's treatise~\cite[Chapter~3]{Stanley_EC_I}. Let $C_{m}$ denote the chain on $m$ elements. Recall that $\Ppp^{n}$ is the set of all words of length~$n$ having positive integer entries. We make this set into a poset, in fact, a lattice, by entrywise comparison, where the partial order relation is given by $v_{1} v_{2} \cdots v_{n} \leq w_{1} w_{2} \cdots w_{n}$ if and only if $v_{i} \leq w_{i}$ for all indices $1 \leq i \leq n$. Note that $[1,m]^{n}$ is the subposet consisting of all words of length~$n$ where the entries are at most~$m$. For a word $v$ in $\rg{n}{k}$, factor $v$ according to equation~\eqref{equation_expansion}, that is, write $v$ as the product $v = 1 \cdot u_{1} \cdot 2 \cdot u_{2} \cdots u_{k-1} \cdot k \cdot u_{k}$, where each factor~$u_i$ belongs to $[1,i]^*$. For $m \geq n$ define the word $\omega_{m}(v) = m \cdot u_{1} \cdot m \cdot u_{2} \cdots u_{k-1} \cdot m \cdot u_{k}$. Effectively, each left-to-right maxima is replaced by the integer $m$. Directly it is clear that the interval $[v,\omega_{m}(v)]$ in~$\Ppp^{n}$ is isomorphic to a product of chains, that is, $$ [v,\omega_{m}(v)] \cong C_{m} \times C_{m-1} \timesdots C_{m-k+1} . $$ \begin{theorem} %%% margie %%%% The $n$-fold Cartesian power of the $m$-chain The $n$-fold Cartesian product of the $m$-chain has the decomposition \begin{equation*} [1,m]^{n} = \bigcupdotalt_{0 \leq k \leq \min(m,n)} \: \bigcupdotalt_{v \in \rg{n}{k}} [v,\omega_{m}(v)] . \end{equation*} \label{theorem_Carlitz_poset} \end{theorem} \begin{proof} Define a map $f : \Ppp^{n} \longrightarrow \Ppp^{n}$ as follows. Let $w = w_{1} w_{2} \cdots w_{n}$ be a word in $\Ppp^{n}$. If $w$ is an $RG$-word, let $f(w) = w$. Otherwise let $i$ be the smallest index in $w$ reading from left to right that makes~$w$ fail to be an $RG$-word. In other words, $i$ is the smallest index such that $\max(0,w_{1}, w_{2}, \ldots, w_{i-1})+1 < w_{i}$. Let $f(w)$ be the new word formed by replacing the $i$th entry of $w$ with $\max(0,w_{1}, w_{2}, \ldots, w_{i-1})+1$. Observe that for all words~$w$ we obtain the poset inequality $f(w) \leq w$. Since the word $w$ only has $n$ entries, we know that the $(n+1)$st iteration of $f$ is equal to the $n$th iteration of $f$, that is, $f^{n+1}(w) = f^{n}(w)$. Furthermore, $f^{n}(w)$ is an $RG$-word. Finally, define $\varphi : \Ppp^{n} \longrightarrow \bigcupdotalt_{0 \leq k \leq n} \rg{n}{k}$ to be the map $f^{n}$. Observe that $\varphi$ is a surjection since every $RG$-word is a fixed point. Furthermore, for all words $w$ the inequality $\varphi(w) \leq w$ holds in the poset $\Ppp^{n}$. Let $v$ be a word in $\rg{n}{k}$. Use the expansion~\eqref{equation_expansion} to write $v$ in the form $v = 1 \cdot u_{1} \cdot 2 \cdot u_{2} \cdots u_{k-1} \cdot k \cdot u_{k}$, where $u_{i} \in [1,i]^{*}$. It is straightforward to check that the fiber $\varphi^{-1}(v)$ is given by \begin{equation} \varphi^{-1}(v) = \{ j_{1} \cdot u_{1} \cdot j_{2} \cdot u_{2} \cdots u_{k-1} \cdot j_{k} \cdot u_{k} \: : \: i \leq j_{i} \text{ for } i=1, 2, \ldots, k\}. \label{equation_fiber} \end{equation} Observe that as a poset this fiber is isomorphic to $\Ppp^{k}$. When we restrict to $[1,m]^{n}$ we obtain that the intersection $\varphi^{-1}(v) \cap [1,m]^{n}$ is the interval $[v,\omega_{m}(v)]$. Taking the disjoint union over all $RG$-words~$v$, the decomposition follows. \end{proof} By considering the rank generating function of Theorem~\ref{theorem_Carlitz_poset}, we can obtain a poset theoretic proof of Carlitz's identity~\cite[Section~3]{Carlitz_identity}. Other proofs are due to Milne using finite operator techniques on restricted growth functions~\cite{Milne_q_analog}, de M\'edicis and Leroux via interpreting the identity as counting products of matrices over the finite field $\GF(q)$ having non-zero columns~\cite{de_Medicis_Leroux_unified}, and Ehrenborg and Readdy using the theory of juggling sequences~\cite{Ehrenborg_Readdy_juggling}. \begin{corollary}[Carlitz, 1948] The following $q$-identity holds: \begin{equation} \label{equation_Carlitz_identity} [m]_{q}^{n} = \sum_{k=0}^{n} q^{\binom{k}{2}} \cdot S_{q}[n, k] \cdot [k]_{q}! \cdot \qchoose{m}{k}{q}. \end{equation} \label{corollary_Carlitz_identity} \end{corollary} \begin{proof} The cases when $n=0$ or $m=0$ are straightforward. The rank generating function of the left-hand side of Theorem~\ref{theorem_Carlitz_poset} is $[m]_{q}^{n}$. The rank generating function of the interval $[v, \omega_{m}(v)]$ is $q^{\binom{k}{2}} \cdot \wt(v) \cdot [m]_{q} \cdot [m-1]_{q} \cdots [m-k+1]_{q}$. By summing over all $RG$-words, the result follows. \end{proof} \begin{remark} {\em Similar poset techniques used to prove Theorem~\ref{theorem_Carlitz_poset} and Corollary~\ref{corollary_Carlitz_identity} can be applied to obtain the identities in Section~\ref{section_recurrence}. The proofs are omitted.} \end{remark} The map $\varphi$ that appears in the proof of Theorem~\ref{theorem_Carlitz_poset} has interesting properties. \begin{proposition} The map $\varphi : \Ppp^{n} \longrightarrow \bigcupdotalt_{0 \leq k \leq n} \rg{n}{k}$ is the dual of a closure operator, that is, it satisfies the following three properties: \vspace*{-3mm} \begin{enumerate}[(i)] \item $\varphi(w) \leq w$, \vspace*{-2.5mm} \item $\varphi^{2}(w) = \varphi(w)$ and \vspace*{-2.5mm} \item $v \leq w$ implies that $\varphi(v) \leq \varphi(w)$. \end{enumerate} \end{proposition} \begin{proof} Properties~(i) and~(ii) are direct from the construction of the map $\varphi$. To prove property~(iii) assume that we have $v \leq w$ but $\varphi(v) \not\leq \varphi(w)$. Let $i$ be the smallest index such that $\varphi(w)_{i} < \varphi(v)_{i}$. Especially for $j < i$ we have $\varphi(w)_{j} \geq \varphi(v)_{j}$. Since $\varphi(w)_{i} < \varphi(v)_{i} \leq v_{i} \leq w_{i}$, we know that the $i$th coordinate is changed when computing $\varphi(w)$. Hence $\varphi(w)_{i} = \max(0,\varphi(w)_{1}, \ldots, \varphi(w)_{i-1}) + 1 \geq \max(0,\varphi(v)_{1}, \ldots, \varphi(v)_{i-1}) + 1 \geq \varphi(v)_{i}$, a contradiction. \end{proof} As a consequence of the closure property, if $v$ and $w$ are $RG$-words then so is their join $v \join w = u$ where the $i$th entry is given by $u_{i} = \max(v_{i},w_{i})$. This can also be proven directly. Note however that the set of $RG$-words is not closed under the meet operation; see for instance the two $RG$-words $1123$ and $1213$. \section{$q$-Vandermonde convolutions} \label{section_convolution} Verde-Star gave Vandermonde convolution identities for Stirling numbers of the second kind~\cite[equations~(6.24), (6.25)]{Verde-Star}. Chen gave a grammatical proof for the first of these identities~\cite[Proposition~4.1]{Chen}. For $q$-analogues of both identities, de M\'edicis and Leroux used $0,1$-tableaux for their argument~\cite[equations~(1.12), (1.14)] {de_Medicis_Leroux_convolution}. In this section we present combinatorial proofs of the de M\'edicis--Leroux results using $RG$-words. As a remark, Theorem~\ref{theorem_Mercier_recurrence} is the special case of $n=1$ in Theorem~\ref{theorem_Anne_and_Pierre_1}. \begin{theorem}[de M\'edicis--Leroux, 1995] The following $q$-Vandermonde convolution holds for $q$-Stirling numbers of the second kind: \begin{equation} \label{equation_convolution_1} S_{q}[m+n,k] = \sum_{i+j \geq k} \binom{m}{j} \cdot q^{i\cdot (i+j-k)} \cdot [i]_{q}^{m-j} \cdot S_{q}[n,i] \cdot S_{q}[j, k-i] . \end{equation} \label{theorem_Anne_and_Pierre_1} \end{theorem} \begin{proof} Given a word $w \in \rg{m+n}{k}$, factor it as~$w = u \cdot z$ where $u$ has length $n$ and $i$ is the largest entry in $u$. By assumption, $u \in \rg{n}{i}$. The second factor $z = w_{n+1} \cdot w_{n+2} \cdots w_{n+m}$ has length $m$ and its maximal entry is at most~$k$. In particular, if $i < k$ then the maximal entry for $z$ is exactly $k$. Suppose there are $j$ entries in~$z$ that are strictly larger than $i$. These $j$ entries from $z$ form a subword $v$. Denote by $v^{(-i)}$ the shift of $v$ by subtracting $i$ from each entry in $v$. It is straightforward to check that $v^{(-i)} \in \rg{j}{k-i}$. For any word $w \in \rg{m+n}{k}$, we can decompose it as described above. In such a decomposition, the first segment $u$ contributes to a factor of $S_{q}[n, i]$. The subsequence $v$ of the second segment~$z$ contributes to a factor of $S_{q}[j, k-i] \cdot q^{i \cdot (j-(k-i))}$ since the shift $v^{(-i)}$ causes a weight loss of $q^{i}$ from each of the $j-(k-i)$ repeated entries in $v$. Finally, the remaining entries in~$z$ that are less than or equal to $i$ range from $1$ to $i$. Each will contribute to a factor of $[i]_{q}$. These $m-j$ entries can be assigned at any position in $z$, which gives~$\binom{m}{j}$ choices. Multiplying all these weights, we obtain the desired identity. \end{proof} Note that Theorem~\ref{theorem_de_Medicis_Leroux_recurrence} is a special case of Theorem~\ref{theorem_Anne_and_Pierre_2} when one takes $r=0$. \begin{theorem}[de M\'edicis--Leroux, 1995] The following $q$-Vandermonde convolution holds for $q$-Stirling numbers of the second kind: \begin{equation} \label{equation_convolution_2} S_{q}[n+1, k+r+1] = \sum_{i=0}^{n} \sum_{j=r}^{i} \binom{i}{j} \cdot q^{(k+1) \cdot (j-r)} \cdot [k+1]_{q} ^{i-j} \cdot S_{q}[j,r] \cdot S_{q}[n-i, k]. \end{equation} \label{theorem_Anne_and_Pierre_2} \end{theorem} \begin{proof} This result is proved in a similar fashion as Theorem~\ref{theorem_Anne_and_Pierre_1}. For any $w \in \rg{n+1}{k+r+1}$, suppose $w$ is of the form $x \cdot (k+1) \cdot y$ where $x \in \rg{n-i}{k}$ for some $i$. Consider the remaining word $y = w_{n-i+2} \cdots w_{n+1}$ of length $i$. The maximal entry of~$y$ is $k+r+1$. Suppose there are $j$ entries in~$y$ that are at least $k+2$. These~$j$ entries form a subword $v$, and $v^{(-k-1)}$, obtained by subtracting $k+1$ from each entry in~$v$, is an $RG$-word in $\rg{j}{r}$, giving a total weight of $S_{q}[j,r]$. The weight loss from the shift is $q^{(k+1)\cdot (j-r)}$ since there are $j-r$ repeated entries. The remaining $i-j$ entries in~$y$ can be any value from the interval~$[1,k+1]$. Each such entry contributes to a factor of~$[k+1]_{q}$. Finally, there are $\binom{i}{j}$ ways to place the $j$ entries back into $u$. This proves identity~\eqref{equation_convolution_2}. \end{proof} \begin{remark} {\em Theorem~\ref{theorem_q_Jordan} can be viewed as an inversion of Theorem~\ref{theorem_Mercier_recurrence}. Furthermore, Theorem~\ref{theorem_Mercier_recurrence} is a special case of Theorem~\ref{theorem_Anne_and_Pierre_1}. Is there any sort of natural inversion analogue to Theorem~\ref{theorem_Anne_and_Pierre_1}? } \end{remark} \section{A $q$-analogue of the Frobenius identity} \label{section_Frobenius} We now prove a $q$-analogue of the Frobenius identity by Garsia and Remmel~\cite[equation~I.1]{Garsia_Remmel}. \begin{theorem}[Garsia--Remmel, 1986] \label{theorem_Frobenius} The following $q$-Frobenius identity holds: \begin{equation} \sum_{m \geq 0} [m]_{q}^{n} \cdot x^{m} = \sum_{k=0}^{n} \frac{q^{\binom{k}{2}} \cdot S_{q}[n,k] \cdot [k]_{q}! \cdot x^{k}} {(1-x) \cdot (1-qx) \cdots (1-q^{k}x)}. \label{equation_Frobenius} \end{equation} \end{theorem} \begin{proof} When $n=0$ the result is direct. We concentrate on the case $n > 0$. For a word $w$ in~$\Ppp^{n}$ let $\max(w)$ denote its maximal entry. Hence the left-hand side of equation~\eqref{equation_Frobenius} is given by $$ \sum_{m \geq 0} [m]_{q}^{n} \cdot x^{m} = \sum_{m \geq 0} \sum_{\substack{w \in \Ppp^{n} \\ \max(w) \leq m}} \ls(w) \cdot x^{m} . $$ Recall the poset map $\varphi : \Ppp^{n} \longrightarrow \bigcupdotalt_{0 \leq k \leq n} \rg{n}{k}$ appearing in the proof of Theorem~\ref{theorem_Carlitz_poset}. Let $v \in \rg{n}{k}$. The fiber $\varphi^{-1}(v)$ is given in equation~\eqref{equation_fiber}. The sum over this fiber appears in the proof of Corollary~\ref{corollary_Carlitz_identity}, that is, \begin{align*} \sum_{\substack{w \in \varphi^{-1}(v) \\ \max(w) \leq m}} \ls(w) %& = %\wt(v) %\cdot %\sum_{1 \leq j_{1} \leq m, \ldots, k \leq j_{k} \leq m} %q^{j_{1} - 1} \cdot q^{j_{2} - 1} \cdots q^{j_{k} - 1} \\ & = \wt(v) \cdot q^{\binom{k}{2}} \cdot [m]_{q} \cdot [m-1]_{q} \cdots [m-k+1]_{q} . \end{align*} Multiplying the above by $x^{m}$ and summing over all $m \geq 0$ yields \begin{align*} \sum_{m \geq 0} \sum_{\substack{w \in \varphi^{-1}(v) \\ \max(w) \leq m}} \ls(w) \cdot x^{m} & = \wt(v) \cdot q^{\binom{k}{2}} \cdot [k]_{q}! \cdot \sum_{m \geq 0} \qchoose{m}{k}{q} \cdot x^{m} \\ & = \frac{ \wt(v) \cdot q^{\binom{k}{2}} \cdot [k]_{q}! \cdot x^{k}}{(1-x) \cdot (1-qx) \cdots (1-q^{k}x)} . \end{align*} The result now follows by summing over all $RG$-words of length $n$. \end{proof} \section{A determinantal identity} \label{section_determinantal} The following identity was first stated by Ehrenborg~\cite[Theorem~3.1]{Ehrenborg_determinants} who proved it using juggling patterns. We now present a proof using $RG$-words. \begin{theorem}[Ehrenborg, 2003] \label{theorem_determinants} Let $n$ and $s$ be non-negative integers. Then the following identity holds: $$ \det(S_{q}[s+i+j, s+j])_{0 \leq i,j \leq n} = [s]_{q}^0 \cdot [s+1]_{q}^1 \cdots [s+n]_{q}^{n}. $$ \end{theorem} \begin{proof} Let $T$ be the set of all $(n+2)$-tuples $(\sigma, w(0), w(1), \ldots, w(n))$ where $\sigma$ is a permutation of the $n+1$ elements $\{0,1, \ldots, n\}$, and $w(i)$ is a word in $\rg{s+i+\sigma(i)}{s+\sigma(i)}$ for all $0 \leq i \leq n$. The determinant expands as the sum $$ \det(S_{q}[s+i+j, s+j])_{0 \leq i,j \leq n} = \sum_{(\sigma, w(0), \ldots, w(n)) \in T} (-1)^{\sigma} \cdot \wt(w(0)) \cdot \wt(w(1)) \cdots \wt(w(n)). $$ Factor the word $w(i) \in \rg{s+i+\sigma(i)}{s+\sigma(i)}$ as $w(i) = u(i) \cdot v(i)$ where the lengths are given by $\ell(u(i)) = s+i$ and $\ell(v(i)) = \sigma(i)$. Furthermore, let $a_{i}$ denote the number of repeated entries in the $RG$-word $w(i)$ that appear in the factor $v(i)$, that is, $$ a_{i} = |\{j \: : \: j > s+i, w(i)_{j} = w(i)_{r} \text{ for some } r < j\}|. $$ There are $\sigma(i) - a_{i}$ left-to-right maxima of $w(i)$ that appear in $v(i)$. Since $w(i)$ has $s+\sigma(i)$ left-to-right maxima, we obtain that the first factor $u(i)$ has $(s+\sigma(i)) - (\sigma(i) - a_{i}) = s+a_{i}$ left-to-right maxima, that is, the factor $u(i)$ belongs to the set $\rg{s+i}{s+a_{i}}$. To be explicit, the left-to-right maxima of $u(i)$ are given by $1, 2, \ldots, s+a_{i}$. Lastly, observe that there are $i$ repeated entries in any word $w(i) \in \rg{s+i+\sigma(i)}{s+\sigma(i)}$ and $\sigma(i)$ is the length of $v(i)$, yielding the bound $a_{i} \leq \min(i, \sigma(i))$ for all~$i$. Let $T_{1} \subseteq T$ consist of all tuples $(\sigma, w(0), \ldots, w(n))$ where the sequence of $a_{i}$'s for $i = 0, \ldots, n$ are distinct. This implies $a_{i} = i = \sigma(i)$, that is, $\sigma$ is the identity permutation. Furthermore, the first factor $u(i)$ is equal to $12\cdots (s+i)$ and the second factor $v(i)$ can be any word of length $i$ with the entries from the interval $[1,s+i]$. Thus $\wt(w(i)) = \ls(v(i))$ and the sum over all such words $v(i)$ gives a total weight of~$[s+i]_{q}^{i}$. Thus we have \begin{equation} \label{equation_determinant_subset1} \sum_{(\sigma, w(0), \ldots, w(n)) \in T_{1}} (-1)^{\sigma} \cdot \wt(w(0)) \cdot \wt(w(1)) \cdots \wt(w(n)) = \prod_{i=0}^{n} [s+i]_{q}^{i}. \end{equation} Let $T_{2} = T-T_{1}$ be the complement of $T_{1}$. Define a sign-reversing involution $\varphi$ on $T_{2}$ as follows. For $t = (\sigma, w(0), \ldots, w(n)) \in T_{2}$ there exists indices $i_{1}$ and $i_{2}$ such that $a_{i_{1}} = a_{i_{2}}$. Let $(j,k)$ be the least such pair of indices in the lexicographic order. First let $\sigma' = \sigma \circ (j,k)$ where $(j,k)$ denotes the transposition. Second, let $w(i)' = w(i)$ for $i \neq j,k$. Finally, define $w(j)'$ and $w(k)'$ by switching the second factors in the factorizations, that is, $w(j)' = u(j) v(k)$ and $w(k)' = u(k) v(j)$. Overall, the function is given by $\varphi(t) = (\sigma', w(0)', \ldots, w(n)')$ Since $u(j)$ and $u(k)$ have the same number of left-to-right maxima, it is straightforward to check that $w(j)' = u(j) v(k)$ belongs to $\rg{s+j+\sigma(k)}{s+\sigma(k)} = \rg{s+j+\sigma'(j)}{s+\sigma'(j)}$. Hence it follows that $\varphi(t) \in T_{2}$. Let $a_{i}'$ be the number repeated entries in $w(i)'$ that occur beyond position $s+i$. Directly, we have $a_{i}' = a_{i}$ and we obtain that $\varphi$ is an involution. Finally, we have $(-1)^{\sigma'} = -(-1)^{\sigma}$ implying $\varphi$ is a sign-reversing involution. Finally, it is direct to see that $\wt(w(j)) \cdot \wt(w(k)) = \wt(w(j)') \cdot \wt(w(k)')$ using the observation that $u(j)$ and $u(k)$ have the same number of left-to-right maxima. Hence the map $\varphi$ is a sign-reversing involution on $T_{2}$ which preserves the weight $\wt(w(0)) \cdots \wt(w(n))$. Thus the determinant is given by equation~\eqref{equation_determinant_subset1}. \end{proof} \section{A pair of identities of Carlitz} \label{section_another_identity_from_Carlitz} In this section we turn our attention to two identities of Carlitz. Observe that setting $q=1$ in Theorems~\ref{theorem_Carlitz_funny_q_1} and~\ref{theorem_Carlitz_funny_q_2} in this section does not yield any information about the Stirling number $S(n,k)$ of the second kind. We first prove a theorem from which Carlitz's Theorem~\ref{theorem_Carlitz_funny_q_1} will follow. \begin{theorem} For two non-negative integers $n$ and $k$ not both equal to $0$, the following identity holds: \begin{equation} (1-q)^{n-k} \cdot S_{q}[n,k] = \sum_{j=0}^{n-k} (-q)^{j} \cdot \binom{n-1}{n-k-j} \cdot \qchoose{j+k-1}{j}{q} . \label{equation_Stanton_Gould_Carlitz_preliminary} \end{equation} \label{theorem_Stanton_Gould_Carlitz_preliminary} \end{theorem} \begin{proof} For a word $u = u_{1} u_{2} \cdots u_{n}$ in $\rg{n}{k}$ let $\NLRM(u)$ be the set of all positions~$r$ such that the letter $u_{r}$ is not a left-to-right-maxima of the word $u$, that is, $u_{r} \leq \max(u_{1}, u_{2}, \ldots, u_{r-1})$. Furthermore, for a position $r \in NLRM(u)$ define the bound $b(r)$ to be $\max(u_{1}, u_{2}, \ldots, u_{r-1})$. Note that $b(r)$ is the largest possible value we could change $u_{r}$ to be so that the resulting word remains an $RG$-word in $\rg{n}{k}$. To describe the left-hand side of~\eqref{equation_Stanton_Gould_Carlitz_preliminary}, consider the set of pairs $(u,P)$ where $u \in \rg{n}{k}$ and $P \subseteq \NLRM(u)$. Define the weight of such a pair $(u,P)$ to be $(-q)^{|P|} \cdot \wt(u)$. It is clear that the sum of the weight over all such pairs $(u,P)$ is given by the left-hand side of~\eqref{equation_Stanton_Gould_Carlitz_preliminary}. Define a sign-reversing involution as follows. For the pair $(u,P)$ pick the smallest position $r$ in $\NLRM(u)$ such that either $r \in P$ and $u_{r} \leq b(r)-1$ or $r \not\in P$ and $2 \leq u_{r}$. In the first case, send~$P$ to $P-\{r\}$ and replace the $r$th letter $u_{r}$ with $u_{r}+1$. In the second case, send $P$ to $P \cup \{r\}$ and replace the $r$th letter $u_{r}$ with $u_{r}-1$. This is a sign-reversing involution which pairs terms having the same weight, but opposite signs. Furthermore, the remaining pairs $(u,P)$ satisfy for all positions $r \in \NLRM(u)$ either $r \in P$ and $u_{r} = b(r)$ or $r \not\in P$ and $u_{r} = 1$. We now sum the weight of these remaining pairs $(u,P)$. First select the cardinality~$j$ of the set~$P$. Note that $0 \leq j \leq n-k$ and that it yields a factor of $(-q)^{j}$. Second, select the positions $r$ of the non-left-right-maxima such that $r$ will not be in the set $P$ and $u_{r} = 1$. There will be $n-k-j$ such positions and they can be anywhere in the interval $[2,n]$, yielding $\binom{n-1}{n-k-j}$ possibilities. Third, select a weakly increasing word $z$ of length $j$ with letters from the set $[k]$. This will be the letters corresponding to the non-left-to-right-maxima such that their positions belong to set $P$. The $\ls$-weight of these letters will be the $q$-binomial coefficient $\qchoose{j+k-1}{j}{q}$. Fourth, insert into the word $z$ the letters of the left-to-right-maxima. There is a unique way to do this insertion. Finally, insert the~$1$'s corresponding to positions not in the set $P$, which were already been chosen by the binomial coefficient. \end{proof} Note that the above proof fails when $n=k=0$ since we are using that a non-empty $RG$-word must begin with the letter $1$, whereas the empty $RG$-word does not. The next identity is due to Carlitz~\cite[equation~(9)]{Carlitz}. It was stated by Gould~\cite[equation~(3.10)]{Gould}. As a warning to the reader, Gould's notation $S_{2}(n,k)$ for the $q$-Stirling number of the second kind is related to ours by $S_{2}(n,k) = S_{q}[n+k,n]$. This identity also appears in the paper of de M\'edicis, Stanton and White~\cite[equation~(3.3)]{de_Medicis_Stanton_White} using modern notation. \begin{theorem}[Carlitz, 1933] \label{theorem_Carlitz_funny_q_1} For two non-negative integers $n$ and $k$ the following identity holds: \begin{equation} (1-q)^{n-k} \cdot S_{q}[n,k] = \sum_{j=0}^{n-k} (-1)^{j} \cdot \binom{n}{k+j} \cdot \qchoose{j+k}{j}{q} . \label{equation_Stanton_Gould_Carlitz} \end{equation} \end{theorem} \begin{proof} When $n=k=0$ the statement is direct. It is enough to show that the right-hand sides of equations~\eqref{equation_Stanton_Gould_Carlitz_preliminary} and~\eqref{equation_Stanton_Gould_Carlitz} agree. We have \begin{align*} \sum_{j=0}^{n-k} & (-1)^{j} \cdot \binom{n-1}{n-k-j} \cdot q^{j} \cdot \qchoose{j+k-1}{j}{q} \\ & = \sum_{j=0}^{n-k} (-1)^{j} \cdot \binom{n-1}{n-k-j} \cdot \left( \qchoose{j+k}{j}{q} - \qchoose{j+k-1}{j-1}{q} \right) \\ & = \sum_{j=0}^{n-k} (-1)^{j} \cdot \binom{n-1}{n-k-j} \cdot \qchoose{j+k}{j}{q} - \sum_{j=1}^{n-k} (-1)^{j} \cdot \binom{n-1}{n-k-j} \cdot \qchoose{j+k-1}{j-1}{q} \\ & = \sum_{j=0}^{n-k} (-1)^{j} \cdot \binom{n-1}{n-k-j} \cdot \qchoose{j+k}{j}{q} - \sum_{j=0}^{n-k-1} (-1)^{j+1} \cdot \binom{n-1}{n-k-j-1} \cdot \qchoose{j+k}{j}{q} \\ & = \sum_{j=0}^{n-k} (-1)^{j} \cdot \binom{n}{n-k-j} \cdot \qchoose{j+k}{j}{q} . \end{align*} Here we used the Pascal recursion for the $q$-binomial coefficients in the first step, shifted $j$ to $j+1$ in the second sum in the third step, and applied the Pascal recursion for the binomial coefficients in the last step. \end{proof} The next identity is also due to Carlitz; see~\cite[equation~(8)]{Carlitz}. It is equivalent to the previous identity, but we provide a proof using $RG$-words. \begin{theorem}[Carlitz, 1933] \label{theorem_Carlitz_funny_q_2} For $n$ and $k$ two non-negative integers the following identity holds: $$ \qchoose{n}{k}{q} = \sum_{j=k}^{n} (q-1)^{j-k} \cdot \binom{n}{j} \cdot S_{q}[j,k] . $$ \end{theorem} \begin{proof} The right-hand side describes the following collection of triplets $(A, u, P)$ where $A$ is a subset of the set $[n]$, $u$ is a word in $\rg{|A|}{k}$ and $P$ is a subset of $\NLRM(u)$. Define the weight of the triple $(A, u, P)$ to be the product $(-1)^{j-k-|P|} \cdot q^{|P|} \cdot \wt(u)$. To better visualize the pair~$(A,u)$, define the word $w = w_{1} w_{2} \cdots w_{n}$ of length $n$ with the letters in the set $\{0\} \cup [k]$ as follows. Write $A$ as the increasing set $\{a_{1} < a_{2} < \cdots < a_{j}\}$ and let $w_{a_{r}} = u_{r}$. The remaining letters of $w$ are set to be~$0$, that is, if $i \not\in A$ let $w_{i} = 0$. Note that the word $w$ uniquely encodes the pair~$(A,u)$. Let $Q$ be the set $Q = \{a_{r} \: : \: r \in P\}$, that is, the set $Q$ encodes the subset $P$, where these non-left-to-right-maxima occur in the longer word $w$. Similar to the proof of Theorem~\ref{theorem_Stanton_Gould_Carlitz_preliminary} we define a sign-reversing involution by selecting the smallest $r \in \NLRM(w)$ such that $r \not\in Q$ and $w_{r} \geq 2$, or $r \in Q$ and $1 \leq w_{r} \leq b(r)-1$. In the first case decrease $w_{r}$ by $1$ and join $r$ to the subset $Q$. In the second case, increase~$w_{r}$ by~$1$ and remove~$r$ from $Q$. The remaining words $w$ satisfy the following: for a non-left-to-right-maxima $r$ such that $w_{r} \geq 1$ either $r \not\in Q$ and $w_{r} = 1$ both hold, or $r \in Q$ and $w_{r} = b(r)$ hold. On the remaining pairs $(w,Q)$ define yet again a sign-reversing involution. Let $i > a_{1}$ be the smallest index $i$ such that $w_{i} = 0$, or $w_{i} = 1$ and $i \not\in Q$. This involution replaces~$w_{i}$ with $1-w_{i}$. Note that this involution changes the sign. The pairs $(w,Q)$ which remain unmatched under this second involution are those where the word~$w$ is weakly increasing and the subset $Q$ consists of all non-left-to-right-maxima $r$ with $w_{r} \geq 1$. Note that the weight of the pair $(w,Q)$ is the weight $q^{|Q|} \cdot q^{\sum_{r \in Q} w_{r}-1} = q^{\sum_{r \in Q} w_{r}}$. Finally, the sum of the weights of these pairs is~$\qchoose{n}{k}{q}$. \end{proof} \section{An extension of Mercier's identities} \label{section_extension_of_Mercier} We simultaneously generalize two identities of Mercier by introducing a two parameter identity involving $q$-Stirling numbers. The proof of this identity depends on a different decomposition of $RG$-words. Let $([n]_{q})_{k}$ denote the $q$-analogue of the lower factorial, that is, $([n]_{q})_{k} = [n]_{q}!/[n-k]_{q}!$. Alternatively, one can expand it as the product $$ ([n]_{q})_{k} = [n]_{q} \cdot [n-1]_{q} \cdots [n-k+1]_{q} . $$ \begin{theorem} For three non-negative integers $n$, $r$ and $s$ such that $s < r \leq n$ the following holds: \begin{align} \sum_{k=r}^{n} (-q^{s})^{k-r} \cdot ([k-s-1]_{q})_{k-r} \cdot S_{q}[n,k] & = \sum_{i=r-1}^{n-1} S_{q}[i,r-1] \cdot [s]_{q}^{n-i-1} . \label{equation_two_parameters} \end{align} \label{theorem_two_parameters} \end{theorem} \begin{proof} On the set of $RG$-words $S = \bigcupdotalt_{r \leq k \leq n} \rg{n}{k}$ define a weight function by $$ f(w) = (-q^{s})^{k-r} \cdot ([k-s-1]_{q})_{k-r} \cdot \wt(w). $$ Our objective is to evaluate the sum $\sum_{w \in S} f(w)$, which is the left-hand side of~\eqref{equation_two_parameters}. We do this in two steps. First we will partition the set $S$ into blocks and extend the weight~$f$ to a block $B$ by $f(B) = \sum_{w \in B} f(w)$. Secondly, on the set of blocks we will define a sign-reversing involution such that if two blocks $B$ and $C$ are matched, their $f$-weights cancel, that is, $f(B) + f(C) = 0$. Hence the right-hand side of~\eqref{equation_two_parameters} will be equal to the sum over all the blocks that have not been matched. We now define an equivalence relation on the set $S$. The blocks of our partition will be the equivalence classes. For any integer $k$ where $r \leq k \leq n$, we say two words $u, v \in \rg{n}{k}$ are equivalent if there exists an index $i$ such that $s+1 \leq u_{i}, v_{i} \leq k$ and $u = x \cdot u_{i} \cdot y$, $v = x \cdot v_{i} \cdot y$ for some word $x \in \rg{i-1}{k}$ and $y$ a word in $[1,s]^{*}$. Note that when $s=0$ that $y$ is the empty word~$\epsilon$. If a word $v \in \rg{n}{k}$ is of the form $v = x \cdot k \cdot y$ for some $x \in \rg{i-1}{k-1}$ and $y \in [1,s]^{*}$, then this word is not equivalent to any other words and hence it belongs to a singleton block. Since for any $RG$-word we can find a decomposition described as above, this is a partition of the set $\rg{n}{k}$ and hence the set $S$. Match the singleton block $B = \{x \cdot k \cdot y\}$ where $x \in \rg{i-1}{k-1}$, $y \in [1,s]^{*}$ and $r < k$ with the block $$ C = \{x \cdot j \cdot y \: : \: s+1 \leq j \leq k-1\}. $$ It is straightforward to check that $C \subseteq \rg{n}{k-1} \subseteq S$. Note that the weight $\wt(x \cdot j \cdot y)$ factors as $\wt(x) \cdot q^{j-1} \cdot \ls(y)$. Moreover, the $f$-weight of the block $C$ satisfies \begin{align} \label{equation_Stirling_f_weight} \nonumber f(C) & = \sum_{j=s+1}^{k-1} (-q^{s})^{k-r-1} \cdot ([k-s-2]_{q})_{k-r-1} \cdot \wt(x) \cdot q^{j-1} \cdot \ls(y) \nonumber \\ & = (-q^{s})^{k-r-1} \cdot ([k-s-2]_{q})_{k-r-1} \cdot \wt(x) \cdot q^{s} \cdot [k-s-1]_{q} \cdot \ls(y) \nonumber \\ & = - (-q^{s})^{k-r} \cdot ([k-s-1]_{q})_{k-r} \cdot \wt(x) \cdot \ls(y) \nonumber \\ & = -f(x \cdot k \cdot y). \end{align} Hence the weight of the two blocks $B$ and $C$ cancel each other. It remains to determine the weight of the unmatched blocks. Observe that every block of the form $\{x \cdot j \cdot y : s+1 \leq j \leq k\}$ where $x \in \rg{i}{k}$ and $y \in [1,s]^{*}$ has been matched by the above construction. Hence the unmatched blocks are singleton blocks. Given a word $u \in \rg{n}{k} \subseteq S$, it has a unique factorization as $u = x \cdot j \cdot y$ where $y \in [1,s]^{*}$ and $s < j$. If $x$ is a word in $\rg{i}{k}$ then the word $u$ belongs to a block that has been matched. If $x \in \rg{i}{k-1}$ then $m = k$ and the word $u$ belongs to a singleton block which has been matched if $k > r$. Hence the unmatched blocks are of the form $\{x \cdot r \cdot y\}$ where $x \in \rg{i}{r-1}$ and $y \in [1,s]^{n-i-1}$. The sum of their $f$-weights are \begin{align*} \sum_{i=r-1}^{n-1} \sum_{\substack{x \in \rg{i}{r-1} \\ y \in [1,s]^{n-i-1}}} f(x \cdot r \cdot y) & = \sum_{i=r-1}^{n-1} \sum_{\substack{x \in \rg{i}{r-1} \\ y \in [1,s]^{n-i-1}}} \wt(x) \cdot \ls(y) \\ & = \sum_{i=r-1}^{n-1} S_{q}[i,r-1] \cdot [s]_{q}^{n-i-1} , \end{align*} which is the right-hand side of the desired identity. \end{proof} Setting $(r,s) = (1,0)$ and $(r,s) = (2,1)$ in Theorem~\ref{theorem_two_parameters} we obtain two special cases, both of which are due to Mercier~\cite[Theorem~2]{Mercier_q_identities}. The second identity is a $q$-analogue of a result due to Jordan~\cite[equation~5, page~186]{Jordan}. \begin{corollary}[Mercier, 1990] \label{corollary_Mercier_involution} For $n \geq 2$, the following two identities hold: \begin{align} \sum_{k=1}^{n} (-1)^k \cdot [k-1]_{q}! \cdot S_{q}[n,k] & = 0, \label{equation_Mercier_1}\\ \sum_{k=2}^{n} (-1)^k \cdot q^{k-2} \cdot [k-2]_{q}! \cdot S_{q}[n,k] & = n-1. \label{equation_Mercier_2} \end{align} \end{corollary} \noindent Mercier's identity~\eqref{equation_Mercier_2} reappears in work of Ernst~\cite[Corollary~3.30]{Ernst}. The next result is the case $r = s+1$ in Theorem~\ref{theorem_two_parameters}. Here we provide a different expression. \begin{proposition} The following identity holds: \begin{multline} \sum_{k=r}^{n} (-q^{r-1})^{k-r} \cdot ([k-r]_{q})_{k-r} \cdot S_{q}[n,k] = \\ \sum_{c_{1} + c_{2} \plusdots c_{r-1} = n-r+1} c_{r-1} \cdot [1]_{q}^{c_{1}} \cdot [2]_{q}^{c_{2}} \cdots [r-2]_{q}^{c_{r-2}} \cdot [r-1]_{q}^{c_{r-1}-1} . \label{equation_long} \end{multline} \label{proposition_long} \end{proposition} \begin{proof} The $f$-weights of the unmatched words $u = x \cdot r \cdot y$ in the proof of Theorem~\ref{theorem_two_parameters} can be determined in a different manner. Since $x \in \rg{i}{r-1}$ we can factor $x$ according to equation \eqref{equation_expansion}. Hence the unmatched word $u$ has the form $$ u = 1 \cdot x_{1} \cdot 2 \cdot x_{2} \cdot 3 \cdots (r-1) \cdot x_{r-1} \cdot r \cdot y, $$ where $x_{i}$ belongs to $[1,i]^{*}$ and $y$ belongs to $[1,r-1]^{*}$. All possible words $x_{i}$ of length~$c_{i}$ give total weight of $[i]_{q}^{c_{i}}$ for $i \leq r-2$. For the word $x_{r-1} \cdot r \cdot y$, suppose its length is $c_{r-1}$. Then we have $c_{r-1}$ choices to place the letter~$r$ and the total weight of such words of the form $x_{r-1} \cdot y$ will be $[r-1]_{q}^{c_{r-1}-1}$. Hence the $f$-weight for unmatched words is given by equation~\eqref{equation_long}. \end{proof} Recall the Stirling numbers of the second kind are specializations of the homogeneous symmetric function; see equation~\eqref{equation_complete_symmetric_functions}. Thus one can view Theorem~\ref{theorem_two_parameters} from a symmetric function perspective. \begin{theorem} The following polynomial identity holds: \begin{align*} \sum_{i=0}^{n-r} h_{i}(x_{1}, x_{2},\ldots, x_{r-1})\cdot x_{s}^{n-r-i} = & \sum_{k=r}^{n} (x_{s}-x_{r})\cdot (x_{s}-x_{r+1})\cdots (x_{s}-x_{k-1})\\ & \:\:\:\: \:\:\: \cdot h_{n-k}(x_{1}, x_{2}, \ldots, x_{k}). \end{align*} \label{theorem_x} \end{theorem} \begin{proof} Let $[t^{n}]f(t)$ denote the coefficient of $t^{n}$ in $f(t)$. We consider the function $$ G_{r}(t) = \frac{1}{1-x_{s}\cdot t} \cdot \prod_{j=1}^{r-1} \frac{1}{1-x_{j}\cdot t} = \prod_{j=1}^{r} \frac{1}{1-x_{j}\cdot t} + \frac{(x_{s}-x_{r})\cdot t}{1-x_{s}\cdot t} \cdot \prod_{j=1}^{r} \frac{1}{1-x_{j}\cdot t}, $$ and compute the coefficient of $t^{n-r}$ in two ways. Using the first expression of $G_{r}(t)$ and that $$ \frac{1}{1-x_{s}\cdot t} = \sum_{i\geq 0} x_{s}^{i} \cdot t^{i} \;\; \text{ and } \;\; \prod_{j=1}^{r-1} \frac{1}{1-x_{j}\cdot t} = \sum_{i \geq 0} h_{i}(x_{1}, x_{2},\ldots, x_{r-1})\cdot t^{i}, $$ we obtain \begin{equation} [t^{n-r}]G_{r}(t) = \sum_{i=0}^{n-r} h_{j}(x_{1}, x_{2}, \ldots, x_{r-1})\cdot x_{s}^{n-r-i}. \label{equation_symetric_one} \end{equation} Using the second expression of $G_{r}(t)$ we have \begin{align} \nonumber [t^{n-r}]G_{r}(t) &= [t^{n-r}] \prod_{j=1}^{r} \frac{1}{1-x_{j} \cdot t} + [t^{n-r}] \frac{(x_{s}-x_{r})\cdot t}{1-x_{s}\cdot t} \cdot \prod_{j=1}^{r} \frac{1}{1-x_{j}\cdot t} \\ &= h_{n-r}(x_{1}, x_{2}, \ldots, x_{r}) + (x_{s}-x_{r}) \cdot [t^{n-r-1}] G_{r+1}(t) . \label{equation_symmetric_iteration_one} \end{align} Iterate equation~\eqref{equation_symmetric_iteration_one} $n-r$ times yields \begin{equation} \label{equation_symmetric_two} [t^{n-r}]G_{r}(t) = \sum_{k=r}^{n} (x_{s}-x_{r})\cdot (x_{s}-x_{r+1}) \cdots (x_{s}-x_{k-1}) \cdot h_{n-k}(x_{1}, x_{2}, \ldots, x_{k}). \end{equation} Now combine equations~\eqref{equation_symetric_one} and~\eqref{equation_symmetric_two} we obtain the desired identity. \end{proof} \begin{proof} [Second proof of Theorem~\ref{theorem_two_parameters}.] Substituting $x_{i} = [i]_{q}$ in Theorem~\ref{theorem_x} yields the result using that $[s]_q - [i]_q = -q^{s} \cdot [i-s]_q$ when $i > s \geq 0$. \end{proof} \section{Concluding remarks} There are many extensions of $q$-Stirling numbers of the second kind. Remmel and Wachs~\cite{Remmel_Wachs} develop $(p,q)$-analogues of $q$-Stirling numbers of the first and second kinds, and give a colored restricted growth word interpretation of Hsu and Shiue's generalized Stirling numbers~\cite{Hsu_Shiue}. An earlier two-parameter $(p,q)$-Stirling number of the second kind by Wachs and White~\cite{Wachs_White} include interpretations via rook placements and restricted growth functions. What identities arise in these settings? As an example, Briggs and Remmel~\cite{Briggs_Remmel} have a $(p,q)$-analogue of Garsia and Remmel's $q$-Frobenius formula (Theorem~\ref{theorem_Frobenius}) via three statistics: number of descents, major index and comajor index. One can also be interested in other applications of restricted growth words. See the recent paper of Ehrenborg, Hedmark and Hettle for an application to partitions with block sizes of the same parity~\cite{Ehrenborg_Hedmark_Hettle}, as well as Steingr\'{i}msson's new statistics on ordered set partitions~\cite{Steingrimsson} and the related papers by Ishikawa, Kasraoui and Zeng~\cite{Ishikawa_Kasraoui_Zeng,Kasraoui_Zeng}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} The authors thank Dennis Stanton for directing us to the pair of identities of Carlitz discussed in Section~\ref{section_another_identity_from_Carlitz}. The authors would also like to thank the Princeton University Mathematics Department for its hospitality and support. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/math/#1}{\texttt{arXiv:#1}}} \newcommand{\arxivref}[4]{{#1,} #2, \arxiv{#3} #4.} \newcommand{\journal}[6]{{#1,} #2, {\it #3} {\bf #4} (#5), #6.} \newcommand{\book}[4]{{#1,} ``#2,'' #3, #4.} \newcommand{\bookf}[5]{{#1,} ``#2,'' #3, #4, #5.} \newcommand{\books}[6]{{#1,} ``#2,'' #3, #4, #5, #6.} \newcommand{\collection}[6]{{#1,} #2, #3, in {\it #4}, #5, #6.} \newcommand{\thesis}[4]{{#1,} ``#2,'' Doctoral dissertation, #3, #4.} \newcommand{\springer}[4]{{#1,} ``#2,'' Lecture Notes in Math., Vol.\ #3, Springer-Verlag, Berlin, #4.} \newcommand{\preprint}[3]{{#1,} #2, preprint #3.} \newcommand{\preparation}[2]{{#1,} #2, in preparation.} \newcommand{\appear}[3]{{#1,} #2, to appear in {\it #3}} \newcommand{\submitted}[3]{{#1,} #2, submitted to {\it #3}} \newcommand{\JCTA}{J.\ Combin.\ Theory Ser.\ A} \newcommand{\AdvancesinMathematics}{Adv.\ Math.} \newcommand{\JournalofAlgebraicCombinatorics}{J.\ Algebraic Combin.} \newcommand{\communication}[1]{{#1,} personal communication.} % \newpage \begin{thebibliography}{99} \bibitem{Briggs_Remmel} \journal{K.\ Briggs and J.\ Remmel} {A $p, q$-analoque of a formula of Frobenius} {Electron.\ J.\ Combin.} {10}{2003}{Research Paper 9, 26 pp} \bibitem{Cai_Readdy} \journal{Y.\ Cai and M.\ Readdy} {$q$-Stirling numbers: A new view} {Adv. in Appl.\ Math.}{86}{2017}{50--80} \bibitem{Carlitz} \journal{L.\ Carlitz} {On abelian fields} {Trans.\ Amer.\ Math.\ Soc.} {35}{1933}{122--136} \bibitem{Carlitz_identity} \journal{L.\ Carlitz} {$q$-Bernoulli numbers and polynomials} {Duke Math.\ J.} {15}{1948}{987--1000} \bibitem{Chen} \journal{W.\ Y.\ C.\ Chen} {Context-free grammars, differential operators and formal power series} {Theoret.\ Comput.\ Sci.} {117}{1993}{113--129} \bibitem{Comtet} \book{L.\ Comtet} {Advanced Combinatorics} {The art of finite and infinite expansions. Revised and enlarged edition, D. Reidel Publishing Company} {1974} \bibitem{de_Medicis_Leroux_unified} \journal{A.\ de M\'edicis and P.\ Leroux} {A unified combinatorial approach for $q$- (and $p,q$-) Stirling numbers} {J.\ Statist.\ Plann.\ Inference} {34}{1993}{89--105} \bibitem{de_Medicis_Leroux_convolution} \journal{A.\ de M\'edicis and P.\ Leroux} {Generalized Stirling numbers, convolution formulae and $p,q$-analogues} {Canad.\ J.\ Math.} {47}{1995}{474--499} \bibitem{de_Medicis_Stanton_White} \journal{A.\ de M\'edicis, D.\ Stanton and D.\ White} {The combinatorics of $q$-Charlier polynomials} {J.\ Combin.\ Theory Ser. A} {69}{1995}{87--114} \bibitem{Ehrenborg_determinants} \journal{R.\ Ehrenborg} {Determinants involving $q$-Stirling numbers} {Adv.\ in Appl.\ Math.} {31}{2003}{630--642} \bibitem{Ehrenborg_Hedmark_Hettle} \journal{R.\ Ehrenborg, D.\ Hedmark and C.\ Hettle} {A restricted growth word approach to partitions with odd/even size blocks} {J.\ Integer Seq.} {20}{2017}{Article 17.5.5, 7 pp} \bibitem{Ehrenborg_Readdy_juggling} \journal{R.\ Ehrenborg and M.\ Readdy} {Juggling and applications to $q$-analogues} {Discrete Math.} {157}{1996}{107--125} \bibitem{Ernst} \journal{T.\ Ernst} {$q$-Stirling numbers, an umbral approach} {Adv.\ Dyn.\ Syst.\ Appl.} {3}{2008}{251-–28} \bibitem{Garsia_Remmel} \journal{A.\ M.\ Garsia and J.\ B.\ Remmel} {Q-counting rook configurations and a formula of Frobenius} {\JCTA} {41}{1986}{246--275} \bibitem{Gould} \journal{H.\ W.\ Gould} {The $q$-Stirling numbers of the first and second kinds} {Duke Math.\ J.} {28}{1961}{281--289} \bibitem{Hsu_Shiue} \journal{L.\ C.\ Hsu and P.\ J-S Shiue} {A unified approach to generalized Stirling numbers} {Adv.\ in Appl.\ Math.} {20}{1998}{366--384} \bibitem{Ishikawa_Kasraoui_Zeng} \journal{M.\ Ishikawa, A.\ Kasraoui and J.\ Zeng} {Euler-Mahanonian statistics on ordered set partitions} {SIAM J.\ Discrete Math.} {22}{2008}{1105--1137} \bibitem{Jordan} \book{C.\ Jordan} {Calculus of Finite Differences. Second edition} {Chelsea Publishing Company, New York}{1947} \bibitem{Kaplansky_Riordan} \journal{I.\ Kaplansky and J.\ Riordan} {The problem of the rooks and its applications} {Duke Math.\ J.} {13}{1946}{259--268} \bibitem{Kasraoui_Zeng} \journal{A.\ Kasraoui and J.\ Zeng} {Euler-Mahanonian statistics on ordered set partitions (II)} \JCTA {116}{2009}{539--563} \bibitem{Leroux} \journal{P.\ Leroux} {Reduced matrices and $q$-log-concavity properties of $q$-Stirling numbers} {\JCTA} {54}{1990}{64--84} \bibitem{Macdonald} \book{I.\ G.\ Macdonald} {Symmetric Functions and Hall Polynomials. Second edition} {Oxford Mathematical Monographs. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York} {1995} \bibitem{Mercier_q_identities} \journal{A.\ Mercier} {Quelques identit\'{e}s pour les $q$-analogues} {Utilitas Math.} {38}{1990}{33--41} \bibitem{Milne_restricted} \journal{S.\ Milne} {Restricted growth functions and incidence relations of the lattice of partitions of an $n$-set} {Adv.\ in Math.} {26}{1977}{290--305} \bibitem{Milne_q_analog} \journal{S.\ Milne} {A $q$-analog of restricted growth functions, Dobinski's equality, and Charlier polynomials} {Trans.\ Amer.\ Math.\ Soc.} {245}{1978}{89--118} \bibitem{Milne_restricted_rank_row} \journal{S.\ Milne} {Restricted growth functions, rank row matchings of partition lattices, and $q$-Stirling numbers} {Adv.\ in Math.} {43}{1982}{173--196} \bibitem{Remmel_Wachs} \journal{J.\ Remmel and M.\ Wachs} {Rook theory, generalized Stirling numbers and $(p,q)$-analogues} {Electron.\ J.\ Combin.} {11}{2004}{Research Paper 84, 48 pp} \bibitem{Rota} \journal{G.-C.\ Rota} {The number of partitions of a set} {Amer.\ Math.\ Monthly} {71}{1964}{498--504} \bibitem{Stanley_EC_I} \book{R.\ P.\ Stanley} {Enumerative Combinatorics, Vol. I, 2nd edition} {Cambridge Studies in Advanced Mathematics (No.\ 49), Cambridge University Press} {2012} \bibitem{Steingrimsson} \arxivref{E.\ Steingr\'{\i}msson} {Statistics on ordered partitions of sets} {0605670}{[math.CO], 2014} \bibitem{Stirling} {J.\ Stirling}, ``Methodus Differentialis: sive Tractatus de Summatione et Interpolatione Serierum Infinitarum,'' Londini, 1730. \bibitem{Verde-Star} \journal{L.\ Verde-Star} {Interpolation and combinatorial functions} {Stud.\ Appl.\ Math.} {79}{1988}{65--92} \bibitem{Verde-Star_transformation} \journal{L.\ Verde-Star} {Transformation formulas for complete symmetric polynomials and identities for generalized binomial coefficients and $q$-Stirling numbers} {Discrete Math.} {312}{2012}{2197--2202} \bibitem{Wachs_White} \journal{M.\ Wachs and D.\ White} {$p$, $q$-Stirling numbers and set partition statistics} {\JCTA} {56}{1991}{27--46} \bibitem{White} \journal{D.\ White} {Interpolating set partition statistics} {\JCTA} {68}{1994}{262--295} \end{thebibliography} \end{document}