\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{psfrag}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Counting the Restricted Gaussian Partitions \\
\vskip .10in
of a Finite Vector Space
}
\vskip 1cm
\large
Fusun Akman and Papa A. Sissokho  \\ 
4520 Mathematics Department \\ 
Illinois State University\\ 
Normal, IL  61790-4520 \\
USA \\
\href{mailto:akmanf@ilstu.edu}{\tt akmanf@ilstu.edu}\\
\href{mailto:psissok@ilstu.edu}{\tt psissok@ilstu.edu}
\end{center}

\vskip .2 in

\def \bs{\bigskip}
\def \GF{{\rm GF}}
\def \GL{{\rm GL}}
\def \P{{\mathcal P}}
\def \ra{\rangle}
\def \la{\langle}
\def \th{\theta}
\def \Vnq{V(n,q)}


\begin{abstract}
A subspace partition $\Pi$ of a finite vector space $V=V(n,q)$ of
dimension $n$ over $\GF(q)$ is a collection of subspaces of $V$ such
that their union is $V$, and the intersection of any two subspaces in
$\Pi$ is the zero vector.  The multiset $T_{\Pi}$ of dimensions of
subspaces in $\Pi$ is called the type of $\Pi$, or, a Gaussian
partition of $V$. Previously, we showed that subspace partitions of $V$
and their types are natural, combinatorial $q$-analogues of the set
partitions of $\{ 1,\dots,n\}$ and integer partitions of $n$
respectively. In this paper, we connect all four types of partitions
through the concept of  ``basic'' set, subspace, and Gaussian
partitions, corresponding to the integer partitions of $n$. In
particular, we combine Beutelspacher's  classic construction of
subspace partitions with some additional conditions to derive a special
subset ${\mathcal G}$ of Gaussian partitions of $V$.  We then show that
the cardinality of ${\mathcal G}$ is a rational polynomial $R(q)$ in
$q$, with $R(1)=p(n)$, where $p$ is the integer partition function.
\end{abstract}

\section{Introduction}

\subsection{The background}

Let $n$ be a positive integer and $q$ be a prime power. Let $V=\Vnq$ denote the $n$-dimensional vector space over $\GF(q)$.
A {\em subspace partition} (also known as {\em vector space partition})  of $V$ is a collection of subspaces of $V$ such that their union is $V$, and the intersection of any 
two subspaces in $\Pi$ is the zero vector; for example, see the recent survey by Heden~\cite{HeSv}. Subspace partitions are used 
to construct translation planes and nets~\cite{An,Ba,BB}, error-correcting codes~\cite{He0,HoPa,KoKs,Li}, orthogonal
arrays~\cite{EJSSS}, and designs~\cite{EZ,Th1}. 
The origins of subspace partitions can be traced back to the general problem of partitioning a 
finite group into subgroups intersecting only at the identity element \cite{HeSc2,Mi,Za}. 


Let $\Pi$ be a subspace partition of $V=\Vnq$. Suppose that $\Pi$ consists of $x_i$ subspaces 
of dimension $d_i$ for $1\leq i\leq k$. The multiset $T_{\Pi}=d_1^{x_1}\ldots d_k^{x_k}$ of dimensions 
is then called a  {\em partition type} of $V$. 
Clearly, not every multiset $T$ that contains plausible dimensions is a  partition type of $V$. 
 However, if $T$ {\em is} a partition type, then it must satisfy certain necessary conditions.
One such condition,  called the {\em packing condition}, is obtained by counting the 
nonzero vectors of $V$ in two ways:
\begin{equation}\label{nc1}
\sum_{i=1}^{k}x_i(q^{d_i}-1)=(q^{n}-1). 
\end{equation}

A second necessary condition comes from dimension considerations.
If $U$ and $W$ are subspaces of $\Vnq$, then it is well known that the subspace spanned 
by $U \cup W$ has dimension $\dim(U)+\dim(W)-\dim(U\cap W)$. 
Therefore, if $T$ is a partition type, then it must satisfy
\begin{equation}\label{nc2}
\begin{cases}
2d_i\leq n,&\quad\mbox{if }x_i\geq2;\\
d_i+d_j\leq n,  &\quad\mbox{if } i\neq j.
\end{cases}
\end{equation}
The necessary conditions~\eqref{nc1} and~\eqref{nc2} are not sufficient in general. 
For instance, $2^{10}1^1$ is not a partition type of $V(5,2)$. There are several other 
nontrivial necessary conditions \cite{HeT,HeLe,HLNS2}.

In previous papers~\cite{AS2,AS1}, we studied the lattice of subspace partitions of $V=\Vnq$ and the poset 
of partition types of $V$ (which we called the {\em Gaussian partitions} of $V$). We proved several results, revealing  
these two objects as natural, combinatorial $q$-analogues of the set partitions of ${\bf n}=\{1,\ldots,n\}$ and the integer partitions of $n$ respectively.  In this paper, we connect all four types 
of partitions through the concept of  ``basic'' set, subspace, and Gaussian partitions, which correspond to the integer partitions of $n$. In particular, we distinguish ``regular'' subspace partitions as those that owe their existence to the most natural construction due to Beutelspacher~\cite{Be2} and give an argument on why it is not practical at this point to count the ``irregular'' Gaussian partitions. We then impose additional conditions on the regular subspace (and hence Gaussian) partitions and call them the ``restricted'' partitions, which are certain refinements of the basic ones. Our main result is as follows:

\begin{theorem}\label{thm:main}
Let $q$ be a prime power and $n$ be a positive integer. 
Then the number of restricted Gaussian partitions of $V(n,q)$ is a rational polynomial $R(q)$ in $q$. Moreover, 
we have $R(1)=p(n)$, where $p$ is the integer partition function.
\end{theorem}

This is the counterpart of an earlier 
result of ours \cite{AS2}, which states that the number of the {\em full} set of subspace partitions of $V$ is congruent to the Bell number $B_n$, the number of set partitions of {\bf n}, modulo~$q-1$. 

\subsection{Why consider restricted partitions?}

The techniques we used in our first article \cite{AS2} in this series to count the subspace partitions of $V=V(n,q)$ are not applicable to the process of enumerating the set of all Gaussian partitions; new methods need to be developed. In our second article \cite{AS1}, we demonstrated that counting the Gaussian partitions of $V$ for $n\leq 5$ by brute force was fairly straightforward, but that as soon as we reached $n=6$, we were stymied: we simply do not have much information about the existence of maximal  subspace partitions that are not constructed by traditional means. Some exotic examples (used to disprove conjectures), such as a subspace partition of $V(8,2)$ with 34 subspaces of dimension 3 and 17 subspaces of dimension 1, are often constructed by the aid of computers~\cite{AS1,EJSSS}. However, an analysis conducted by Lambert~\cite{La} shows that there is no apparent structure in the aforementioned example, making it difficult to generalize. Hence, the problem of determining the {\em maximum-size partial spreads} remains largely unsolved. Similarly, finding the {\em maximal partial spread} partitions of $V(n,q)$ for $n\geq 4$ is currently intractable. This makes the precise counting of all Gaussian partitions an essentially impossible task. Nevertheless, it would still be interesting to count certain subsets of the Gaussian partitions, in particular, those  that could provide a $q$-analogue of integer partitions.

