\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}
