\documentclass[12pt]{article} \usepackage{e-jc} \specs{P5}{19(3)}{2012} \usepackage{amsthm,amsmath,amssymb,latexsym} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{prop}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \numberwithin{equation}{section} \newcommand{\FF}{\mathbb{F}} \newcommand{\be}{\mathbf{e}} \newcommand{\bm}{\mathbf{m}} \newcommand{\ulk}{\underline{k}} \newcommand{\ule}{\underline{e}} \newcommand{\tH}{\tilde{H}} \newcommand*{\subst}[2]{\genfrac{}{}{0pt}{}{#1}{#2}} \title{An enumeration of flags in finite vector spaces} \author{C. Ryan Vinroot\thanks{Supported by NSF grant DMS-0854849.}\\ \small Department of Mathematics\\[-0.8ex] \small College of William and Mary\\[-0.8ex] \small P. O. Box 8795\\[-0.8ex] \small Williamsburg, VA 23187\\ \small\tt vinroot@math.wm.edu\\ } \date{\dateline{Feb 2, 2012}{Jun 27, 2012}{Jul 12, 2012}\\ \small Mathematics Subject Classifications: 05A19, 05A15, 05A30} \begin{document} \bibliographystyle{plain} \maketitle \begin{abstract} By counting flags in finite vector spaces, we obtain a $q$-multinomial analog of a recursion for $q$-binomial coefficients proved by Nijenhuis, Solow, and Wilf. We use the identity to give a combinatorial proof of a known recurrence for the generalized Galois numbers. \end{abstract} \section{Introduction} For a parameter $q \neq 1$, and a positive integer $n$, let $(q)_n = (1 - q)(1 - q^2) \cdots (1-q^{n})$, and $(q)_0 = 1$. For non-negative integers $n$ and $k$, with $n \geq k$, the {\em $q$-binomial coefficient} or {\em Gaussian polynomial}, denoted $\binom{n}{k}_q$, is defined as $\binom{n}{k}_q = \frac{(q)_n}{(q)_k (q)_{n-k}}$. The {\em Rogers-Szeg\"o polynomial} in a single variable, denoted $H_n(t)$, is defined as $$ H_n(t) = \sum_{k = 0}^n \binom{n}{k}_q t^k.$$ The Rogers-Szeg\"o polynomials first appeared in papers of Rogers \cite{Rog1, Rog2} which led up to the famous Rogers-Ramanujan identities, and later were independently studied by Szeg\"o \cite{Sz26}. They are important in combinatorial number theory (\cite[Ex. 3.3--3.9]{An76} and \cite[Sec. 20]{Fi88}), symmetric function theory \cite{Wa06}, and are key examples of orthogonal polynomials \cite{AsWi85}. They also have applications in mathematical physics \cite{Ka06, Ma89}. The Rogers-Szeg\"o polynomials satisfy the recursion (see \cite[p. 49]{An76}) \begin{equation} \label{RogSze} H_{n+1}(t) = (1+t)H_n(t) + t(q^n - 1)H_{n-1}(t). \end{equation} Letting $t=1$, we have $H_n(1) = \sum_{k = 0}^n \binom{n}{k}_q$, which, when $q$ is the power of a prime, is the total number of subspaces of an $n$-dimensional vector space over a field with $q$ elements. The numbers $G_n = H_n(1)$ are the \emph{Galois numbers}, and from (\ref{RogSze}), satisfy the recursion \begin{equation} \label{GaloisGoRo} G_{n+1} = 2G_n + (q^n - 1)G_{n-1}. \end{equation} The Galois numbers were studied from the point of view of finite vector spaces by Goldman and Rota \cite{GoRo69}, and have been studied extensively elsewhere, for example, in \cite{NiSoWi84, HiHo10}. In particular, Nijenhuis, Solow, and Wilf \cite{NiSoWi84} give a bijective proof of the recursion (\ref{GaloisGoRo}) using finite vector spaces, by proving, for integers $n \geq k \geq 1$, \begin{equation} \label{GalLemma} \binom{n+1}{k}_q = \binom{n}{k}_q + \binom{n}{k-1}_q + (q^n - 1) \binom{n-1}{k-1}_q. \end{equation} For non-negative integers $k_1, k_2, \ldots, k_m$ such that $k_1 + \cdots + k_m = n$, we define the $q$-multinomial coefficient of length $m$ as $$ \binom{n}{k_1, k_2, \ldots, k_m}_q = \frac{(q)_n}{(q)_{k_1} (q)_{k_2} \cdots (q)_{k_m}},$$ so that $\binom{n}{k}_q = \binom{n}{k, n-k}_q$. If $\underline{k}$ denotes the $m$-tuple $(k_1, \ldots, k_m)$, write the corresponding $q$-multinomial coefficient as $\binom{n}{k_1, \ldots, k_m}_q = \binom{n}{\ulk}_q$. For a subset $J \subseteq \{ 1, \ldots, m \}$, let $\ule_J$ denote the $m$-tuple $(e_1, \ldots, e_m)$, where $$ e_i = \left\{ \begin{array}{ll} 1 & \text{ if $i \in J$,} \\ 0 & \text{ if $i \not\in J$.} \end{array} \right.$$ For example, if $m = 3$, $J = \{1, 3\}$, and $\ulk = (k_1, k_2, k_3),$ then $\binom{n}{\ulk - \ule_J}_q = \binom{n}{k_1 -1, k_2, k_3 - 1}_q$. The main result of this paper, which is obtained in Section \ref{flags}, Theorem \ref{GenGalLemma}, is a combinatorial proof through enumerating flags in finite vectors spaces of the following generalization of the identity (\ref{GalLemma}). For $m \geq 2$, and any $k_1, \ldots, k_m > 0$ such that $k_1 + \cdots + k_m = n+1$, we have $$ \binom{n+1}{k_1, \ldots, k_m}_q = \sum_{J \subseteq \{1, \ldots, m\}, |J| > 0} (-1)^{|J| - 1} \frac{(q)_{n}}{(q)_{n - |J| + 1}} \binom{n + 1 - |J|}{\ulk - \ule_J}_q.$$ In Section \ref{Galois}, we prove a recursion which generalizes (\ref{GaloisGoRo}). In particular, the generalized Galois number $G_n^{(m)}$ is defined as $$G_n^{(m)} = \sum_{k_1 + \cdots + k_m = n} \binom{n}{k_1, k_2, \ldots, k_m}_q,$$ which, in the case that $q$ is the power of a prime, enumerates the total number of flags of length $m-1$ of an $n$-dimensional $\FF_q$-vector space. Quite recently, the asymptotic statistics of these generalized Galois numbers have been studied by Bliem and Kousidis \cite{BlKo11} and Kousidis \cite{Ko11}. Directly following from Theorem \ref{GenGalLemma}, we prove in Theorem \ref{GenGalRecThm} that, for $n \geq m-1$, $$G_{n+1}^{(m)} = \sum_{i=0}^{m-1} \binom{m}{i+1} (-1)^i \frac{(q)_n}{(q)_{n-i}}G_{n-i}^{(m)},$$ which also follows from a known recurrence for the multivariate Rogers-Szeg\"o polynomials. \section{Flags in finite vector spaces} \label{flags} In this section, let $q$ be the power of a prime, and let $\FF_q$ denote a finite field with $q$ elements. If $V$ is an $n$-dimensional vector space over $\FF_q$, then the $q$-binomial coefficient $\binom{n}{k}_q$ is the number of $k$-dimensional subspaces of $V$ (see \cite[Thm. 7.1]{KaCh02} or \cite[Prop. 1.3.18]{St97}). So, the Galois number $$ G_n = H_n(1) = \sum_{k=0}^n \binom{n}{k}_q,$$ is the total number of subspaces of an $n$-dimensional vector space over $\FF_q$. Now consider the $q$-multinomial coefficient in terms of vector spaces over $\FF_q$. It follows from the definition of a $q$-multinomial coefficient and the fact that $\binom{n}{k}_q = \binom{n}{n-k}_q$ that we have \begin{align*} \binom{n}{k_1, k_2, \ldots, k_m}_q & = \binom{n}{k_1}_q \binom{n-k_1}{k_2}_q \cdots \binom{n-k_1-\cdots - k_{m-2}}{k_{m-1}}_q\\ & = \binom{n}{n-k_1}_q \binom{n-k_1}{n-k_1-k_2}_q \cdots \binom{n-k_1 - \cdots -k_{m-2}}{n-k_1 -\cdots -k_{m-2} - k_{m-1}}_q. \end{align*} So, if $V$ is an $n$-dimensional vector space over $\FF_q$, the $q$-multinomial coefficient $\binom{n}{k_1, \ldots, k_m}_q$ is equal to the number of ways to choose an $(n-k_1)$-dimensional subspace $W_1$ of $V$, an $(n-k_1 -k_2)$-dimensional subspace $W_2$ of $W_1$, and so on, until finally we choose an $(n-k_1-\cdots -k_{m-1})$-dimensional subspace $W_{m-1}$ of some $(n-k_1 - \cdots -k_{m-2})$-dimensional subspace $W_{m-2}$ (see also \cite[Sec. 1.5]{Mo06}). That is, $$W_{m-1} \subseteq W_{m-2} \subseteq \cdots \subseteq W_2 \subseteq W_1$$ is a {\em flag} of subspaces of $V$ of length $m-1$, where ${\rm dim} \; W_i = n - \sum_{j=1}^i k_j$. We now turn to a bijective proof of the identity (\ref{GalLemma}), that for integers $n \geq k \geq 1$, $$\binom{n+1}{k}_q = \binom{n}{k}_q + \binom{n}{k-1}_q + (q^n-1)\binom{n-1}{k-1}_q.$$ While the bijective interpretation of this identity which we give now is different from the proof given by Nijenhuis, Solow, and Wilf in \cite{NiSoWi84}, it is the interpretation which is most helpful for the proof of our main result. Fix $V$ to be an $(n+1)$-dimensional $\FF_q$-vector space. There are $\binom{n+1}{k}_q$ ways to choose a $k$-dimensional subspace $W$ of $V$. Fix a basis $\{v_1, v_2, \ldots, v_{n+1}\}$ of $V$. Any $k$-dimensional subspace $W$ can be written as $\mathrm{span}(W', v)$ where $W'$ is a $(k-1)$-dimensional subspace of $V' = \mathrm{span}(v_1, \ldots, v_n)$, for some $v$. We may choose $W$ in three distinct ways. If $v \in V'$, then $W$ is a subspace of $V'$, for which there are $\binom{n}{k}_q$ choices. Call this a \emph{type 1} subspace of $V$. If $v_{n+1}\in W$, then we may take $v = v_{n+1}$, and $W$ is determined by $W'$, for which there are $\binom{n}{k-1}_q$ choices. We call this a \emph{type 2} subspace of $V$. Finally, if both $W \not\subset V'$ and $v_{n+1} \not\in W$, then we call $W$ a \emph{type 3} subspace of $V$, and it follows from (\ref{GalLemma}) (and can be shown directly, as well) that there are $(q^n-1)\binom{n-1}{k-1}_q$ choices for $W$. We may now prove our main result. \begin{theorem} \label{GenGalLemma} For $m \geq 2$, and any $k_1, \ldots, k_m > 0$ such that $k_1 + \cdots + k_m = n+1$, we have $$ \binom{n+1}{k_1, \ldots, k_m}_q = \sum_{J \subseteq \{1, \ldots, m\}, |J| > 0} (-1)^{|J| - 1} \frac{(q)_{n}}{(q)_{n - |J| + 1}} \binom{n + 1 - |J|}{\ulk - \ule_J}_q$$ \end{theorem} \begin{proof} Fix $V$ to be an $(n+1)$-dimensional vector space over $\FF_q$. Fix a basis of each subspace $U$ of $V$, so that we may speak of subspaces of type 1, 2, or 3 of each subspace $U$ with respect to this fixed basis. Consider a flag $F$ of subspaces of $V = W_0$, $W_{m-1} \subset \cdots \subset W_2 \subset W_1$, such that if we define $k_i$ for $1 \leq i \leq m$ by $\sum_{j=1}^i k_j = n + 1 - {\rm dim} \; W_i$, then each $k_i > 0$. The total number of such flags is $\binom{n+1}{k_1, \ldots, k_m}_q$. Consider now a labeling of such flags in the following way. Given a flag $F$ as above, define $$r = \mathrm{min} \{ 1 \leq j \leq m \, \mid \, W_j \text{ is a type 1 subspace of } W_{j-1} \},$$ and $$J = \{r \} \cup \{ 1 \leq j \leq r-1 \, \mid \, W_j \text{ is a type 3 subspace of } W_{j-1} \}.$$ Define the flag $F$ to be a \emph{type $J$ flag} of $V$. That is, for any nonempty $J \subseteq \{ 1, \ldots, m \}$, we may speak of flags of type $J$ of $V$. We shall prove that \begin{equation} \label{subcount} (-1)^{|J| - 1} \frac{(q)_{n}}{(q)_{n - |J| + 1}} \binom{n + 1 - |J|}{\ulk - \ule_J}_q \end{equation} is the number of type $J$ flags of length $m-1$ of the $\FF_q$-space $V$. Once this claim is proven, we will have accounted for all $2^m - 1$ terms on the right-side of the desired result of Theorem \ref{GenGalLemma}, and all possible ways to choose our flag. We prove the claim by induction on $m$, where the base case of $m=2$ follows from (\ref{GalLemma}) and its interpretation in terms of subspaces of types 1, 2, and 3, as given above. We must consider each possible nonempty $J \subseteq \{1,\ldots,m\}$, and show that in each case, the quantity (\ref{subcount}) counts the number of type $J$ flags. So, consider a flag of subspaces $W_{m-1} \subset \cdots \subset W_2 \subset W_1$ of $V$, where ${\rm dim} \; W_i = n + 1 - \sum_{j=1}^i k_j$. First, if $J = \{ 1\}$, then the number of ways to choose $W_1$ to be a type 1 subspace of $V$ of dimension $n+1 - k_1$ is $\binom{n}{n+1-k_1}_q$, while the number of ways to choose the remaining length $m-2$ flag $W_{m-1} \subset \cdots \subset W_2$ of $W_1$ is exactly $\binom{n+1-k_1}{k_2, \ldots, k_m}_q$. Thus, the total number of ways to choose our flag of type $J$ with $J= \{1\}$ is $\binom{n}{n+1-k_1}_q \binom{n+1-k_1}{k_2, \ldots, k_m}_q = \binom{n}{k_1-1, k_2, \ldots, k_m}_q$, which is exactly the expression (\ref{subcount}) for $J = \{1\}$, as claimed. So, we now suppose $J \neq \{ 1 \}$, so if $r$ is the maximum element of $J$, we have $r > 1$. We consider the cases of whether $1 \in J$ or $1 \not\in J$ separately. Suppose that $1 \not\in J$. Then, we must choose our flag so that $W_1$ is a type 2 subspace of $V$, of which there are $\binom{n}{n-k_1}_q$ such subspaces. Now, if we define $I= J - 1 = \{j - 1 \, \mid \, j \in J \}$, so that $I \subset \{1, \ldots, m-1 \}$ and $|I| = |J|$, we must choose the rest of our type $J$ flag of $V$ by choosing a type $I$ flag of $W_1$ of length $m-2$. If we let $\ulk' = (k_2, \ldots, k_m)$, then by our induction hypothesis, the number of type $I$ flags of length $m-2$ of the $(n+1-k_1)$-dimensional space $W_1$ is $$(-1)^{|I| - 1} \frac{(q)_{n-k_1}}{(q)_{n -k_1 - |I| + 1}} \binom{n + 1 - k_1 - |I|}{\ulk' - \ule_{I}}_q.$$ So, the total number of ways to choose the type $J$ flag of length $m-1$ in $V$ is $$\binom{n}{n-k_1}_q (-1)^{|I| - 1} \frac{(q)_{n-k_1}}{(q)_{n -k_1 - |I| + 1}} \binom{n + 1 - k_1 - |I|}{\ulk' - \ule_{I}}_q.$$ A direct computation yields $$\binom{n}{n-k_1}_q \frac{(q)_{n-k_1}}{(q)_{n - k_1 - |I| + 1}} = \frac{(q)_n}{(q)_{n - |I| + 1}} \binom{n+1 - |I|}{n - k_1 - |I| + 1}_q,$$ and further note that $$\binom{n+1 - |I|}{n - k_1 - |I| + 1}_q \binom{n + 1 - k_1 - |I|}{\ulk' - \ule_{I}}_q = \binom{n + 1 - |J|}{\ulk - \ule_J}_q,$$ where $\ulk = (k_1, \ldots, k_m)$. Together, these give \begin{align*} \binom{n}{n-k_1}_q (-1)^{|I| - 1} \frac{(q)_{n-k_1}}{(q)_{n -k_1 - |I| + 1}} & \binom{n + 1 - k_1 - |I|}{\ulk' - \ule_{I}}_q \\ & = (-1)^{|J| - 1} \frac{(q)_{n}}{(q)_{n - |J| + 1}} \binom{n + 1 - |J|}{\ulk - \ule_J}_q, \end{align*} giving the claim that when $1 \not\in J$, the number of type $J$ subspaces of length $m-1$ of $V$ is given by (\ref{subcount}). Finally, suppose that $1 \in J$, and $J \neq \{1\}$. So, we must choose our flag so that $W_1$ is a type 3 subspace of $V$, and there are $(q^n - 1) \binom{n-1}{n - k_1}_q$ such subspaces. If we let $I = (J-1) \setminus \{0\}$ (so that now $|J| = |I| + 1$), then we must choose the rest of our flag as a type $I$ flag of length $m-2$ of $W_1$. Letting again $\ulk' = (k_2, \ldots, k_m)$, then by our induction hypothesis, the total number of flags of type $J$ of length $m-1$ of $V$ is given by $$(q^n - 1) \binom{n-1}{n - k_1}_q (-1)^{|I| - 1} \frac{(q)_{n-k_1}}{(q)_{n -k_1 - |I| + 1}} \binom{n + 1 - k_1 - |I|}{\ulk' - \ule_{I}}_q.$$ A computation gives $$(q^n - 1) \binom{n-1}{n - k_1}_q\frac{(q)_{n-k_1}}{(q)_{n -k_1 - |I| + 1}} = (-1) \frac{(q)_n}{(q)_{n - |I|}} \binom{n-|I|}{n - k_1 - |I| + 1}_q,$$ and also note $$\binom{n-|I|}{n - k_1 - |I| + 1}_q\binom{n + 1 - k_1 - |I|}{\ulk' - \ule_{I}}_q = \binom{n+1 - |J|}{\ulk - \ule_{J}}_q,$$ where $\ulk=(k_1, \ldots, k_m)$, since $|I| = |J| - 1$. We finally obtain that \begin{align*} (q^n - 1) \binom{n-1}{n - k_1}_q (-1)^{|I| - 1} \frac{(q)_{n-k_1}}{(q)_{n -k_1 - |I| + 1}} & \binom{n + 1 - k_1 - |I|}{\ulk' - \ule_{I}}_q \\ & = (-1)^{|J| - 1} \frac{(q)_{n}}{(q)_{n - |J| + 1}} \binom{n + 1 - |J|}{\ulk - \ule_J}_q, \end{align*} is the the number of type $J$ subspaces of length $m-1$ of $V$, as claimed. \end{proof} \section{Generalized Galois numbers} \label{Galois} Define the homogeneous Rogers-Szeg\"o polynomial in $m$ variables for $m \geq 2$, denoted $\tH_{n}(t_1, t_2, \ldots, t_m)$, by $$ \tH_n(t_1, t_2, \ldots, t_m) = \sum_{k_1 + \cdots + k_m = n} \binom{n}{k_1, \ldots, k_m}_q t_1^{k_1} \cdots t_m^{k_m},$$ and define the Rogers-Szeg\"o polynomial in $m-1$ variables, denoted $H_n(t_1, \ldots, t_{m-1})$, by $$H_n(t_1, \ldots t_{m-1}) = \tH(t_1, \ldots, t_{m-1}, 1).$$ The homogeneous multivariate Rogers-Szeg\"o polynomials were first defined by Rogers \cite{Rog1} in terms of their generating function, and several of their properties are given by Fine \cite[Section 21]{Fi88}. The definition of the multivariate Rogers-Szeg\"o polynomial $H_n$ is given by Andrews in \cite[Chap. 3, Ex. 17]{An76}, along with a generating function, although there is little other study of these polynomials elsewhere in the literature (however, there is a non-symmetric version of a bivariate Rogers-Szeg\"o polynomial \cite{ChSaSu07}). The multivariate Rogers-Szeg\"o polynomials satisfy a recursion which generalizes (\ref{RogSze}), although it seems not to be very well-known, as the only proof and reference to it that the author has found is in the physics literature, in papers of Hikami \cite{Hi95, Hi97}. For any finite set of variables $X$, let $\be_i(X)$ denote the $i$th elementary symmetric polynomial in the variables $X$. Then the Rogers-Szeg\"o polynomials in $m-1$ variables satisfy the following recursion: \begin{equation} \label{MultiRec} H_{n+1}(t_1, \ldots, t_{m-1}) = \sum_{i = 0}^{m-1} \be_{i+1}(t_1, \ldots, t_{m-1}, 1) (-1)^{i} \frac{(q)_n}{(q)_{n-i}} H_{n-i}(t_1, \ldots, t_{m-1}). \end{equation} The sum of all $q$-multinomial coefficients of length $m$, or the generalized Galois number $G_n^{(m)}$, is then $$H_n(1,1,\ldots, 1) = G_n^{(m)} = \sum_{k_1 + \cdots +k_m=n} \binom{n}{k_1, \ldots, k_m}_q.$$ From the discussion at the beginning of Section \ref{flags}, when $q$ is the power of a prime, $G_n^{(m)}$ is exactly the total number of flags of subspaces of length $m-1$ in an $n$-dimensional $\FF_q$-vector space. Since the number of terms in the elementary symmetric polynomial $\be_{i+1}(t_1, \ldots, t_{m-1}, 1)$ is $\binom{m}{i+1}$, then the following, our last result, follows directly from the formal identity (\ref{MultiRec}) proved by Hikami. However, we give a proof which follows directly from Theorem \ref{GenGalLemma}, and is thus a bijective proof through the enumeration of flags in a finite vector space. \begin{theorem} \label{GenGalRecThm} The generalized Galois numbers satisfy the recursion, for $n \geq m-1$, $$G_{n+1}^{(m)} = \sum_{i=0}^{m-1} \binom{m}{i+1} (-1)^i \frac{(q)_n}{(q)_{n-i}}G_{n-i}^{(m)}.$$ \end{theorem} \begin{proof} For convenience, whenever any $k_i < 0$, we define the $q$-multinomial coefficient $\binom{n}{k_1, k_2, \ldots, k_m}_q = 0$. Granting this, we have Theorem \ref{GenGalLemma} holds for all $k_i \geq 0$. We now begin with the definition of $G_{n+1}^{(m)}$ as the sum of all $q$-multinomial coefficients, and we directly apply Theorem \ref{GenGalLemma} to rewrite the sum, as follows: \begin{align*} G_{n+1}^{(m)} & = \sum_{k_1 + \cdots k_m = n+1} \binom{n+1}{k_1, \ldots, k_m}_q \\ & = \sum_{k_1 + \cdots k_m = n+1} \sum_{\subst{J \subseteq \{1, \ldots, m\}}{|J| >0}} (-1)^{|J|-1} \frac{(q)_n}{(q)_{n-|J|+1}} \binom{n + 1 - |J|}{\ulk - \ule_J}_q \\ & = \sum_{\subst{J \subseteq \{1, \ldots m\}}{|J| > 0}} \sum_{\subst{\ulk = (k_1, \ldots, k_m)}{k_1 + \cdots + k_m = n+1}} (-1)^{|J|-1} \frac{(q)_n}{(q)_{n-|J|+1}} \binom{n + 1 - |J|}{\ulk - \ule_J}_q \\ & = \sum_{i=0}^{m-1} \sum_{\subst{J \subseteq \{1, \ldots, m\}}{|J| = i+1}} \sum_{\subst{\ulk = (k_1, \ldots, k_m)}{k_1 + \cdots + k_m = n+1}} (-1)^{i} \frac{(q)_n}{(q)_{n-i}} \binom{n - i}{\ulk - \ule_J}_q \\ & = \sum_{i=0}^{m-1} \binom{m}{i+1} \sum_{\subst{k_1' + \cdots + k_m' = n-i}{\ulk' = (k_1', \ldots, k_m')}} (-1)^i \frac{(q)_n}{(q)_{n-i}} \binom{n-i}{\ulk'}_q \label{last}\\ & = \sum_{i=0}^{m-1} \binom{m}{i+1} (-1)^i \frac{(q)_n}{(q)_{n-i}} G_{n-i}^{(m)}, \end{align*} where the next-to-last equality follows from the fact that each index $\ulk'$ may be obtained from an index $\ulk$ from any of the $\binom{m}{i+1}$ subsets $J$ of size $i+1$. \end{proof} By a very similar argument, we may see that in fact the recursion for the multinomial Rogers-Szeg\"o polynomials in (\ref{MultiRec}) also follows from Theorem \ref{GenGalLemma}. \subsection*{Acknowledgements} The author thanks George Andrews and Kent Morrison for very helpful comments, and the anonymous referee for very useful suggestions to improve this paper. \begin{thebibliography}{10} \bibitem{An76} G.~Andrews, \newblock {\em The Theory of Partitions}. \newblock Encyclopedia of Mathematics and its Applications, Addison-Wesley, Reading, Mass.-London-Amsterdam, 1976. \bibitem{AsWi85} R.~Askey and J.~Wilson. \newblock Some basic hypergeometric orthogonal polynomials that generalize Jacobi polynomials. \newblock {\em Mem. Amer. Math. Soc.}, 54(319), 1985. \bibitem{BlKo11} T.~Bliem and S.~Kousidis. \newblock The number of flags in finite vector spaces: asymptotic normality and Mahonian statistics. \newblock {\em J. Algebraic Combin.}, to appear, \doi{10.1007/s10801-012-0373-1}. \bibitem{ChSaSu07} W. Y. C.~Chen, H. L.~Saad, and L. H.~Sun. \newblock The bivariate Rogers-Szeg\"o polynomials. \newblock {\em J. Phys. A}, 40(23):6071--6084, 2007. \bibitem{Fi88} N. J.~Fine. \newblock Basic Hypergeometric Series and Applications. \newblock Mathematical Surveys and Monographs 27, American Mathematical Society, Providence, RI, 1988. \bibitem{GoRo69} J.~Goldman and G.-C.~Rota. \newblock The number of subspaces of a vector space. \newblock In {\em Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968)}, pages 75--83. Academic Press, New York, 1969. \bibitem{Hi95} K.~Hikami. \newblock Representations of motifs: new aspect of the Rogers-Szeg\"o polynomials. \newblock {\em J. Phys. Soc. Japan}, 64(4):1047--1050, 1995. \bibitem{Hi97} K.~Hikami. \newblock Representation of the Yangian invariant motif and the Macdonald polynomial. \newblock {\em J. Phys. A}, 30(7):2447-2456, 1997. \bibitem{HiHo10} S.~Hitzemann and W.~Hochst\"attler. \newblock On the combinatorics of Galois numbers. \newblock {\em Discrete Math.}, 310(24):3551--3557, 2010. \bibitem{KaCh02} V.~Kac and P.~Cheung. \newblock {\em Quantum Calculus}. \newblock Universitext, Springer-Verlag, New York, 2002. \bibitem{Ka06} H.~Karabulut. \newblock Distributed Gaussian polynomials as $q$-oscillator eigenfunctions. \newblock {\em J. Math. Phys.}, 47(1):013508, 2006. \bibitem{Ko11} S.~Kousidis. \newblock Asymptotics of generalized Galois numbers via affine Kac-Moody algebras. \newblock \emph{Proc. Amer. Math. Soc.}, to appear, \arxiv{1109.2546}. \bibitem{Ma89} A. J.~Macfarlane. \newblock On $q$-analogues of the quantum harmonic oscillator and the quantum group ${\rm SU}(2)_q$. \newblock {\em J. Phys. A}, 22(21):4581--4588, 1989. \bibitem{Mo06} K.~Morrison. \newblock Integer sequences and matrices over finite fields. \newblock {\em J. Integer Seq.}, 9(2):06.2.1, 2006. \bibitem{NiSoWi84} A.~Nijenhuis, A. E.~Solow, and H. S.~Wilf. \newblock Bijective methods in the theory of finite vector spaces. \newblock {\em J. Combin. Theory Ser. A}, 37(1):80--84, 1984. \bibitem{Rog1} L. J.~Rogers. \newblock On a three-fold symmetry in the elements of Heine's series. \newblock {\em Proc. London Math. Soc.}, 24:171--179, 1893. \bibitem{Rog2} L. J.~Rogers. \newblock On the expansion of some infinite products. \newblock {\em Proc. London Math. Soc.}, 24:337--352, 1893. \bibitem{St97} R. P.~Stanley. \newblock {\em Enumerative Combinatorics, Vol. 1}. \newblock Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge, 1997. \bibitem{Sz26} G.~Szeg\"o. \newblock Ein Beitrag zur Theorie der Thetafunktionen. \newblock {\em S. B. Preuss. Akad. Wiss. Phys.-Math. Kl.}, 242--252, 1926. \bibitem{Wa06} S. O.~Warnaar. \newblock Rogers-Szeg\"o polynomials and Hall-Littlewood symmetric functions. \newblock {\em J. Algebra}, 303(2):810--830, 2006. \end{thebibliography} \end{document}