As a first step towards conquering the counting problem, we propose to consider only those subspace partitions that are constructed from $V$ by  the Beutelspacher method described in Section~\ref{TheMechanism}. This 
method is crucial in constructing examples for the applications we referred to in the previous section. 
We will designate the resulting subspace and Gaussian partitions as {\em regular}.
This convention is akin to leaving out the exceptional groups in the classification of finite simple groups, whose existence and structures require the use of more customized techniques. Unfortunately, the resulting poset of regular Gaussian partitions is still very difficult to count ---  we had to stop at $n=7$. The problem stems from the fact that the same regular Gaussian partition may be obtained by more than one sequence of consecutive ``refinements'' of subspace dimensions, and there seems to be no consistent way to prefer one construction over the others. That is, there is no good way of building 
a tree structure out of all regular Gaussian partitions with respect to preferred refinements. However, regular Gaussian partitions can conceivably be counted by sheer computer power for  a specific dimension $n$ in terms of $q$. 
For $n\leq 6$, the numbers of regular Gaussian partitions of $V(n,q)$ turned out to be rational polynomials in $q$ with 
the value $p(n)$ at $q=1$, placing regular Gaussian partitions among strong contenders for a $q$-analogue of the integer partition function.

As a second step, we propose counting a subset of regular Gaussian partitions 
(defined by  simple rules) while maintaining the property that this set of Gaussian partitions 
provides a $q$-analogue of integer partitions. To that end, we enumerate the {\em restricted} Gaussian partitions 
of $V(n,q)$, described in detail in Section~\ref{looklike}. This method requires that as a starting point, 
we introduce the notions of {\em basic set}, {\em basic subspace},  and {\em basic Gaussian partitions} that naturally correspond to the integer partitions of $n$ (the basic set and basic Gaussian partitions are in fact in 1-1 correspondence with  the  integer partitions). We then apply the Beutelspacher method of refinement selectively, so that the new subspace dimensions that are created from any one dimension can be squeezed in between the existing ones, without disturbing the nonincreasing sequence (there are a few more conditions). 
Our claim that the choice of restricted Gaussian partitions  is a reasonable compromise is validated
by the fact that these partitions do form a $q$-analogue for integer partitions, as proven in Theorem~\ref{thm:main}.

Our ultimate goal is to find simple enough rules to capture the largest  subset of Gaussian partitions (ideally all of them) forming a $q$-analogue of integer partitions that 
 {\em counts combinatorial objects}. We realized a similar goal in our first paper \cite{AS2} by showing that the full lattice of subspace partitions is the natural $q$-analogue of the lattice of set partitions. 

\section{Set, integer, and subspace partitions}

\subsection{Set partitions}

\begin{definition}[Split of subset] 
A {\em split} of a subset $D$ of $\mbox{\bf n}=\{ 1,\dots,n\}$ with $d=|D|\geq 2$ is a refinement operation denoted by $(a,b)$, where $a+b=d$ and  $a\geq b\geq 1$, that results in partitioning $D$ into two disjoint subsets $A$ and $B$ of cardinalities $a$ and $b$ respectively. 
\end{definition}

The partition $\{A,B\}$ of $D$ is not unique as defined. However, we can make it unique as follows: 

\begin{definition}[Ordering split of subset] An {\em ordering split} of a subset $D$ of $\mbox{\bf n}$ is a split $(a,b)$ as in the above definition such that any element of $A$ is strictly less than any element of $B$. 
\end{definition}

\begin{lemma} Any set partition of {\bf n} can be obtained by applying a sequence of splits to {\bf n} (after the first split, we understand that each subsequent split is applied to a smaller subset generated previously). The empty sequence corresponds to the partition $\{ \mbox{\bf n}\}$ with one part.
\end{lemma}

\begin{definition}[Basic set partition]\label{canon} A set partition of $\mbox{\bf n}=\{ 1,\dots,n\}$ with $k$ parts will be called {\em basic} if its parts can be labeled $D_1,\dots,D_k$, with cardinalities $d_1,\dots,d_k$ respectively, in such a way that:
\begin{enumerate}
  \item $d_1\geq \cdots \geq d_k\geq 1$, and
  \item for all $i$ with $1\leq i\leq k$, the collection $D_1,\dots,D_i$ is a set partition of $\mbox{\bf d}=\{ 1,\cdots ,d\}$, where $d=d_1+\cdots +d_i$.
\end{enumerate}
\end{definition}

For the next two lemmas, let us adopt the notation of Definition~\ref{canon}.

\begin{lemma} The set of basic set partitions of {\bf n} is in one-to-one correspondence with the integer partitions of 
$n$, via 
\[ \{ D_1,\dots,D_k\}\longleftrightarrow  d_1\dots d_k.\]
\end{lemma}

\begin{remark} 
Note that we are only interested in the {\em unordered integer partitions} of $n$ here. 
For instance, the sequence $5\cdot 3\cdot 1\cdot 1$ and its permutations (e.g., $3\cdot 5\cdot 1\cdot 1$)
will all represent the same integer partition of $n=10$.
\end{remark}

\begin{example} The collection 
$\left\{\{1,2,3,4,5\},\{ 6,7,8,9,10\},\{11,12,13\},\{ 14\}, \{15\},\{ 16\} ,\{ 17\}\right\}$ is the basic set partition of {\bf 17} corresponding to the integer partition $5^23^11^4$ of $17$. 
\end{example}

\begin{lemma} Any basic set partition of {\bf n} with parts described as in Definition~\ref{canon} can be obtained by applying the sequence  
\[ (d_1+\cdots +d_{k-1},d_k),(d_1+\cdots+d_{k-2},d_{k-1}),\dots,(d_1,d_2)\]
of ordering splits to {\bf n}. By definition, the empty sequence corresponds to $\{ \mbox{\bf n}\}$.
\end{lemma}

\subsection{Regular, basic, and restricted subspace partitions}

\subsubsection{Splits of subspaces}

\label{splitsofsubspaces}
The study of all possible subspace partitions and their types considered in~\cite{AS2,AS1} is hampered by the 
fact that even in small dimensions, the maximal subspace partitions of $V(n,q)$ have not been enumerated 
for all $q$, and even their types remain a mystery. Examples are the number of 2-spreads of $V(4,q)$ and 
the types of the exceptional partitions of $V(6,q)$ that we mentioned elsewhere~\cite{AS1}. As a matter of fact, 
when we put aside the dozens of special cases of partition constructions of novel types~\cite{Bu,HeLe,SSSV}, there have been only two basic existence theorems in 
the literature that are used consistently:

\medskip

 { (A)} If $d$ divides $n$, then Andr\'e~\cite{An} proved that $V(n,q)$ has a refinement of type 
$d^{\frac{q^{n}-1}{q^d-1}}$, which is better known as a {\em $d$-spread of $\Vnq$}. 

\medskip

 { (B)} If $1\leq d< n/2$, then it was proved by Beutelspacher~\cite{Be2}, and independently by Bu~\cite{Bu},
that $V(n,q)$ has a refinement of type $(n-d)^1\,d^{\,q^{n-d}}$.

\medskip

The case $d=n/2$ is covered by (A). If $d$ divides $n$ but is not equal to $n/2$, then finitely many applications of the move (B) will give us a spread as in (A). Thus, these two refinements can be combined into a single one:

\medskip

 { (C)} If $1\leq d\leq n/2$, then $V(n,q)$ has a refinement of type $(n-d)^1\,d^{\,q^{n-d}}$. 

\begin{definition}[Split of subspace] A {\em split} is a refinement of the form (C) on any one subspace in a subspace partition. We will let $(a,b)$ (for $a\geq  b\geq 1$) denote a subspace split that produces the refinement $(a+b)^1\rightarrow a^1b^{\, q^a}$ of the type $(a+b)^1$. 
\end{definition}

Note that a split only shows the type of the move and not the subspace it is applied to. It is possible to obtain many different refined subspace partitions (of the same type) by applying a split to a specific subspace partition, just as in the case of set partitions. 

\subsubsection{The mechanism for creating regular subspace partitions}

\label{TheMechanism}
We will use the construction of Beutelspacher~\cite{Be2} and Bu~\cite{Bu} that yields the partitions in 
the statement (B) discussed earlier.
This construction starts from a given direct sum decomposition $W\oplus U$ of $V(n,q)$ and a partition of 
$U$ to give us a partition of $V(n,q)$ that includes $U$ and $W$. Moreover, the new subspaces in the 
partition reproduce the dimension of $U$.

\begin{theorem}[Beutelspacher~\cite{Be2}]\label{BeBu} Let $V=V(n,q)$, $U$ and $W$ be subspaces of $V$ such that 
$V=W\oplus U$, and $s=\dim(W)\geq\dim(U)=t$. Let $\{ w_1,\dots, w_s\}$ be a basis of $W$, and 
$\{ u_1,\dots,u_t\}$ be a basis of $U$. Moreover, we identify $W$ with the field  GF$(q^s)$. 
For every  element $\gamma\in W$, define a subspace $U_{\gamma}$ of $V$ by
\[ U_{\gamma}=\mbox{\em span}(\{ u_{1}+\gamma w_1,\dots, u_{t}+\gamma w_{t}\} ).\]
Then $\dim(U_{\gamma})=t$, $U_{\gamma}\cap U_{\gamma'}=\{ 0\}$ for $\gamma\neq \gamma'$, and the 
collection 
\[ \{W\}\cup \left\{ U_{\gamma}:\, \gamma\in W\right\} \]
of subspaces forms a partition of $V$. 
\end{theorem}

Theorem~\ref{BeBu} can be used to accomplish refinements described in (C):

\begin{corollary}\label{maincor} Choosing $\dim(W)=n-d$ and $\dim(U)=d$ (where $d\leq n/2$) in 
Theorem~\ref{BeBu}, we obtain a subspace partition of $V(n,q)$ of type $(n-d)^1d^{\, q^{n-d}}$. 
\end{corollary}

We will informally designate the new subspaces $U_{\gamma}$ created in the above corollary, 
for which $\gamma\neq 0$, as ``copies'' of $U=U_0$.

\begin{definition}[Regular subspace partition] A {\em regular subspace partition} of $V=V(n,q)$ is one that is obtained from $V$ via a finite number of splits of type~(C), employing the mechanism described in Corollary~\ref{maincor}.
\end{definition}

\subsubsection{Basic subspace partitions}

Let us fix a basis $S=\{ e_1,\dots ,e_n\}$ of $V=V(n,q)$, and identify it with {\bf n} via the subscripts. 

\begin{definition}[Ordering split of special subspace] Let $D$ be a nonempty subset of $S$. An {\em ordering split} of type $(a,b)$ of $\langle D\rangle$, the subspace of $V(n,q)$ generated by $D$, is one that is created by applying the ordering split $(a,b)$ to the set $D$ to obtain a partition $\{ A,B\}$ of $D$, then applying the construction in Corollary~\ref{maincor} to $\langle D\rangle=\langle A\rangle\oplus \langle B\rangle$, with $W=\langle A\rangle$ and $U=\langle B\rangle$.
\end{definition}

\begin{definition}[Basic subspace partition]\label{tau} We call a regular subspace partition $\Pi$ of $V$ {\em basic} 
if it can be obtained by applying a sequence of ordering splits to $V=\langle S\rangle$ that would have resulted in the corresponding basic set partition of $S$.
\end{definition}

\begin{lemma}\label{Pi}Let $\Pi$ be a basic subspace partition as described above, and let $\{ D_1,\dots,D_k\}$ be the corresponding basic set partition of the basis $S$ of $V$. Then $\Pi$ contains the subspaces $\langle D_1\rangle ,\dots,\langle D_k\rangle$ of $V$.
\end{lemma}

Note that due to the different choices of identification of $W$ with GF$(q^s)$ in Theorem~\ref{BeBu}, there may be multiple basic subspace partitions associated with an integer partition of $n$. However, all of these 
basic subspace partitions are in the same orbit under the action by $\GL(n,q)$.

\subsubsection{Restricted subspace partitions}\label{sec:ConAlgo}

\begin{definition}[Left/right subspaces] Consider a subspace $W$ of $V$ of dimension $a+b$, with $a\geq b\geq 1$. We will call the $a$-dimensional subspace that results from a split of $W$ of type $(a,b)$ a {\em left subspace} and the $q^{\, a}$ dimensional subspaces of dimension $b$ that are produced in the same split {\em right subspaces}.
\end{definition}

Even if $a=b$, there is still one distinguished left subspace due to the construction in Theorem~\ref{BeBu}.

From this point on, we will only consider regular subspace partitions of $V(n,q)$ that are either basic or are obtained from a basic one by finitely many splits via the mechanism described in Corollary~\ref{maincor} and three additional rules that we will outline below. 


\begin{definition}[Restricted subspace partition] Let $V=V(n,q)$. A regular subspace partition $\Gamma$ of $V$ is called a {\em restricted subspace partition} if it is basic, or if it can be obtained from a basic subspace partition $\Pi$ (as given in Definition~\ref{tau} and Lemma~\ref{Pi}) by refinements of type (C) according to the following rules:

\medskip

 {\em 1. The unique ancestor rule:} The subspaces $\langle D_i\rangle$ in $\Pi$ will be left intact.

 \medskip

 {\em 2. The left-right rule:} Only copies of $\la D_i\ra$ and subsequently the resulting left subspaces can be split.

 \medskip

 {\em 3. The dimension rule:} If $f_1\cdots f_s$ is the Gaussian partition describing the nonincreasing dimensions of the subspaces  that exist at any stage of the construction, then applying a split $(a,b)$ to a subspace of dimension $f_i$ with $i<s$ will result in the ordering $f_i>a\geq b\geq f_{i+1}$. Exception: The same split $(a,b)$ may be  applied to several subspaces of dimension $f_i$ simultaneously.
\end{definition}

\begin{remark} The untouched subspaces $\langle D_i\rangle$ reflect the corresponding partitioning of the basis $S$ of $V$ as a set. This way, we can trace every restricted subspace partition back to a unique basic set partition as well as a unique integer partition. The dimension rule dictates that the parts $a$ and $b$ of the split cannot be strictly smaller than the dimensions to the right of $f_i$, if any. 
\end{remark}


\section{Restricted Gaussian partitions extend integer partitions}

\subsection{Basic Gaussian partitions}

\begin{definition}[Basic Gaussian partition] A regular Gaussian partition of $V(n,q)$ is called {\em basic} 
if it is the type of a basic subspace partition of $V(n,q)$.
\end{definition}

\begin{proposition} The basic  Gaussian partitions of $V(n,q)$ and the basic set partitions of {\bf n} are in one-to-one correspondence with  the integer partitions of $n$. 
\end{proposition}

\begin{example}\label{exthirteen} The integer partition $5^23^11^4$ of $n=17$ is represented by the basic Gaussian partition
\[ 5^{\, 1}5^{\, q^5} 3^{\, q^{10}} 1^{\, q^{13}}  1^{\, q^{14}}1^{\, q^{15}}1^{\, q^{16}}=      5^{\, 1+q^5}3^{\, q^{10}}1^{\, q^{13}+q^{14}+q^{15}+q^{16}}\]
of $V(17,q)$. Note that the exponent of $5^{\, q^5}$ tells us that the sum of the dimensions that come before (equivalently, the parts of the corresponding integer partition) is $5$, the exponent of $3^{\, q^{10}}$ tells us that the previous sum is 10, and the exponent of $1^{\, q^{13}}$ tells us that the previous dimensions  add up to 13, etc.
\end{example}

The following  proposition provides an explicit shape for basic Gaussian partitions.

\begin{proposition}\label{obviousone}\label{add-prop}

\mbox{\vphantom{X}}

 {\em (1)} The basic Gaussian partition of $V(n,q)$ that corresponds to the integer partition $d_1\cdots d_k$ of $n$, 
with $d_1\geq \cdots \geq d_k$, is given by
\[ T=d_1^1d_2^{\, q^{\, d_1}}d_3^{\, q^{\, d_1+d_2}}\cdots d_k^{\, q^{\, d_1+\cdots +d_{k-1}}}.\]
Conversely, a partition of type $T$, where $d_1\geq \cdots \geq d_k$ and $d_1+\cdots +d_k=n$, is basic. 
\medskip

 {\em (2) (The Addition Property)} For a Gaussian partition written as in part {\em (1)}, the exponent $q^t$ of any dimension $d_i$ reflects the sum $t=d_1+\cdots +d_{i-1}$  of the parts of the corresponding integer partition that come before $d_i$ (the empty sum is zero).
 \medskip

 {\em (3)} If we require the dimensions $d_i$  to be distinct, then the basic Gaussian 
partition corresponding to the integer partition $d_1^{\, n_1}\cdots d_k^{\, n_k}$ of $n$, with $d_1> \cdots > d_k$, 
is given by 
\begin{align}
T &=d_1^{ 1+q^{\, d_1}+\cdots +q^{(n_1-1)d_1}}d_2^{\, q^{n_1d_1}+q^{n_1d_1+d_2}+\cdots +q^{n_1d_1+(n_2-1)d_2}}\cdots\nonumber\\
& d_k^{\, q^{(n_1d_1+\cdots +n_{k-1}d_{k-1}) }+\cdots +q^{(n_1d_1+\cdots +(n_k-1)d_k)}} .\nonumber
\end{align}
 Moreover, the uniqueness of the exponents in $T$ as a polynomial in $q$ with integer coefficients 0 or 1 follows from 
the uniqueness of digits in the base-$q$ representation of positive integers. 
\end{proposition}

The two depictions of $T$ in Proposition~\ref{obviousone}, parts (1) and (3), correspond to the left- and right-hand sides of the equation in Example~\ref{exthirteen} respectively.

\subsection{Restricted Gaussian partitions}\label{looklike} 

The definition and notation of splits can be applied to the  regular Gaussian partitions associated with $V(n,q)$. 
The subspace dimensions in a Gaussian partition $T$ will be written in nonincreasing order, with or without exponents.


\begin{definition}[Dimension-preserving split of Gaussian partition] Let $T=f_1^{x_1}\cdots f_k^{x_k}$ with $f_1\geq  \cdots \geq f_k$ be a Gaussian partition, and suppose that $f_i=a+b$  with $a\geq b\geq 1$ and $i<k$. Then the split $(a,b)$ of the dimension $f_i$ is called {\em dimension-preserving} provided that $f_i>a\geq b\geq f_{i+1}$. Splits of the last dimension, $f_k$, are always dimension-preserving. Simultaneous applications of the same dimension-preserving split $(a,b)$ to several of the dimensions $f_i$ are also considered to be dimension-preserving.
\end{definition}

After applying a dimension-preserving split $(a,b)$ to one of the dimensions $f_i$ as above, we will replace the segment $f_i^{x_i}f_{i+1}^{x_{i+1}}$ in $T$ by $f_i^{x_i-1}
a^1b^{\, q^{\, a}}f_{i+1}^{x_{i+1}}$.  If $x_i\geq j$, then $j$ simultaneous applications of $(a,b)$ to the $f_i$'s will result in the expression 
$f_i^{x_i-j}a^jb^{\, jq^{\, a}}f_{i+1}^{x_{i+1}}$, so that the nonincreasing order is preserved.


\begin{definition}[Left/right dimensions] Let $(a,b)$ be a split to be applied to a dimension $f=a+b$. Then $a^1$ is called a {\em left dimension} and the dimensions $b$ appearing in $b^{q^a}$ are called {\em right dimensions}, even if $a=b$.
\end{definition}

A restricted Gaussian partition $T_{\Gamma}$ is just the type of a restricted subspace partition $\Gamma$. However, it is possible to describe a restricted Gaussian partition without any reference  to  a restricted subspace partition by applying the principles in Section~\ref{sec:ConAlgo}. 

\begin{definition}[Restricted Gaussian partition, Spine, Spinelet]\label{restga} 
Let $V=V(n,q)$ and $T$ be a basic Gaussian partition of $V$, written 
\begin{align}
T &=d_1^{ 1+q^{\, d_1}+\cdots +q^{(n_1-1)d_1}}d_2^{\, q^{n_1d_1}+q^{n_1d_1+d_2}+\cdots +q^{n_1d_1+(n_2-1)d_2}}\cdots\nonumber\\
&d_k^{\, q^{(n_1d_1+\cdots +n_{k-1}d_{k-1}) }+\cdots +q^{(n_1d_1+\cdots +(n_k-1)d_k)}} \;\;\;\; (d_1>\cdots >d_k)\nonumber
\end{align}
as in Proposition~\ref{obviousone}(3). The partition $T$ and any regular Gaussian partition $T'$ obtained from $T$ by dimension-preserving splits according to the following rules are called {\em restricted Gaussian partitions} of $V$:

\medskip

 {\em 1.} A split $(a,b)$ may only be applied to the dimension $d_i$ in $T$ if the exponent of $d_i$ is not equal to 1. 

 \medskip

 {\em 2.} At most $N=q^u-1$ splits of the same type $(a,b)$ may be applied simultaneously to repeated dimensions $d_i$ in the basic partition $T$, where $q^u$ is the unique largest power of $q$ in the exponent of $d_i$. The linearly ordered collection of $N$ Gaussian partitions obtained by applying $(a,b)$ to the $d_i$'s 1 through $N$ times is called the {\em spine} corresponding to the split $(a,b)$.

 \medskip

 {\em 3.} At any  regular Gaussian partition containing a power $a^k$  of a left dimension $a$ (where $1\leq k\leq N$) 
on a spine, we may apply a dimension-preserving split $(c,d)$ up to $k$ times to  $a$, obtaining a 
linearly ordered collection of $k$ Gaussian partitions called a {\em spinelet} corresponding to $(c,d)$. Any subsequent linear side branch constructed by up to $l$ repeated dimension-preserving splits of the same kind to left dimensions 
$c^l$ is also called a spinelet, and so on. 
\end{definition}


Examples of spines and spinelets can be seen in Example~\ref{v6q} as well as Figure~\ref{fig1}. Note that we are allowed to completely dissolve powers of left dimensions on a spine or spinelet, whereas the number of applications of any one order-preserving split to the basic Gaussian partition $T$ is bounded.

\bigbreak

\begin{remark}
\mbox{\vphantom{.}} 
\begin{enumerate}
  \item The tree of various spines and spinelets emanating from $T$ help us visualize the universe of possibilities for restricted Gaussian partitions $T'$ constructed from $T$ and eventually help us explicitly count all such  partitions.
  \item  Suppose $T$ were written in the form
\[ T=d_1^1d_2^{\, q^{\, d_1}}d_3^{\, q^{\, d_1+d_2}}\cdots d_k^{\, q^{\, d_1+\cdots +d_{k-1}}}\;\;\;\; (d_1\geq \cdots \geq d_k)\]
as in Proposition~\ref{obviousone}(1). Clearly, strictly smaller dimensions $a$ and $b$ cannot be placed in between the same two integers $d_i$ and $d_{i+1}$ in $T$ by the dimension rule for subspaces, and splitting the unique subspace $\langle D_i\rangle$ of dimension $d_i$ is prohibited by the unique ancestor rule. 
Hence, for any distinct dimension of $T$, with largest power of $q$ in its exponent  equal to $q^u$, 
we may only dissolve (refine) at most $q^u-1$ copies of it. 
  \item Only one kind of dimension-preserving split $(a,b)$ may be applied to a dimension $d_i$ during a particular construction. If a different one, say $(r,s)$ with $a>r$ and $b<s$ is attempted before or after $(a,b)$, then the resulting order of dimensions would be $d_i,r,s,a,b,d_{i+1}$ or $d_i,a,b,r,s,d_{i+1}$, violating the dimension rule. 
   \item  By the same reasoning as above, only one type of dimension-preserving split may be applied to a subsequently formed left dimension.
   \item None of the dimension-preserving  splittings whose results are placed between powers of dimensions $d_i$ and $d_{i+1}$ ends in another basic Gaussian partition. However, if we were to split the last dimension $d_i$ at the end of a spine (corresponding to the subspace $\la D_i\ra$) using an $(N+1)$st split $(a,b)$, then we would arrive at another basic Gaussian partition. This is stated as Proposition~\ref{obvioustwo}.
   \item  The construction process of any restricted Gaussian partition $T'$ is unique up to order. That is, it can be traced back to a unique basic Gaussian partition $T$, and there is only one possible set of splits  that results in $T'$ (splits starting out of different places in $T$ commute). This is stated as Proposition~\ref{norep}.
\end{enumerate} 
\end{remark}

\begin{example}[The Gaussian partitions of $V(6,q)$]\label{v6q}
The $11=p(6)$ basic Gaussian partitions of $V(6,q)$ are $6^1$, $5^11^{q^5}$,  $4^11^{q^4+q^5}$, $3^11^{q^3+q^4+q^5}$,  $2^11^{q^2+q^3+q^4+q^5}$, $1^{1+q+q^2+q^3+q^4+q^5}$, $4^12^{\, q^4}$, $3^{1+q^3}$, 
$3^12^{\, q^3}1^{q^5}$, $2^{1+q^2+q^4}$, and $2^{1+q^2}1^{q^4+q^5}$. The first five cannot be split further without running into another basic partition, and the sixth one is already minimal. The non-basic restricted Gaussian partitions obtained from the remaining five are described in the following table:

\bigbreak

\[ \begin{array}{|c|c|c|c|}\hline
\mbox{\em Basic} & \mbox{\em Splits} & \mbox{\em Non-basics} & \mbox{\em Range} \\ \hline
4^12^{\, q^4} & (1,1) & 4^12^{\, q^4-i}1^{i(q+1)} & 1\leq i\leq q^4-1\\ \hline
3^{1+q^3} & (2,1) & 3^{1+q^3-i}2^i1^{iq^2} & 1\leq i\leq q^3-1\\ \hline
3^{1+q^3} & (2,1)\,\mbox{\rm and}\, (1,1) & 3^{1+q^3-i}2^{i-j} 1^{iq^2+j(q+1)} 
& 1\leq i\leq q^3-1;\,1\leq j\leq i\\ \hline
3^12^{\, q^3}1^{q^5} &(1,1) & 3^12^{\, q^3-i}1^{i(q+1)+q^5} &1\leq i\leq q^3-1 \\ \hline
2^{1+q^2+q^4} & (1,1) & 2^{1+q^2+q^4-i}1^{i(q+1)} & 1\leq i\leq q^4-1\\ \hline
2^{1+q^2}1^{q^4+q^5} & (1,1) & 2^{1+q^2-i}1^{i(q+1)+q^4+q^5} & 1\leq i\leq q^2-1\\ \hline
\end{array}\]

Consider the number of non-basic regular Gaussian partitions of $V(6,q)$: there are
\[ s(q)=\sum_{i=1}^{q^3-1} \sum_{j=0}^i 1=\sum_{i=1}^{q^3-1}(i+1)= \frac{(q^3-1)q^3}{2}+(q^3-1)\]
of them that are obtained from $3^{1+q^3}$, and the total is
\[ (q^4-1)+s(q) +(q^3-1)+(q^4-1)+(q^2-1),\]
a rational polynomial in $q$ with root $q=1$.

In this table, we can see the spines corresponding to the separate splits of types $(1,1)$ and $(2,1)$ as well as the spinelets resulting from $(2,1)$'s followed by $(1,1)$'s. See Figure~\ref{fig1}, where the basic Gaussian partitions, 
spines, and spinelets for $n=6$ are laid out in tree form.

\bs
\begin{figure}[ht!]
\psfrag{a}[][]{\tiny $6^1$}
\psfrag{b1}[][]{\tiny $5^11^{q^5}$}
\psfrag{b2}[][]{\tiny $4^11^{q^4+q^5}$}
\psfrag{b3}[][]{\tiny $3^12^{q^3}1^{q^5}$}
\psfrag{b4}[][]{\tiny $3^11^{q^3+q^4+q^5}$}
\psfrag{b5}[][]{\tiny $\;2^{1+q^2}1^{q^4+q^5}$}
\psfrag{b6}[][]{\tiny $2^{1}1^{q^2+\ldots+q^5}$}
\psfrag{b7}[][]{\tiny $2^{q^2}1^{(q+1)+q^4+q^5}$}
\psfrag{b8}[][]{\tiny $1^{1+q+\ldots+q^5}$}
\psfrag{b9}[][]{\tiny $2^{2}1^{(q^2-1)(q+1)+q^4+q^5}$}
\psfrag{b10}[][]{\tiny $3^12^{q^3-1}1^{(q+1)+q^5}$}
\psfrag{b11}[][]{\tiny $3^12^{1}1^{(q^3-1)(q+1)+q^5}$}

\psfrag{c1}[][]{\tiny $4^12^{q^4}$}
\psfrag{c2}[][]{\tiny $2^{1+q^2+q^4}$}
\psfrag{c3}[][]{\tiny $4^12^{q^4-1}1^{q+1}$}
\psfrag{c4}[][]{\tiny $2^{q^2+q^4}1^{q+1}$}
\psfrag{c5}[][]{\tiny $4^12^11^{(q^4-1)(q+1)}$}
\psfrag{c6}[][]{\tiny $2^{2+q^2}1^{(q^4-1)(q+1)}$}

\psfrag{d1}[][]{\tiny $3^{1+q^3}$}
\psfrag{d2}[][]{\tiny $3^{q^3}2^11^{q^2}$}
\psfrag{d3}[][]{\tiny $3^{q^3}1^{q^2+(q+1)}$}
\psfrag{d4}[][]{\tiny $3^{q^3-1}2^{2}1^{2q^2}$}
\psfrag{d5}[][]{\tiny $3^{q^3-1}2^{1}1^{2q^2+(q+1)}$}
\psfrag{d6}[][]{\tiny $3^{q^3-1}1^{2q^2+2(q+1)}$}
\psfrag{d7}[][]{\tiny $3^{2}2^{q^3-1}1^{(q^3-1)q^2}$}
\psfrag{d8}[][]{\tiny $3^{2}1^{(q^3-1)q^2+(q^3-1)(q+1)}$}
\psfrag{red}[][]{\tiny link between basic partitions}
\psfrag{black}[][]{\tiny spines}
\psfrag{an}[][]{\tiny ; }
\psfrag{blue}[][]{\tiny spinelets}

\centerline{\includegraphics[width=5in]{figure1.eps}}
\caption{Basic Gaussian partitions, spines, and spinelets for $n=6$}\label{fig1}
\end{figure}
\end{example}

\begin{proposition}\label{obvioustwo}
Let
\begin{align}
T &=d_1^{\, 1+q^{d_1}+\cdots +q^{(n_1-1)d_1}}d_2^{\, q^{n_1d_1}+q^{n_1d_1+d_2}+\cdots +q^{n_1d_1+(n_2-1)d_2}}\cdots\nonumber\\
& d_k^{\, q^{(n_1d_1+\cdots +n_{k-1}d_{k-1}) }+\cdots +q^{(n_1d_1+\cdots +(n_k-1)d_k)}} ,\nonumber
\end{align}
with dimensions $d_1>\cdots >d_k$, be a basic Gaussian partition. If $(a,b)$ is a  dimension-preserving split  with $a+b=d_i$, then neither the spine obtained by applying $(a,b)$ to $T$ simultaneously one through $q^{n_1d_1+\cdots +(n_i-1)d_i}-1$ times, nor the set of restricted Gaussian partitions obtained from the spine, contains a basic partition. However, with an additional application of the split $(a,b)$ to the last partition on the spine, we obtain another basic Gaussian partition $T'$.
\end{proposition}

\begin{proof} As long as the largest power of $q$ in the exponent of $d_i$ is partially decomposed, the Gaussian partition cannot be basic, because the exponent of $d_i$ does not correctly reflect the Addition Property in Proposition~\ref{add-prop}. However, once the highest power of $q$ in the exponent of $d_i$ is completely dissolved, we do get a basic partition: this partition is 
\begin{align}
T'&=d_1^{\, 1+q^{d_1}+\cdots +q^{(n_1-1)d_1}}\cdots d_i^{\, q^{( n_1d_1+\cdots +n_{i-1}d_{i-1})}+\cdots +  q^{(n_1d_1+\cdots +(n_i-2)d_i)}  }\nonumber\\
& a^{\, q^{(n_1d_1+\cdots +(n_i-1)d_i)}} b^{\, q^{(n_1d_1+\cdots +(n_i-1)d_i+a)}} d_{i+1}^{\, q^{(n_1d_1+\cdots +n_id_i)}+\cdots     }\cdots\nonumber
\end{align}
The exponents of $a$ and $b$, as well as the expression $q^{n_1d_1}$ in the exponent of $d_{i+1}$, conform to the addition property; note that $a+b=d_i$, and equalities in the expression $a\geq b\geq d_{i+1}$ are allowed.
\end{proof}

\begin{proposition}\label{norep} A restricted Gaussian partition 
is uniquely defined by its basic ancestor and the set of 
splits applied to it.
\end{proposition}

\begin{proof} This proof depends implicitly on the uniqueness of the base-$q$ representation of positive integers. Every non-basic restricted Gaussian partition $T'$ starts from {\em some} basic Gaussian partition $T$  by definition.  It turns out that $T$ can be uniquely reconstructed due to the structure of basic partitions described  in Proposition~\ref{obviousone}: let
\[ T=d_1^1d_2^{\, q^{\, d_1}}d_3^{\, q^{\, d_1+d_2}}\cdots d_k^{\, q^{\, d_1+\cdots +d_{k-1}}}.\]
The original dimensions $d_1\geq \cdots \geq d_k$ of $T$ are all present in $T'$. In fact, if $k\geq 2$, then $d_1$ and $d_2$ must be the leftmost two numbers in $T'$, when dimensions are written in nonincreasing order without exponents, because of Definition~\ref{restga}. If the total exponent of $d_2$ is already $q^{\, d_1}$, then we factor out this power, and the next number to the right has to be $d_3<d_2$. If the total exponent exceeds $q^{\, d_1}$, then we understand that $d_3=d_2$, separate $d_2^{\, q^{d_1}}$, and check if the total exponent of $d_3$ is $q^{d_1+d_2}$, etc. As soon as we hit an exponent of some $d_i$ that falls short of the Addition Property in Proposition~\ref{add-prop}, the first split $(a,b)$ applied to $d_i$ can be identified by the first integer $a<d_i$ to the right of the $d_i$'s. If $a^{\alpha}$ is the collection of all $a$'s in $T'$, then we can locate $(d_i-a)^{\alpha q^a}=b^{\alpha q^a}$ somewhere to the right (and the next integer, if any, must be $d_{i+1}$). All subsequent splits in nested intervals, if any, can be put together in this fashion, from outside towards inside, owing to Definition~\ref{restga}. Then we start working on $d_{i+1}$, and so on, until all splits are repaired backwards and $T$ is re-created.
\end{proof}

\subsection{Some preliminary counting}

We will use the following lemma, which states Faulhaber's formula~\cite{CoGu} for the sums of consecutive powers.

\begin{lemma}[Sums of Consecutive Powers~\cite{CoGu}]\label{powers} 
Let $N$ and $m$ be any nonnegative integers. Then the familiar sum
\[ \th_m(N)=\sum_{k=1}^N k^m\]
of the first $N$ consecutive $m$-th powers of $k$ is a rational polynomial in $N$, with $\th_m(0)=0$ (when $N=0$, 
the empty sum is equal to zero). An explicit formula for $\th_m(N)$ can be given in terms of the Bernoulli 
numbers $B_k$:
\begin{equation}\label{eq:conspow}
\th_m(N)=\frac{1}{m+1}\sum_{k=0}^m\binom{m +1}{k}(-1)^kB_k\, N^{m+1-k}.
\end{equation}
\end{lemma}

\begin{corollary}\label{poly} Let $N$ be a positive integer, and $S(x)$ be any rational polynomial. Then the sum
\[ U(N)=\sum_{k=1}^N S(k)\]
is a rational polynomial in $N$, with $U(0)=0$.
\end{corollary}

\begin{proof} Let $S(x)=a_0+a_1x+\cdots +a_tx^t$, with $a_i\in\mathbb{Q}$. Then, in the notation of 
Lemma~\ref{powers}, the sum
\[ U(N)=a_0\sum_{k=1}^N1+a_1\sum_{k=1}^Nk+\cdots +a_t\sum_{k=1}^Nk^t=a_0\th_0(N)+a_1\th_1(N)+\cdots +a_t\th_t(N)\]
is a $\mathbb{Q}$-linear combination of rational polynomials in $N$ with $N=0$ as a root.
\end{proof}


Let $N$ be an unspecified positive integer and $k$ be a variable that may take on the integer values $1,2,\dots,N$. 
Recall that we denote the set $\{ 1,2,\dots,k\}$ by {\bf k}. We define  a sequence of multisets 
$A_0(N)$, $A_1(N)$, $A_2(N)$, ... by the following recursive rule: we set $A_0(N)=\{ N\}$, and replace each occurrence 
of an integer $k$ in the set $A_i(N)$ by all elements of the set {\bf k} in $A_{i+1}(N)$. 
Thus
\[A_{i+1}(N)=\biguplus_{k=1}^N A_i(k),\]
where $\uplus$ denotes the {\em multiset sum}. The first few multisets in this sequence are
\begin{align*}
A_0(N)&=\{ N\}, \quad A_1(N)=\biguplus_{k=1}^N A_0(k)= \mbox{\bf N}=\{ 1,2,\dots ,N\}, \mbox{ and } \\
A_2(N)&= \biguplus_{k=1}^N A_1(k)= \mbox{\bf 1}\uplus \mbox{\bf 2}\uplus\cdots\uplus \mbox{\bf N}=\{ 1\} \uplus \{ 1,2\} \uplus \cdots\uplus \{ 1,2,\dots, N\}.
\end{align*}

\begin{corollary}\label{repeatedsums}
Let $1_{A_i(N)}(k)$ denote the multiplicity of the integer $k$ in the multiset $A_i(N)$. For $i\geq 0$, let 
\[ S_i(N)=\sum_{k=1}^N k\cdot 1_{A_i(N)}(k),\]
the sum of all elements of the multiset $A_i(N)$ counted with multiplicities. Then

 $(1)$ For each $i\geq 0$, we have
\[ S_{i+1}(N)=\sum_{k=1}^NS_i(k).\]

 $(2)$ For each $i\geq 0$, the expression $S_i(N)$ is a rational polynomial in $N$, with $S_i(0)=0$.
\end{corollary}

\begin{proof} Part $(1)$  follows immediately from the definition of $A_i$ as a sum of multisets 
and the additive property of the multiplicity function. For part $(2)$, we note that $S_0(N)=N=\th_0(N)$, and 
\[ S_1(N)=\sum_{k=1}^Nk=\sum_{k=1}^NS_0(k)=\th_1(N).\]
By Corollary~\ref{poly} and part $(1)$, it is clear that each subsequent $S_i(N)$ is a polynomial with the desired properties.
\end{proof}

\subsection{Adding up}

\begin{proposition}\label{counting} Let $T$ be a basic Gaussian partition of $V(n,q)$  given by
\[ T=d_1^1d_2^{\, q^{\, d_1}}d_3^{\, q^{\, d_1+d_2}}\cdots d_k^{\, q^{\, d_1+\cdots +d_{k-1}}},\]
where $d_1\geq\cdots\geq d_k$ and $d_1+\ldots+d_k=n$. Then the number of all restricted Gaussian partitions obtained from  $T$ is a rational polynomial in $q$. Moreover, $q=1$ is a root of this polynomial.
\end{proposition}

\begin{remark}
The restricted Gaussian partitions obtained from $T$ according to the rules in Section~\ref{looklike} are necessarily non-basic by Proposition~\ref{obvioustwo}.
\end{remark}

\begin{proof} In the special cases of a basic Gaussian partition $T$ for which the only dimension-preserving splits create other basic partitions, or where all $d_i=1$, the polynomial in question is the zero polynomial. Henceforth, we assume that it is possible to obtain non-basic regular Gaussian partitions from $T$. Since sequences of splits are applied to one dimension $d_i$ at a time, it suffices to show that the number of Gaussian partitions obtained from one $d_i$ is a polynomial $P_i(q)$ of the desired type. Again, we single out the cases where it is not possible to fit any splits to $d_i$, and declare that in these cases $P_i(q)=1$. However, there will be at least one  factor $P_i(q)$ that is a rational polynomial with $1$ as a root by our assumption. The total number for $T$ will be the product $P_T(q)$ of all $P_i(q)$. 

Thus, assume that the restricted Gaussian partitions obtained from $T$ only contain changes to $d_i$, and that $q^u$ is the largest power of $q$ in the exponent of $d_i$.  Let $N=q^u-1$ and recall the notation of Corollary~\ref{repeatedsums}. Now, several different splits $(a,b)$ may be allowed for $d_i$ (i.e., we have $a+b=d_i$ and $d_i>a\geq b\geq d_{i+1}$), but any given restricted Gaussian partition may contain only one of these, possibly applied several times (see Section~\ref{looklike}). Simultaneous applications of a  split $(a,b)$ results in a total of $N=S_0(N)$ possible Gaussian partitions on a spine, where the set of exponents of $a$ is $\{ 1,2,\dots,N\}=A_1(N)$.  If there are $t_0=t_0(i)$ possible splits $(a,b)$ of $d_i$, then there must be $t_0S_0(N)$ Gaussian partitions that have exactly one more kind of split than $T$ has in their construction, because spines are disjoint by Proposition~\ref{norep}. 

For any one of the first splits $(a,b)$ of $d_i$, let $(c,d)$ be one of the next generation of splits (that is, $c+d=a$, and $a>c\geq d\geq b$). Then each  $a^k$  on the spine will generate  a new set of exponents for $c$ on a spinelet, namely, ${\bf k}=\{1,2,\ldots,k\}$. The multiset $A_2(N)$ will contain all exponents of $c$ thus generated, and $S_1(N)$ new Gaussian partitions that contain only $(a,b)$ and $(c,d)$ in their construction sequence (starting from  $T$) will be created. If there are $t_1=t_1(i)$ possible sets of back-to-back splits $(a,b)$ and $(c,d)$ applied to $d_i$, then the number of Gaussian partitions that are obtained from $T$ by splitting $d_i$ with only two kinds of new splits is $t_1S_1(N)$, as once again Proposition~\ref{norep} tells us that there cannot be any repetitions of Gaussian partitions when different sequences of splits are employed. We continue in this manner as far as possible.

If $t_r=t_r(i)$ denotes the number of all distinct back-to-back split sequences of length $r+1$ applied to $d_i$, and if the maximum possible length of such sequences is $m=m(i)$, then the total number of restricted Gaussian partitions that can be obtained from $T$ by splitting only $d_i$  is given by the rational polynomial
\[ P_i(q)=t_0S_0(N)+\cdots +t_{m-1}S_{m-1}(N),\]
which must have $q=1$ as a root by Corollary~\ref{repeatedsums}. The product
\[ P_{T}(q)=\prod_{i=1}^k P_i(q)\]
is hence the total number of restricted Gaussian partitions obtained from $T$, a rational polynomial with $P_{T}(1)=0$. Note that the numbers $u$, $N$, $m$, and $t_1,\dots,t_{m-1}$ depend on $i$, but we are suppressing references to $i$ for simplicity of notation. 
\end{proof}

As an immediate corollary of Proposition~\ref{counting}, we obtain the proof of our main result.

\begin{proof}[Proof of Theorem~\ref{thm:main}] The total number of basic Gaussian partitions is $p(n)$, and each basic partition $T$ produces $P_{T}(q)$ non-basic restricted partitions. Then the total number of restricted Gaussian partitions 
of $V(n,q)$ is given by
\[ R(q)=p(n)+\sum_{T}P_{T}(q),\]
which is a rational polynomial in $q$ with $R(1)=p(n)+\sum_{T}0=p(n)$.
\end{proof}

\section{Acknowledgment}
We thank the referee whose comments helped improve the presentation of this paper.


\begin{thebibliography}{18}

\bibitem{AS2} F.\ Akman and P.\ Sissokho, The lattice of finite subspace partitions, {\em Discrete Math.} {\bf 312} (2012), 1487--1491.

\bibitem{AS1} F.\ Akman and P.\ Sissokho, Gaussian partitions, {\em Ramanujan J.} {\bf 28} (2012), 125--138. 

\bibitem{An}J. Andr\'e, \"{U}ber nicht-Desarguessche Ebenen mit transitiver Translationsgruppe, {\em Math.\ Z.} {\bf 60} (1954), 156--186.

\bibitem{Ba} R.\ Baer, Partitionen endlicher Gruppen,
{\em Math.\ Z.} {\bf 75} (1960/61), 333--372.

\bibitem{Be1} A.\ Beutelspacher, Partial spreads in finite projective spaces  and partial designs, {\em Math.\ Z.} {\bf 145} (1975), 211--229.

\bibitem{Be2} A.\ Beutelspacher, Partitions of finite vector spaces:
an application of the Frobenius number in geometry, 
{\em Arch.\ Math.} {\bf 31} (1978), 202--208.

\bibitem{Bu} T.\ Bu, Partitions of a vector space, {\em Discrete Math.} {\bf 31} (1980), 79--83.

\bibitem{BB} R. Bruck and R. Bose, The construction of translation planes from projective planes,
{\em J.\ Algebra } {\bf  1} (1964), 85--102.

\bibitem{CoGu} J. Conway and  R. Guy, {\em The Book of Numbers}, Springer,  1996, p.\ 107.

\bibitem{DrFr} D. Drake and J. Freeman, Partial $t$-spreads and group constructible
 $(s,r,\mu)$-nets, {\em J. Geom.} {\bf 13} (1979), 211--216.

\bibitem{EiStSz} J. Eisfeld, L. Storme, and P. Sziklai, On the spectrum 
of the sizes of maximal partial line spreads in $PG(2n,q)$, $n\geq3$, 
{\em Des.\ Codes Cryptogr.} {\bf 36}  (2005), 101--110.

\bibitem{EJSSS} S. El-Zanati, H. Jordon, G. Seelinger, P. Sissokho, and L. Spence, 
The maximum size of a partial $3$-spread in a finite vector space over $\GF(2)$,
{\em Des. Codes Cryptogr.} {\bf 54} (2010), 101--107.

\bibitem{EZ} S. El-Zanati, G. Seelinger, P. Sissokho, L. Spence, and
C. Vanden Eynden, Partitions of finite vector spaces into subspaces,
{\em J. Combin. Des.} {\bf 16} (2008), 329--341.

\bibitem{HeSv} O. Heden, A survey of the different types of vector space partitions, 
{\em Disc. Math. Algo. Appl.} {\bf 4} (2012), 1--14.

\bibitem{He0} O. Heden, A survey on perfect codes,
{\em Adv. Math. Commun.} {\bf 2} (2008), 223--247.


\bibitem{HeT} O. Heden, On the length of the tail of a vector space partition,
{\em Discrete Math.} {\bf 309} (2009), 6169--6180.

\bibitem{HeLe} J. Lehmann and O. Heden, Some necessary conditions for vector space partitions, 
{\em Discrete Math.} {\bf 312} (2012), 351--361.

\bibitem{HLNS2} O. Heden, J. Lehmann, E. N\u{a}stase, and P. Sissokho, 
The supertail of a subspace partition,
{\em Des. Codes Cryptogr.} {\bf 69} (2013), 305--316.

\bibitem{HeSc2} M.\ Herzog and J.\ Sch\"{o}nheim,
Group partition, factorization and the
vector covering problem, {\em Canad.\ Math.\ Bull.} {\bf 15} (1972), 207--214.

\bibitem{HoPa} S. Hong and A. Patel, A general class of maximal codes
for computer applications, {\em IEEE Trans.\ Comput.} {\bf C-21} (1972),
1322--1331.

\bibitem{KoKs} R. Koetter and F. R. Kschischang, Coding for errors and
erasures in random network coding, {\em IEEE Trans.\ Infor.\ Theor.}
{\bf 54} (2008), 3579--3591.

\bibitem{La} L. Lambert, Random network coding and designs over ${\mathbb F}_q$,
{\em Master's thesis} Ghent University, Belgium, 2013.

\bibitem{Li} B. Lindstr\"{o}m, Group partitions and mixed perfect codes, 
{\em Canad. Math. Bull.} {\bf 18} (1975), 57--60.

\bibitem{Mi} G. Miller, Groups in which all operators are contained in a series 
of subgroups such that any two have only the identity in common,
{\em Bull. Amer. Math. Soc.} {\bf 12} (1905--1906), 446--449.

\bibitem{SSSV} G. Seelinger, P. Sissokho, L. Spence, and C. Vanden Eynden, 
Partitions of $V(n,q)$ into  $2$-and $s$-dimensional subspaces,
{\em J. Combin. Des.} {\bf 20} (2012), 467--482.

\bibitem{Th1} S. Thomas, Designs over finite fields, {\em
Geom. Dedicata} {\bf 24} (1987), 237--242.

\bibitem{Za} G. Zappa, Partitions and other coverings of finite groups, 
{\em Illinois J. Math.}, {\bf 47} (2003), 571--580.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A17; Secondary 11P83,  51E20.

\noindent \emph{Keywords: } 
subspace partition, vector space partition, Gaussian partition, integer
partition, $q$-analogue.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  September 5 2014;
revised versions received  December 16 2014; July 15 2015.
Published in {\it Journal of Integer Sequences},
July 16 2015.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}