\documentclass[12pt,reqno]{amsart}


\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{latexsym,boxedminipage}
\usepackage{epsfig}


\textwidth 6.0in
\textheight 8.5in
\topmargin -0.25in
\oddsidemargin 0.25in
\parskip .1in

\newcommand{\Om}{\begin{array}{c}{\Omega}\vspace{-.1cm}\\{\ge}\end{array}}
\newcommand{\la}{\lambda}
%\newcommand{\la}{\lambda_1}
%\newcommand{\lb}{\lambda_2}
%\newcommand{\lc}{\lambda_3}
%\newcommand{\lk}{\lambda_k}
\newcommand{\bof}{\noindent{\bf Proof}}
%\newcommand{\qed}{\hfill{$\Box$}}
\newcommand{\ld}{\left(}
\newcommand{\rd}{\right)}
\newcommand{\C}{{\mathcal C}}


\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
%\newtheorem{observation}{Remark}


\title[Enumeration of Constrained Sequences]{Enumeration of Sequences Constrained by the Ratio of Consecutive Parts}

\author[Sylvie Corteel, Sunyoung Lee, and Carla D. Savage]{Sylvie Corteel*,
Sunyoung Lee$^\dagger$,
and
Carla D. Savage$^\ddagger$
}

\thanks{\hbox{* CNRS PRiSM, UVSQ,
 45 Avenue des Etats-Unis,
 78035 Versailles, France.}\newline
({\tt syl@prism.uvsq.fr})}

\thanks{$^\dagger$ 
Computer Science,
North Carolina  State University, Box 8206, 
 Raleigh, NC 27695, USA.
({\tt slee7@unity.ncsu.edu})
Research supported in part by NSF grant DMS-0300034.
}

\thanks{$^\ddagger$ 
{Computer Science,}
 {North Carolina State University, Box 8206, }
{ Raleigh, NC 27695, USA}.
({\tt savage@csc.ncsu.edu})
{Research supported in part by NSF grants DMS-0300034 and INT-0230800}.
}

%\date{November 13, 2004; Revised March 3, 2005}

\begin{document}

\begin{abstract}
Recurrences are developed to enumerate any family of nonnegative
integer sequences
 $\la=(\la_1, \ldots, \la_n)$
satisfying the constraints:
\[
\frac{\la_1}{a_1} \geq
\frac{\la_2}{a_{2}} \geq
\cdots \geq
\frac{\la_{n-1}}{a_{n-1}} \geq
\frac{\la_{n}}{a_{n}} \geq 0,
\]
for a given constraint sequence ${\bf a}=[a_1, \ldots, a_n]$ of positive
integers.  They are applied to derive new counting formulas, to reveal
new relationships between families, and to give simple proofs of the
truncated lecture hall and anti-lecture hall theorems.


\vspace{.2in}


\noindent 
{\sc R\'esum\'e}.
Nous d\'eveloppons des r\'ecurrences pour \'enum\'erer des familles de
suites d'entiers
$\lambda=(\lambda_1,\ldots ,\lambda_n)$
satisfaisant les contraintes
$$
\frac{\la_1}{a_1} \geq
\frac{\la_2}{a_{2}} \geq
\cdots \geq
\frac{\la_{n-1}}{a_{n-1}} \geq
\frac{\la_{n}}{a_{n}} \geq 0,
$$
pour une suite d'entiers positifs 
donn\'ee ${\bf a}=[a_1,\ldots ,a_n]$. Ces r\'ecurrences
permettent
de d\'eriver de nouvelles formules d\'enum\'eration, de r\'ev\'eler de
nouvelles relations entre certaines familles, et de donner des preuves 
simples
des th\'eor\`emes des partitions Lecture Hall tronqu\'ees et des 
compositions
Lecture Hall tronqu\'ees.


\end{abstract}
\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54A \rms (2005), Article~B54Aa\hfill}
\def\thepage{}
%
%

\section{Introduction}
%In this abstract,
We consider the problem of enumerating
 nonnegative integer sequences $\la=(\la_1, \ldots,\break \la_n)$
satisfying the constraints:
\begin{equation}
\frac{\la_1}{a_1} \geq
\frac{\la_2}{a_{2}} \geq
\cdots \geq
\frac{\la_{n-1}}{a_{n-1}} \geq
\frac{\la_{n}}{a_{n}} \geq 0,
\label{intro_constraints}
\end{equation}
for a given constraint sequence ${\bf a}=[a_1, \ldots, a_n]$ of positive
integers. 

We refer to a sequence $\la=(\la_1, \ldots, \la_n)$ of nonnegative
integers as a {\em composition} into $n$ nonnegative parts.
If the parts of $\la$ are nonincreasing, then $\la$ is a {\em partition}.
Partitions and compositions are commonly
defined by the set of parts allowed, the number of
occurrences of a part, or the difference between consecutive parts.
In contrast, the compositions satisfying (\ref{intro_constraints})
are constrained by the ratio of
consecutive parts and we
refer to them as
{\em ratio compositions}.  
Generating functions are known  for ratio compositions
only for
some special constraint sequences, ${\bf a}$, including:

\vspace{-.4in}
\begin{quote}
\item
${\bf a}=[1,1, \ldots, 1]$:  ordinary partitions \cite{top};
\item
${\bf a}=[1,2,4, \ldots, 2^{n-1}]$:
Cayley compositions \cite{cayley,RRreciprocal,minc0,PA5}; 
\item
${\bf a}=[r^{n-1},r^{n-2}, \ldots, r, 1]$:
Hickerson partitions \cite{hickerson};
\item
${\bf a} =[n,n-1,\ldots,1]$: lecture hall partitions \cite{BME1,BME2,BME3,yee1,yee2,PA1};
\item
${\bf a}=[1,2,\ldots,n]$:
anti-lecture hall compositions \cite{anti};
\item
${\bf a}=[1,2,1,2,...,2-(-1)^n]$: one-two compositions \cite{ineq1};  
\item
${\bf a}=[n, n-1 \ldots, n-t+1]$:
truncated lecture hall partitions \cite{CS2};
\item
${\bf a}=[n-t+1,n-t, \ldots, n]$:
truncated anti-lecture hall compositions~\cite{CS2}. 
%$k,l$-lecture hall partitions \cite{}
\end{quote}
%We will refer to compositions defined by the constraints
%(\ref{intro_constraints}) for some positive integer sequence
%$a=[a_1,a_2, \ldots, a_n]$
In this paper, we introduce a common approach for the enumeration 
of ratio compositions
by using as a statistic a bound on the size of the first part.
This generalizes the enumeration of ordinary partitions via  the Gaussian
polynomials.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL SYLVIE CORTEEL, SUNYOUNG LEE, AND CARLA D. SAVAGE}{\SMALL ENUMERATION OF CONSTRAINED SEQUENCES}
%
%

In Section 2, we derive a recurrence for the generating function of
{\em any} family of ratio compositions with first part {\em bounded}.
We use this
to derive  new counting formulas and their $q$-analogs. 
Among these,  
we discover a family of polynomials with several interesting properties
which arise in
the enumeration of lecture hall partitions.
In addition, we find a functional relationship between the generating
functions for the ratio compositions  constrained by a
sequence $[a_1,a_2, \ldots, a_n]$ and those constrained by its reverse 
sequence $[a_n, a_{n-1} \ldots,  a_1]$.  This reveals for the
first time the relationship between, e.g., lecture hall partitions
and anti-lecture hall compositions and between Hickerson partitions and
Cayley compositions.

In Section 3, we derive a different recurrence for the enumeration of
ratio compositions with first part bounded. 
By allowing the bound to approach infinity, we get a recurrence for the
generating function of {\em any} family of ratio compositions with first part
{\em unbounded}.  As one consequence, we discover new 
``easy'' proofs of the (truncated) lecture hall 
and (truncated) anti-lecture hall theorems.  In contrast to earlier
proofs, where deriving a recurrence was a challenge,  here the
recurrence is generic  and the work is
moved entirely to ``standard'' $q$-series manipulation in an induction proof.


\section{Enumeration of ratio compositions with first part bounded}

%Let ${\bf s}= \{s_i\}$
 %be an infinite sequence of positive integers.
To build a recurrence, let 
  %we first consider the case where
%the constraint sequence ${\bf a}$ in (\ref{intro_constraints})
$[a_1, \ldots, a_n]=
[s_n,s_{n-1}, \ldots, s_1]$ for an
  infinite sequence of positive integers
$\{s_i\}$.
For $n \geq 0$,
let $S_n$ be the set of compositions $\la = (\la_1, \la_2, \ldots, \la_n)$
satisfying
\begin{equation}
\frac{\la_1}{s_n} \geq 
\frac{\la_2}{s_{n-1}} \geq 
\cdots \geq
\frac{\la_{n-1}}{s_{2}} \geq 
\frac{\la_{n}}{s_{1}} \geq 0.
\label{s_constraints}
\end{equation}
%We refer to the sequence $s$ as the {\em constraint sequence}.
Let $S_n^{(j,i)}$ be the set  of $\la \in S_n$ with $\la_1 \leq js_n+i$
and let
\[
S_n^{(j,i)}(q) = \sum_{\la \in S_n^{(j,i)}} q^{|\la|}.
\]
\begin{theorem}
For $n \geq 0$, $j \geq 0$, and $0 \leq i \leq s_n$,
\[
S_n^{(j,i)}(q)=  \left \{
\begin{array}{ll}
1 & \mbox{if $n=0$ or $j=i=0$, else}\\
S_n^{(j-1,s_n)}(q) & \mbox{if $i=0$, else} \\
S_n^{(j,i-1)}(q)+ q^{js_n+i}S_{n-1}^{(j,\lfloor is_{n-1}/s_n \rfloor)}(q) & \mbox{otherwise}. \\
\end{array}
\right.
\]
\label{Sgf}
\end{theorem}
\noindent
{\bf Proof.}  The theorem is clearly true for $n=0$ and for $j=i=0$.
Let $(n,j,i)$ satisfy $n>0$, $(j,i)>(0,0)$.
If $i=0$, then $j>0$ and $js_n+i=js_n=(j-1)s_n+s_n$, so the theorem is true.
Assume, then, that $1 \leq i \leq s_n$.
By definition, $\la \in S_n^{(j,i)}$ if and only if either
$\la \in S_n^{(j,i-1)}$ or
$\la \in S_{n}$ and
$\la_1 = js_n+i$.  But $(js_n+i, \la_2, \ldots, \la_n) \in S_n$
if and only if $(\la_2, \ldots, \la_n) \in S_{n-1}$ and
$(js_n+i)/\la_2 \geq s_n/s_{n-1}$.  That is,
\[
\la_2 \leq \frac{s_{n-1}}{s_n}(js_n+i)=js_{n-1}+i\frac{s_{n-1}}{s_n}.
\]
So, since $\la_2$ is an integer, 
\[
\la_2 \leq js_{n-1}+\lfloor i\frac{s_{n-1}}{s_n}\rfloor.
\]
Note, since $1 \leq i \leq s_n$, $\lfloor is_{n-1}/{s_n}\rfloor \leq
s_{n-1}$, so
$(\la_2, \ldots, \la_n) \in S_{n-1}^{(j,\lfloor is_{n-1}/s_n \rfloor)}$.
\hfill{$\Box$}

\noindent
{\bf Remark 1.}
For ordinary partitions, $P_n$, into $n$ nonnegative parts,
 $\{s_i\}=\{1\}$ and
$\lfloor is_{n-1}/s_n \rfloor =i$, so the recurrence of Theorem~\ref{Sgf}
reduces to the recurrence
\[
P_n^{(j,i)}(q)=
P_n^{(j,i-1)}(q)+
q^{j+i}P_{n-1}^{(j,i)}(q),
\]
the familiar recurrence for Gaussian polynomials.

The {\em lecture hall partitions} \cite{BME1}, $L_n$,  are those
compositions, necessarily partitions,
satisfying
\begin{equation}
\frac{\la_1}{n} \geq
\frac{\la_2}{{n-1}} \geq
\cdots \geq
\frac{\la_{n-1}}{{2}} \geq
\frac{\la_{n}}{{1}} \geq 0.
\label{lhpconstraints}
\end{equation}
Then $L_n=S_n$
with  $\{s_i\}=\{i\}$ in (\ref{s_constraints}).
Since $\lfloor i(n-1)/n \rfloor = i-1$ we get the following
from Theorem~\ref{Sgf}.

\begin{corollary}
For $n \geq 0$, $j \geq 0$, and $0 \leq i \leq n$,
let  $L_n^{(j,i)}(q)$ be the generating function for the
lecture hall partitions
$\la \in L_n$ with $\la_1 \leq jn+i$.
\[
L_n^{(j,i)}=  \left \{
\begin{array}{ll}
1 & \mbox{if $n=0$ or $j=i=0$, else}\\
L_n^{(j-1,n)}(q) & \mbox{if $i=0$, else} \\
L_n^{(j,i-1)}(q)+ q^{jn+i}L_{n-1}^{(j,i-1)}(q) & \mbox{otherwise}. \\
\end{array}
\right.
\]
\label{Lgf}
\end{corollary}

For fixed $n>0$, any $t\geq 0$ can be written uniquely in the form $t=jn+i$, where
$0 \leq i < n$.  So, 
we get a nice counting formula for lecture hall partitions with largest part at most $t$.

\begin{theorem}
For $n \geq 0$, $j \geq 0$, and $0 \leq i \leq n$,
the number of lecture hall partitions in $L_n$ with first part
bounded by $jn+i$ is
\[
L_n^{(j,i)}=(j+1)^{n-i}(j+2)^{i}.
\]
\label{countLnij}
\end{theorem}
\noindent
{\bf Proof.}
If $n=0$ then $i=0$, so $(j+1)^{0-0}(j+2)^{0}=1$.
If $i=j=0$, then $(1)^{n-0}(2)^{0}=1$.
Let $(n,j,i)$ satisfy $n>0$, $(j,i)>(0,0)$  and assume
the theorem is true for $(n',i',j')<(n,i,j)$.
If $i=0$, then $j>0$ and by Corollary \ref{Lgf},
$L_n^{(j,0)}(1)=L_n^{(j-1,n)}(1)$, which, by
induction, is $(j)^{n-n}(j+1)^{n}=(j+1)^{n}(j+2)^{0}$.
Otherwise, by Corollary \ref{Lgf},
\begin{eqnarray*}
L_n^{(j,i)}(1) & = & L_n^{(j,i-1)}(1)+ L_{n-1}^{(j,i-1)}(1)\\
& =&
(j+1)^{n-i+1}(j+2)^{i-1}+(j+1)^{n-i}(j+2)^{i-1}\\
& =&
(j+1)^{n-i}(j+2)^{i}.
\end{eqnarray*}
\hfill{$\Box$}

In \cite{BME1}, it was shown that the generating function for the lecture hall partitions,
$L_n$ is:
\begin{equation}
L_n(q) = \frac{1}{(q;q^2)_n},
\label{lht}
\end{equation}
where $(a;q)_n=(1-a)(1-aq) \cdots (1-aq^{n-1})$.
Let $D$ be the set of partitions into distinct parts
and let $O$ be the set of partitions into odd parts.  The sets $D$ and $O$ have generating functions
$D(q)=(-q;q)_{\infty}$  and $O(q)=(q;q^2)_{\infty}^{-1}$, respectively.
Since $\lim_{n \rightarrow \infty}L_n=D$,
the Lecture Hall Theorem (\ref{lht}) is a finite version of Euler's Theorem
 which says that
$D(q)=O(q)$.  The polynomial $L_n^{(j)}(q)=L_n^{(j,0)}(q)$ can be viewed as a $q$-analog of $(j+1)^n$ that
encapsulates a further finitization of Euler's Theorem in the following sense.
\begin{corollary}
The lecture hall  polynomials $L_n^{(j)}(q)$ satisfy

{\rm (i)}  $L_n^{(j)}(1)=(j+1)^n$,

{\rm (ii)}  $\lim_{n \rightarrow \infty} L_n^{(j)}(q)= (-q;q)_{\infty}$,
 and

{\rm (iii)}  $\lim_{j \rightarrow \infty} L_n^{(j)}(q)= (q;q^2)_{n}^{-1}$.
\label{polynomials}
\end{corollary}

\begin{proof} The first equation follows from Theorem~\ref{countLnij}.  The second and third follow from the
observations that
$\lim_{n \rightarrow \infty} L_n^{(j)}=D$ and $\lim_{j \rightarrow \infty} L_n^{(j)}=L_n$.
\end{proof}

The {\em anti-lecture hall compositions} \cite{anti}, $A_n$,  are those sequences
satisfying
\begin{equation}
\frac{\la_1}{1} \geq
\frac{\la_2}{{2}} \geq
\cdots \geq
\frac{\la_{n-1}}{{n-1}} \geq
\frac{\la_{n}}{{n}} \geq 0.
\label{alhconstraints}
\end{equation}
It was shown in \cite{anti} that $A_n$ has generating function
$A_n(q)=(-q,q)_n/(q^2;q)_n$.
The constraint sequence for $A_n$, in the sense of
(\ref{intro_constraints}), is $[1,2, \dots, n]$,  the
{\em reverse} of the constraint sequence  $[n,n-1, \ldots, 1]$ for
$L_n$.
  %We show, for any defining sequence $(s_1,s_2, \ldots, s_n)$,
%a relationship between  
%$S_n$
%and the set $T_n$ defined by the reverse sequence
%$(s_n,s_{n-1}, \ldots, s_1)$.
We introduce some notation to describe the relationship between their
generating functions.
Let $S[a_1,a_2, \ldots,a_k]$ be the set of compositions
$\la = (\la_1, \la_2, \ldots, \la_n)$
satisfying
\begin{equation}
\frac{\la_1}{a_1} \geq
\frac{\la_2}{a_{2}} \geq
\cdots \geq
\frac{\la_{n-1}}{a_{n-1}} \geq
\frac{\la_{n}}{a_{n}} \geq 0,
\label{a_constraints}
\end{equation}
with
$S^{(j,i)}[a_1,a_2, \ldots,a_n]$ denoting those with 
$\la_1 \leq ja_1+i$
and let
$S^{(j)}[a_1,a_2, \ldots,a_n]=
S^{(j,0)}[a_1,a_2, \ldots,a_n]$.
\begin{theorem}
The generating functions for $S^{(j)}[a_1,a_2, \ldots,a_n]$
and $S^{(j)}[a_n,a_{n-1}, \ldots,a_1]$ satisfy:
\[
S^{(j)}[a_1,a_2, \ldots,a_n](q)= q^{j(a_1+a_2+ \cdots + a_n)}
S^{(j)}[a_n,a_{n-1}, \ldots,a_1](1/q).
\label{reverse}
\]
\end{theorem}

%\begin{theorem}
%Given a sequence $(s_1, s_2, \ldots, s_n)$ of positive integers,
%let $S_n$ be the set of sequences defined by (\ref{constraints})
%and $T_n$ the sequences defined by
%\begin{equation}
%\frac{\la_1}{s_1} \geq
%\frac{\la_2}{{s_2}} \geq
%\cdots \geq
%\frac{\la_{n-1}}{s_{n-1}} \geq
%\frac{\la_{n}}{{s_n}} \geq 0.
%\label{alhconstraints}
%\end{equation}
%Let $T_{n,j}(q)$ and $S_{n,j}(q)$ be defined by
%\[
%S_{n,j}(q) = \sum_{\la \in S_n, \ \la_1 \leq js_n}q^{|\la|}; \ \ \ 
%T_{n,j}(q) = \sum_{\la \in T_n, \ \la_1 \leq js_1}q^{|\la|}.
%\]
%Then
%\[
%T_{n,j}(q)=q^{j(s_1+s_2+ \cdots + s_n)}S_{n,j}(1/q).
%\]
%\label{reverse}
\noindent
{\bf Proof.}
The result follows if we show that
$\la \in S^{(j)}[a_n,a_{n-1}, \ldots,a_1]$
if and only if $\mu \in 
S^{(j)}[a_1,a_2, \ldots,a_n]$,
 where
$\mu$ is defined by $\mu_i=js_i-\la_{n+1-i}$.
%From this it follows that
%\[
%T_{n,j}(x_1,x_2, \ldots, x_n)=(x_1x_2^2x_3^3\cdots x_n^n)^j
%S_{n,j}(1/x_n,1/x_{n-1}, \ldots, 1/x_1),
%\]
%where
%\[
%S_{n,j}(x_1,x_2, \ldots, x_n) = \sum_{\la \in S_n, \ \la_1 \leq js_n}
%x_1^{\la_1}
%x_2^{\la_2} \cdots
%x_n^{\la_n}; \ \ \
%T_{n,j}(x_1,x_2, \ldots, x_n) = \sum_{\la \in T_n, \ \la_1 \leq js_1}
%x_1^{\la_1}
%x_2^{\la_2} \cdots
%x_n^{\la_n}. \ \ \
%\]
%giving the result of the theorem.


So,  assume 
$\la \in S^{(j)}[a_n,a_{n-1}, \ldots,a_1]$,
 that is,
$\la_1 \leq ja_n$ and $a_i\la_{n-i}\geq a_{i+1}\la
_{n+1-i}$
for $1 \leq i \leq n$.
Then for $1 \leq i \leq n$,
\[
\la_{n+1-i} \leq \frac{a_i}{a_{i+1}}\frac{a_{i+1}}{a_{i+2}} \cdots 
\frac{a_{n-1}}
{a_n}a_n j = a_ij,
\]
so $\mu_i = ja_i - \la_{n+1-i} \geq 0$.
Also, $\mu_1=ja_1-\la_n$ satisfies $\mu_1 \leq ja_1$.  To show 
$\mu \in S^{(j)}[a_1,a_{2}, \ldots,a_{n}]$,
it remains to show $a_{i+1}\mu_i \geq a_i\mu_{i+1}$:
\[
a_{i+1}\mu_i=a_{i+1}(ja_i-\la_{n+1-i})=ja_ia_{i+1}-a_{i+1}\la_{n+1-i}
\geq ja_ia_{i+1}-a_i\la_{n-i}=a_i\mu_{i+1}.
\]




The converse is similar.
\hfill{$\Box$}

\noindent
{\bf Remark 2.}
The proof of Theorem~\ref{reverse} also shows that
for $1 \leq i \leq n$, $\la \in S^{(j)}[a_n,a_{n-1},\break \ldots,a_1]$
if and only if $\mu \in S^{(j+1)}[a_1,a_{2}, \ldots,a_{n}]$ and 
$\mu_n \geq a_n-i$.

\begin{corollary}
Lecture hall partitions, $L_n^{(j)}$, with first part bounded by
$jn$  and anti-lecture hall compositions, $A_n^{(j)}$ with first
part bounded by $j$ have the following relationship:
\[
A_n^{(j)}(q)=q^{jn(n+1)/2}L_n^{(j)}(1/q).
\]
\end{corollary}

\begin{proof}
Observe that $A_n^{(j)}=S^{(j)}[1,2, \ldots, n]$ and
$L_n^{(j)}=S^{(j)}[n,n-1, \ldots, 1]$ and apply Theorem~\ref{reverse}.
\end{proof}

This gives
a counting formula for
anti-lecture hall compositions.
\begin{corollary}
The number of anti-lecture hall compositions in $A_n$ with first
part bounded by $j$ is
\[
A_n^{(j)}(1)=(j+1)^{n}.
\]
\end{corollary}
\noindent
{\bf Proof.}
By Theorem~\ref{reverse},
$A_n^{(j)}(1)=L_n^{(j)}(1)$.  By definition, 
$L_n^{(j)}(q)=L_n^{(j,0)}(q)$, and by Corollary \ref{countLnij},
$L_n^{(j,0)}(1) =(j+1)^{n}(j+2)^{0}$.
\hfill{$\Box$}

As another example of the application of Theorems~\ref{Sgf} and \ref{reverse},
we consider Hickerson partitions $H_n$ (for $r=2$)
and Cayley compositions, $C_n$.
$H_n$ is the set of compositions into $n$ nonnegative parts
satisfying $\la_i \geq 2\la_{i+1}$ and
$C_n$ is the set of compositions into $n$ nonnegative parts
satisfying $\la_i \geq \la_{i+1}/2$.
So, $H_n=S[2^{n-1},2^{n-2}, \ldots, 1]$ and
$C_n=S[1,2,4, \ldots, 2^{n-1}]$.
Let $B(n)$ be the number of {\em binary partitions} of $n$, i.e.,
the number of partitions of $n$ into powers of 2.
It is easy to check that
$B(0)=B(1)=1$, $B(2n)=B(2n-2)+B(n)$, and $B(2n)=B(2n+1)$.
\begin{theorem}
For $0 \leq i < 2^{n-1}$, the number of Hickerson partitions with first part
at most $i$ is $H_n^{(0,i)}=B(2i)$;
with first part
at most $2^{n-1}+i$ is $H_n^{(1,i)}=B(2^n+2i)$;
with first part
at most $2^{n}$ is $H_n^{(2,0)}=B(2^{n+1})-1$.
\label{hickerson_theorem}
\end{theorem}

\begin{proof}
Use the recurrence of Theorem~\ref{Sgf} with the observation that
since $\{s_i\}=\{2^{i-1}\}$ for Hickerson partitions, 
$\lfloor is_{i-1}/s_i \rfloor = \lfloor i/2 \rfloor$.
The theorem follows by induction using the properties of $B(n)$.
\end{proof}


Cayley's Theorem \cite{cayley} says that the number of compositions in $C_n$ with
$n$ {\em positive} parts and 
with first part 1 is equal to the number of partitions
of $2^{n-1}-1$ into parts from the set $\{1, 1', 2, 4, \ldots, 2^{n-2}\}$.
If we apply Theorem~\ref{reverse} and Remark~2,  we get a generalization and
reformulation of Cayley's Theorem.
\begin{theorem}
For $0 \leq i <2^{n-1}$, the number of Cayley compositions into $n$ positive parts
 with first part 1 and last part at least $2^{n-1}-i$ is $B(2i)$.
The number with first part at most 2 and last part at least $2^n-i$ is
$B(2^n+2i)$.
\label{cayley_theorem}
\end{theorem}
Setting $i= 2^{n-1}-1$ in Theorem~\ref{cayley_theorem} gives:
\begin{corollary}
The number of Cayley compositions into $n$ positive parts with first part 1 is
$B(2^n-2)$; with first part at most 2 is $B(2^{n+1}-2)$.
\end{corollary}

These results can be generalized to $r$-ary Hickerson partitions and
Cayley compositions.  For other families of ratio compositions,
we can expect Theorem~\ref{Sgf} to be most useful for sequences $\{s_i\}$ where
$\lfloor is_{n-1}/s_n \rfloor$ has a nice form.

As $t$ gets larger, solving for $H_n^{(t)}$ gets harder.
This is in spite of the fact that $H_n$ has the nice generating
function
$H_n(q)=\prod_{t=1}^{n}(1-q^{2^t-1})^{-1}$ \cite{hickerson}.
However, we will see in the next section that if $S_n^{(j)}(q)$
has a nice generating function when $j=1$, there is hope that
$\lim_{j \rightarrow \infty}S_n^{(j)}(q)$ will also.
%We have computed $S_n^{(1)}$ for several families, with results
%like ...

In the next section we show how
to get a recurrence
for the generating function of ratio compositions when the first part
{\em unrestricted}.

\section{Enumeration of ratio sequences with first part unbounded.}

We define two slight variations of the set $S^{(j)}[a_1,a_2, \ldots,a_n]$
below:
\[
P^{(j)}[a_1,a_2, \ldots,a_n] = 
\{ \la \in S^{(j)}[a_1,a_2, \ldots,a_n] \ | \ \la_n \geq 1\};
\]
\[
R^{(j)}[a_1,a_2, \ldots,a_n] = 
\{ \la \in S^{(j)}[a_1,a_2, \ldots,a_n] \ | \ \la_1 <ja_1\}.
\]
In $P^{(j)}$, all parts must be positive, whereas in $R^{(j)}$
parts can be nonnegative, but the bound on the first part becomes
strict.
%We will need the notion of {\em truncated sequences}.
%Let $(a_1,a_2, \ldots,a_k)$ be a sequence of positive integers.
%Let $S[a_1,a_2, \ldots,a_k]$ be the set of sequences  of positive integers
%$\la = (\la_1, \la_2, \ldots, \la_k)$ 
%satisfying
%\begin{equation}
%\frac{\la_1}{a_1} \geq
%\frac{\la_2}{a_{2}} \geq
%\cdots \geq
%\frac{\la_{k-1}}{a_{k-1}} \geq
%\frac{\la_{k}}{a_{k}} \geq 1.
%\label{trunc_constraints}
%\end{equation}
%Let $S^{(j)}[a_1,a_2, \ldots,a_k]$  be the set  of $\la \in S[a_1,a_2, \ldots,a_k]$ with
%$\la_1 \leq ja_1$
%and let
%\[
%S^{(j)}[a_1,a_2, \ldots,a_k](q)
%= \sum_{\la \in S^{(j)}[a_1,a_2, \ldots,a_k]} q^{|\la|}.
%\]
\begin{theorem}
For $j \geq 1$,
%$P^{(0)}[a_1,a_2, \ldots,a_k](q)=1$ and 
%for $j\ge 1$, 
$$
P^{(j)}[a_1,a_2, \ldots,a_k](q)= \sum_{t=0}^k q^{(a_1+a_2+\cdots+a_t)}
P^{(1)}[a_{t+1}, \ldots, a_k](q)
P^{(j-1)}[a_1, \ldots, a_t](q).
$$
\label{bigrec}
\end{theorem}

\begin{proof}
Let $\lambda \in
P^{(j)}[a_1,a_2, \ldots,a_k]$ and  let $t$ be the maximum index such that
$\lambda_t>a_{t}$. Then $(\lambda_1-a_1,\lambda_2-a_2,\ldots
,\lambda_t-a_t) \in P^{(j-1)}[a_1, \ldots, a_t]$
and $(\lambda_{t+1},\ldots ,\lambda_k) \in
P^{(1)}[a_{t+1}, \ldots, a_k]$.
\end{proof}

Note that $P^{(1)}(q)$ can be computed using Theorem~\ref{Sgf} as 
\[
P^{(1)}[s_n, \ldots, s_1](q)=
S_n^{(1,0)}[s_1, \ldots, s_n](q)-
S_{n-1}^{(1,0)}[s_2, \ldots, s_n](q).
\]
Thus,
taking the limit as $j \rightarrow \infty$ in Theorem~\ref{bigrec}
gives a recurrence for counting the sequences $\la$ in 
$P[a_1,a_2, \ldots,a_k]$ without
a restriction on the size of the first part.
\begin{theorem}
For $n\ge k$,
$$
P[a_1,a_2, \ldots,a_k](q)= \sum_{t=0}^k q^{(a_1+a_{2} + \cdots + a_{t})}
P^{(1)}[a_{t+1}, \ldots,a_k](q)
P[a_1,a_2, \ldots,a_t](q).
$$
\label{infrec}
\end{theorem}

\noindent
{\bf Remark 3.}
%Let $R[a_1,a_2, \ldots,a_k]$ be the set of sequences  of positive integers
%$\la = (\la_1, \la_2, \ldots, \la_k)$
%satisfying
%\begin{equation}
%\frac{\la_1}{a_1} \geq
%\frac{\la_2}{a_{2}} \geq
%\cdots \geq
%\frac{\la_{k-1}}{a_{k-1}} \geq
%\frac{\la_{k}}{a_{k}} \geq 0
%\label{R_constraints}
%\end{equation}
%and let
 %$R^{(j)}[a_1,a_2, \ldots,a_k]$  be the set  of $\la \in R[a_1,a_2, \ldots,a_
%k]$ with
%$\la_1 < ja_1$, with
%$R^{(j)}[a_1,a_2, \ldots,a_k](q)$ defined accordingly.
Theorem~\ref{bigrec} and its proof are valid with all occurrences of $P$
replaced by $R$.  We need only change the statement
``let $t$ be the maximum index such that $\lambda_t>a_{t}$''
to
``let $t$ be the maximum index such that $\lambda_t \geq a_{n-t+1}$''.
Similarly, Theorem~\ref{infrec} holds with $P$ replaced by $R$.


Theorem~\ref{infrec} can be used
to find an explicit form for the generating function in families
where
$P^{(1)}[a_1, \ldots, a_k]$ 
(or $R^{(1)}[a_1, \ldots, a_k]$) 
is known.  

\noindent
{\bf Remark 4.}
For ordinary partitions into $k$ positive parts, $a_i=1$, so
$$P[a_1,a_2, \ldots,a_k](q)=(q;q)_k^{-1}$$ and
$$P^{(1)}[a_{t+1}, \ldots,a_k](q) = q^{k-t},$$ and the recurrence of
Theorem~\ref{infrec} becomes
\[
\frac{1}{(q;q)_k} =  \sum_{t=0}^k \frac{q^{k}}{(q;q)_t},
\]
which counts partitions into $k$ positive parts by summing over the
number, $t$, of parts greater than 1.
\qed

The partitions $L_{n,k}=P[n,n-1, \ldots, n-k+1]$ are called
{\em truncated lecture hall partitions} with all parts positive.
The compositions $A_{n,k}=R[n-k+1,n-k+2, \ldots, n]$ are called
{\em truncated anti-lecture hall compositions} with nonnegative
parts.  These were introduced in \cite{CS2} where their generating
functions were shown to be
\begin{equation}
L_{n,k}(q)= q^{\binom {k+1}
2}\left[\begin{array}{c}n\\k\end{array}\right]_q
\frac{(-q^{n-k+1};q)_k}{(q^{2n-k+1};q)_k},
\label{tlht}
\end{equation}
\begin{equation}
A_{n,k}(q)=\left[\begin{array}{c}n\\k\end{array}\right]_q
\frac{(-q^{n-k+1};q)_k}{(q^{2(n-k+1)};q)_k}.
\label{talht}
\end{equation}

%\noindent
%{\bf Remark 5.}
%The methods of Section 2 can be used  to show:
%\[
%|L_{n,k}^{(j)}|=
%|A_{n,k}^{(j)}|= (j+1)^k {n \choose k}.
%\]
%We defer the proof to the full paper.

We  now show  how Theorem~\ref{infrec} can be used to give simple
proofs of the (Truncated) Lecture Hall and (Truncated) Anti-lecture
Hall Theorems.
We begin by computing  $P^{(1)}[n,n-1, \ldots, n-k+1](q)$ for $L_{n,k}$ and 
$R^{(1)}[n-k+1,n-k+2, \ldots, n](q)$
for $A_{n,k}$.

\begin{lemma}
For $n \geq k \geq 1$, 
the generating function for  truncated lecture hall partitions into $k$ positive parts
with first part less than or equal to $n$ is
\[
P^{(1)}[n,n-1, \ldots, n-k+1](q)=
q^{{\binom {k+1} 2}}\left[\begin{array}{c}n\\k\end{array}\right]_q. \]
\label{S1}
\end{lemma}

\begin{proof}  We show that 
$P^{(1)}[n,n-1, \ldots, n-k+1]$ is the set of partitions
into $k$ distinct parts from $\{1,2, \ldots, n\}$, which has the generating
function claimed.
If $\la \in P^{(1)}[n,n-1, \ldots, n-k+1]$,
$1 \geq \la_1/n \geq \la_2/(n-1) \geq \cdots \geq \la_k/(n-k+1) > 0$,
so the parts of $\la$ are distinct and bounded by $n$.
Conversely, if $\la_i \geq \la_{i+1}+1$ for $1 \leq i \leq n-1$
and $\la_1 \leq n$, then $\la_{i+1} \leq n-i$, so
\[
\la_i(n-i) \geq
 (\la_{i+1}+1)(n-i) \geq
 \la_{i+1}(n-i)+n-i \geq
 \la_{i+1}(n-i)+\la_{i+1} \geq
 \la_{i+1}(n-i+1),
\]
that is, $\la_i/(n-i+1) \geq \la_{i+1}/(n-i)$, so $\la \in P^{(1)}[n,n-1, \ldots, n-k+1]$.
\end{proof}

\begin{lemma}
For $n \geq k \geq 1$,
the  generating function for  truncated anti-lecture hall compositions into $k$ nonnegative
parts 
with first part less than  $n-k+1$ is
\[
R^{(1)}[n-k+1,n-k+2, \ldots, n](q)=
\left[\begin{array}{c}n\\k\end{array}\right]_q. \]
\label{R1}
\end{lemma}

\begin{proof}  If $\la \in R^{(1)}[n-k+1,n-k+2, \ldots, n]$, then for
$1 \leq i \leq n$, $\la_i < n-k+i$ and
$\la_{i-1} \geq \la_i(n-k+i-1)/(n-k+i)$, so
\[
\la_{i-1}-\la_i \geq
\la_{i}((n-k+i-1)/(n-k+i)-1) = -\la_i/(n-k+i) > -1.
\]
Thus, $\la_{i-1}-\la_i \geq 0$ and $\la$ is a partition into at most
$k$ parts of size at most $n-k$.  Conversely, any such partition is
in $R^{(1)}[n-k+1,n-k+2, \ldots, n]$.
\end{proof}

\begin{corollary}
\[
|L_{n,k}^{(j)}|=
(j)^k {\binom n  k}=
|A_{n,k}^{(j)}|.
\]
\end{corollary}

\begin{proof}
By induction. It is obviously true for
$j=0$. Then for $j>0$, by Theorem~\ref{bigrec} and Lemma~\ref{R1},
$$
L^{(j)}_{n,k}(1)= \sum_{t=0}^k{\binom {n-t} { k-t}}{\binom n
t}(j-1)^t.
$$
We use the classical identity ${\binom {n-t} {k-t}}{\binom n
t}={\binom nk}{\binom k t}$ and the binomial theorem and get the
result.   By Theorem~\ref{reverse},
$L_{n,k}^{(j)}(1)= A_{n,k}^{(j)}(1)$.
\end{proof}





\begin{lemma}
The generating function for truncated lecture hall partitions
satisfies
$$
L_{n,k}(q)=q^{\binom {k+1} 2} \sum_{t=0}^k q^{(n-k)t}
\left[\begin{array}{c}n-t\\k-t\end{array}\right]_qL_{n,t}(q),
$$
for $k \geq 1$ and $L_{n,0}(q)=1$.
\label{lhplemma}
\end{lemma}
\begin{proof}
Since $L_{n,k}=P[n,n-1, \ldots, n-k+1]$,
apply Theorem~\ref{infrec} with Lemma~\ref{S1} to get
\[
L_{n,k}(q) = 
\sum_{t=0}^k q^{n+(n-1)+ \cdots + (n-t+1)}q^{\binom {k-t+1} 2}
\left[\begin{array}{c}n-t\\k-t\end{array}\right]_qL_{n,t}(q)
\]
and simplify.
\end{proof}
%\left[\begin{array}{c}n-t\\k-t\end{array}\right]_qL_{n,t}(q).
%\left[\begin{array}{c}n-t\\k-t\end{array}\right]_qL_{n,t}(q).
%q^{k+1\choose 2} 
%\sum_{t=0}^k q^{(n-k)t}
%\left[\begin{array}{c}n-t\\k-t\end{array}\right]_qL_{n,t}(q).








%Let $${\mathcal
%L}^{}_{n,k}(q)=\frac{L^{}_{n,k}(q)}{q^{k+1\choose
%2}\left[\begin{array}{c}n\\k\end{array}\right]_q}.$$

 %As
%$\left[\begin{array}{c}n-t\\k-t\end{array}\right]_q\left[\begin{array}{c}n\\t\end{array}\right]_q
%=\left[\begin{array}{c}n\\k\end{array}\right]_q\left[\begin{array}{c}k\\t\end{array}\right]_q,
%$ for $j\ge 2$
%\begin{equation}
%{\mathcal L}^{}_{n,k}(q)=\sum_{t=0}^k q^{(n-k)t+{t+1\choose
%2}}\left[\begin{array}{c}k\\t\end{array}\right]_q{\mathcal L}^{}_{n,t}(q)
%\end{equation}
%and ${\mathcal L}^{}_{n,1}=1$.


%Let ${\mathcal L}_{n,k}(q)={\mathcal L}^{j,0}_{n,k}$ as
%$j\rightarrow \infty$.

%\begin{theorem}
%$${\mathcal
%L}_{n,k}(q)=\frac{(-q^{n-k+1};q)_k}{(q^{2n-k+1};q)_k}.
%$$
%\end{theorem}
%\noindent{\bf Proof.}
%Substituting for $L_{n,k}(q)$ and $L_{n,t}(q)$
%in the
%recurrence of Lemma \ref{lhplemma}
%and simplifying gives
%${\mathcal L}^{}_{n,1}=1$ and for $k>1$,
%$${\mathcal
%L}_{n,k}(q)=\sum_{t=0}^k q^{(n-k)t+{t+1\choose
%2}}\left[\begin{array}{c}k\\t\end{array}\right]_q{\mathcal
%L}_{n,t}(q),
%$$
%as
%$$\left[\begin{array}{c}n-t\\k-t\end{array}\right]_q\left[\begin{array}{c}n\\t\end{array}\right]_q
%=\left[\begin{array}{c}n\\k\end{array}\right]_q\left[\begin{array}{c}k\\t
%\end{array}\right]_q.
%$$
%We show ${\mathcal L}_{n,k}(q)$, as given by the theorem satisfies this
%recurrence.

%We make use of (a transformation of) one of the $q$-Chu Vandermonde identities
%[1.5.2] from \cite{gasper}:
%$$
%\frac{(-aq;q)_k}{(cq;q)_k}=\sum_{t=0}^ka^tq^{t+1\choose 2}
%\left[\begin{array}{c}k \\t\end{array}\right]_q
%\frac{(-(c/a)q^{-t+1};q)_t}{(cq^{k-t+1};q)_t}.
%$$
%We do the substitution $a=q^{n-k}$ and $c=q^{2n-k}$ and get
%$$
%\frac{(-q^{n-k+1};q)_k}{(q^{2n-k+1};q)_k}=\sum_{t=0}^k
%q^{t(n-k)+{t+1\choose 2}} \left[\begin{array}{c}k
%\\t\end{array}\right]_q
%\frac{(-q^{n-t+1};q)_t}{(q^{2n-t+1};q)_t},
%$$
%which is exactly the recurrence we just established.\qed


This gives the Truncated Lecture Hall Theorem:

 %. Let $L_{n,k}$ be
%the set of partitions $\lambda$ such that
%$$
%\frac{\lambda_1}{n}\ge \ldots\ge \frac{\lambda_k}{n-k+1}>0.
%$$
%and
%$$
%L_{n,k}(q)=\sum_{\lambda\in L_{n,k}}q^{|\lambda|}.
%$$
\begin{theorem}{\rm \cite{CS2}}
$$
L_{n,k}(q)= q^{\binom {k+1}
2}\left[\begin{array}{c}n\\k\end{array}\right]_q
\frac{(-q^{n-k+1};q)_k}{(q^{2n-k+1};q)_k}.
$$
\label{tlhtheorem}
\end{theorem}
\noindent{\bf Proof.}
Let $${\mathcal
L}^{}_{n,k}(q)=\frac{L^{}_{n,k}(q)}{q^{\binom {k+1}
2}\left[\begin{array}{c}n\\k\end{array}\right]_q}.$$
We show
\begin{equation}
{\mathcal
L}_{n,k}(q)=\frac{(-q^{n-k+1};q)_k}{(q^{2n-k+1};q)_k}.
\label{calL}
\end{equation}
Substituting for $L_{n,k}(q)$ and $L_{n,t}(q)$
in the
recurrence of Lemma~\ref{lhplemma}
and simplifying gives
${\mathcal L}^{}_{n,1}=1$ and for $k>1$,
\begin{equation}{\mathcal
L}_{n,k}(q)=\sum_{t=0}^k q^{(n-k)t+{\binom {t+1}
2}}\left[\begin{array}{c}k\\t\end{array}\right]_q{\mathcal
L}_{n,t}(q),
\label{calLrec}
\end{equation}
as
$$\left[\begin{array}{c}n-t\\k-t\end{array}\right]_q\left[\begin{array}{c}n\\t
\end{array}\right]_q
=\left[\begin{array}{c}n\\k\end{array}\right]_q\left[\begin{array}{c}k\\t
\end{array}\right]_q.
$$
%We show ${\mathcal L}_{n,k}(q)$, as given by the theorem satisfies this
%recurrence.
We make use of (a transformation of) one of the $q$-Chu Vandermonde identities
(1.5.2) from \cite{gasper}:
$$
\frac{(-aq;q)_k}{(cq;q)_k}=\sum_{t=0}^ka^tq^{\binom {t+1} 2}
\left[\begin{array}{c}k \\t\end{array}\right]_q
\frac{(-(c/a)q^{-t+1};q)_t}{(cq^{k-t+1};q)_t}.
$$
We do the substitution $a=q^{n-k}$ and $c=q^{2n-k}$ and get
$$
\frac{(-q^{n-k+1};q)_k}{(q^{2n-k+1};q)_k}=\sum_{t=0}^k
q^{t(n-k)+{\binom {t+1} 2}} \left[\begin{array}{c}k
\\t\end{array}\right]_q
\frac{(-q^{n-t+1};q)_t}{(q^{2n-t+1};q)_t},
$$
%We show ${\mathcal L}_{n,k}(q)$, as given by the theorem satisfies this
%recurrence.
which shows that ${\mathcal L}_{n,k}(q)$ as given by (\ref{calL}) 
is the solution to the recurrence (\ref{calLrec}).
%which is exactly the recurrence we just established.\qed
%ZZZZZZZZZZZZZZZZ
 %$ L_{n,k}(q)= q^{k+1\choose
%2}\left[\begin{array}{c}n\\k\end{array}\right]_q{\mathcal
%L}_{n,k}(q).$\qed
%ZZZZZZZZZZZZZZZZ

From this we also get the Lecture Hall Theorem:

 %et $L_{n}$ be the set of
%partitions $\lambda$ such that
%$$
%\frac{\lambda_1}{n}\ge \ldots\ge \frac{\lambda_n}{1}\ge 0.
%$$
%and
%$$
%L_{n}(q)=\sum_{\lambda\in L_{n}}q^{|\lambda|}.
%$$


\begin{theorem}{\rm \cite{BME1}}
$$
L_{n}(q)=\frac{(-q;q)_n}{(q^{n+1};q)_n}=\frac{1}{(q;q^2)_n}.
$$
\end{theorem}
\begin{proof} Setting $k=n$ in Theorem~\ref{tlhtheorem}
gives  $L_{n,n}$, which is the set of partitions in $L_n$ with
all parts positive.
So, $L_{n,n}(q)=q^{{\binom {n+1} 2}}L_n(q)$.
\end{proof}


%\begin{theorem}
%$$
%L^{(j,0)}_{n,k}(q)=q^{k+1\choose 2}
%\left[\begin{array}{c}n\\k\end{array}\right]_q \sum_{k\ge t_1\ge
%t_{2}\ge \ldots\ge t_{j-1}\ge
%0}q^{\sum_{i=1}^{j-1}(n-t_{i-1})t_i+{t_i+1\choose
%2}}\left[\begin{array}{c}k\\
%t_1-t_{2},\ldots ,t_{j-1}-t_{j-2},k-t_{j-1}
%\end{array}\right]
%$$
%where $t_0$ is set to $k$.
%$$
%L_{n}^{(j,0)}(q)=\sum_{n\ge t_{1}\ge t_2\ge \ldots\ge t_{j}\ge
%0}q^{\sum_{i=1}^{j}(n-t_{i-1})t_i+{t_i+1\choose
%2}}\left[\begin{array}{c}n\\
%t_{1}-t_2,t_2-t_{3},\ldots ,t_{j}-t_{j-1},n-t_{j}
%\end{array}\right].
%$$
%where $t_0$ is set to $n$.
%\end{theorem}

%\noindent{\bf Proof.} Then if we apply the recurrence $j-1$ times
%we get
%$$
%{\mathcal L}^{(j,0)}_{n,k}(q)=\sum_{k\ge t_1\ge t_{2}\ge \ldots\ge
%t_{j-1}\ge 0}q^{\sum_{i=1}^{j-1}(n-t_{i-1})t_i+{t_i+1\choose
%2}}\left[\begin{array}{c}k\\
%t_1-t_{2},\ldots ,t_{j-1}-t_{j-2},k-t_{j-1}
%\end{array}\right]
%$$
%where $t_0$ is set to $k$.\qed


%\begin{corollary}
%$$
%L^{(j,0)}_{n,k}(1)=j^k{n\choose k}
%$$
%\end{corollary}
%\noindent{\bf Proof.} By induction. It is obviously true for
%$j=0$. Then for $j>0$
%$$
%L^{(j,0)}_{n,k}(1)= \sum_{t=0}^k{n-t\choose k-t}{n\choose
%t}(j-1)^t.
%$$
%We use the classical identity ${n-t\choose k-t}{n\choose
%t}={n\choose k}{k\choose t}$ and the binomial theorem and get the
%result.\qed

The approach for
truncated anti-lecture hall compositions is similar.

\begin{lemma}
For  $n\ge k$,
$$
A_{n,k}(q)=\sum_{t=0}^k q^{(n-k)t+{\binom {t+1} 2}}
\left[\begin{array}{c}n\\k-t\end{array}\right]_q
A_{n-k+t,t}(q)
$$
with $A^{(0)}_{n,k}(q)=1$.
\label{antilemma}
\end{lemma}

\begin{proof}
Since $A_{n,k}=R[n-k+1,n-k+2, \ldots, n]$,
apply Theorem~\ref{infrec}, using Remark~3, then Lemma~\ref{R1}
and simplify.
\end{proof}

%Let $\lambda$ be a composition counted by
%$A^{(j)}_{n,k}(q)$. Let $t$ be the maximum index such that
%$\lambda_t\ge n-k+t$. Then
%$(\lambda_1-(n-k+1),\lambda_2-(n-k+2),\ldots ,\lambda_t-(n-k+t))$
%is a composition counted by $A^{(j-1)}_{n-k+t,t}(q)$ and
%$(\lambda_{t+1},\ldots ,\lambda_k)$ is a partition into non
%negative parts less or equal to $n-k+t$. \qed



%\noindent
%{\bf Remark 6.} Note that for $n=k$ we get
%$$
%A_n(q)=\sum_{t=0}^n q^{{t+1\choose 2}}
%\left[\begin{array}{c}n\\t\end{array}\right]_q A^{}_{t}(q),
%$$
%with $A_{n}(q)=A_{n,n}(q)$.\\


 %Let $${\mathcal A^{(j)}_{n,k}(q)}=\frac{A^{(j)}_{n,k}(q)}{
%\left[\begin{array}{c}n\\k\end{array}\right]_q}.$$ Then using the
%previous recurrence we get that
%\begin{equation}
%{\mathcal A}^{(j)}_{n,k}(q)=\sum_{t=0}^k q^{(n-k)t+{t+1\choose 2}}
%\left[\begin{array}{c}k\\t\end{array}\right]_q {\mathcal
%A}^{(j-1)}_{n-k+t,t}, \label{recamath}
%\end{equation}
%as $
%\left[\begin{array}{c}n\\k\end{array}\right]_q\left[\begin{array}{c}k\\k-t\end{array}\right]_q=
%\left[\begin{array}{c}n-k+t\\t\end{array}\right]_q\left[\begin{array}{c}n\\k-t\end{array}\right]_q.$
%

%Therefore
%\begin{proposition}
%$$
%A^{(j)}_{n,k}(q)=\left[\begin{array}{c}n\\k\end{array}\right]_q
%\sum_{k\ge t_j\ge \ldots \ge t_1\ge 0}q^{\sum_{i=1}^j(n-k)
%t_i+{t_i+1\choose
%2}}\left[\begin{array}{c}k\\k-t_j,t_j-t_{j-1},\ldots,t_2-t_1,t_1
%\end{array}\right]_q.
%$$
%\end{proposition}
%
%\noindent{\bf Proof.} Apply $j-1$ times the recurrence of
%${\mathcal A}^{(j)}_{n,k}(q)$ and multiply by
%$\left[\begin{array}{c}n\\k\end{array}\right]_q$.\qed

Now we get an easy proof of the Truncated Anti-lecture Hall
Theorem.
\begin{theorem} {\rm \cite{CS2}}
$$
A_{n,k}(q)=\left[\begin{array}{c}n\\k\end{array}\right]_q
\frac{(-q^{n-k+1};q)_k}{(q^{2(n-k+1)};q)_k}.
$$
\label{truncated-anti}
\end{theorem}
\begin{proof}
 Let $${\mathcal A^{}_{n,k}(q)}=\frac{A^{}_{n,k}(q)}{
\left[\begin{array}{c}n\\k\end{array}\right]_q}.$$ Then using
Lemma~\ref{antilemma},
we get that
\begin{equation}
{\mathcal A}^{}_{n,k}(q)=\sum_{t=0}^k q^{(n-k)t+{\binom {t+1} 2}}
\left[\begin{array}{c}k\\t\end{array}\right]_q {\mathcal
A}^{}_{n-k+t,t}(q), \label{recamath}
\end{equation}
as $$
\left[\begin{array}{c}n\\k\end{array}\right]_q\left[\begin{array}{c}k\\k-t
\end{array}\right]_q=
\left[\begin{array}{c}n-k+t\\t\end{array}\right]_q\left[\begin{array}{c}n\\k-t
\end{array}\right]_q.$$
 %The generating function $A_{n,k}(q)$ is
%${A^{(j)}_{n,k}(q)}$ with $j\rightarrow \infty$. Let
 %${\mathcal
%A}_{n,k}(q)$ be ${\mathcal A}^{(j)}_{n,k}(q)$ as $j\rightarrow
%\infty$. The recurrence of equation (\ref{recamath}) implies that
%$$
%{\mathcal A}_{n,k}(q)=\sum_{t=0}^k q^{(n-k)t+{t+1\choose 2}}
%\left[\begin{array}{c}k\\t\end{array}\right]_q {\mathcal
%A}_{n-k+t,t}.$$ 

We make use of another transformation of  the
$q$-Chu Vandermonde identity
(1.5.2) from \cite{gasper}:
$$
\frac{(-c/a;q)_k}{(c;q)_k}=\sum_{t=0}^k(c/a)^tq^{\binom t
2}\left[\begin{array}{c}k\\t\end{array}\right]_q 
\frac{(-a;q)_t}{(c;q)_t}.
$$
Set $c=q^{2(n-k+1)}$ and $a=q^{n-k+1}$ and get
$$
\frac{(-q^{n-k+1};q)_k}{(q^{2(n-k+1)};q)_k}=\sum_{t=0}^k
q^{(n-k)t+{\binom {t+1}
2}}\left[\begin{array}{c}k\\t\end{array}\right]_q
\frac{(-q^{n-k+1};q)_k}{(q^{2(n-k+1)};q)_k},
$$
showing
${\mathcal
A}_{n,k}(q)=\frac{(-q^{n-k+1};q)_k}{(q^{2(n-k+1)};q)_k}$
satisfies the recurrence.
\end{proof}

Setting $k=n$ in Theorem~\ref{truncated-anti} gives the Anti-Lecture Hall Theorem.
\begin{theorem} {\rm \cite{anti}}
\[
A_{n}(q)= \frac{(-q;q)_n}{(q^2;q)_n}.
\]
\end{theorem}

\section{Concluding Remarks}
The recurrences of Theorems~\ref{Sgf} and \ref{infrec}
 provide simple computational
tools to investigate any family of ratio compositions.
More importantly, they supply the foundation for an inductive proof
of any conjectured enumeration result.
Our experiments suggest that counting formulas and generating
functions will be possible for many other families of ratio
compositions.

One particular question of interest is to characterize the subfamily
of partitions into odd parts in $\{1,3, \ldots, 2n-1\}$ that is counted
by the polynomial $L_n^{(j)}(q)$.

\begin{thebibliography}{10}

\bibitem{top}
George~E. Andrews.
\newblock {\em The theory of partitions}.
\newblock Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976.
\newblock Encyclopedia of Mathematics and its Applications, Vol. 2.

\bibitem{RRreciprocal}
George~E. Andrews.
\newblock The {R}ogers-{R}amanujan reciprocal and {M}inc's partition function.
\newblock {\em Pacific J. Math.}, 95(2):251--256, 1981.

\bibitem{PA1}
George~E. Andrews.
\newblock Mac{M}ahon's partition analysis. {I}. {T}he lecture hall partition
  theorem.
\newblock In {\em Mathematical essays in honor of Gian-Carlo Rota (Cambridge,
  MA, 1996)}, volume 161 of {\em Progr. Math.}, pages 1--22. Birkh\"auser
  Boston, Boston, MA, 1998.

\bibitem{PA5}
George~E. Andrews, Peter Paule, Axel Riese, and Volker Strehl.
\newblock Mac{M}ahon's partition analysis. {V}. {B}ijections, recursions, and
  magic squares.
\newblock In {\em Algebraic combinatorics and applications (G\"o\ss weinstein,
  1999)}, pages 1--39. Springer, Berlin, 2001.

\bibitem{BME1}
Mireille Bousquet-M\'elou and Kimmo Eriksson.
\newblock Lecture hall partitions.
\newblock {\em Ramanujan J.}, 1(1):101--111, 1997.

\bibitem{BME2}
Mireille Bousquet-M\'elou and Kimmo Eriksson.
\newblock Lecture hall partitions {II.}
\newblock {\em Ramanujan J.}, 1(2):165--185, 1997.

\bibitem{BME3}
Mireille Bousquet-M\'elou and Kimmo Eriksson.
\newblock A refinement of the lecture hall theorem.
\newblock {\em J. Combin. Theory. Ser. A}, 86(1):63--84, 1999.

\bibitem{cayley}
Arthur Cayley.
\newblock On a problem in the partition of numbers.
\newblock {\em Philosophical Magazine}, 13:245--248, 1857.
\newblock reprinted in: {T}he {C}ollected {M}athematical {P}apers of {A}.
  {C}ayley, {V}ol. {I}{I}{I}, {C}ambridge {U}niversity {P}ress, {C}ambridge,
  1890, 247-249).

\bibitem{anti}
Sylvie Corteel and Carla~D. Savage.
\newblock Anti-lecture hall compositions.
\newblock {\em Discrete Math.}, 263(1-3):275--280, 2003.

\bibitem{CS2}
Sylvie Corteel and Carla~D. Savage.
\newblock Lecture hall theorems, {$q$}-series and truncated objects.
\newblock {\em J. Combin. Theory Ser. A}, 108(2):217--245, 2004.

\bibitem{ineq1}
Sylvie Corteel and Carla~D. Savage.
\newblock Partitions and compositions defined by inequalities.
\newblock {\em Ramanujan J.}, 8(3):357--381, 2004.

\bibitem{gasper}
George Gasper and Mizan Rahman.
\newblock {\em Basic hypergeometric series}, volume~35 of {\em Encyclopedia of
  Mathematics and its Applications}.
\newblock Cambridge University Press, Cambridge, 1990.
\newblock With a foreword by Richard Askey.

\bibitem{hickerson}
Dean~R. Hickerson.
\newblock A partition identity of the {E}uler type.
\newblock {\em Amer. Math. Monthly}, 81:627--629, 1974.

\bibitem{minc0}
Henryk Minc.
\newblock A problem in partitions: {E}numeration of elements of a given degree
  in the free commutative entropic cyclic groupoid.
\newblock {\em Proc. Edinburgh Math. Soc. (2)}, 11:223--224, 1958/1959.

\bibitem{yee1}
Ae~Ja Yee.
\newblock On the combinatorics of lecture hall partitions.
\newblock {\em Ramanujan J.}, 5(3):247--262, 2001.

\bibitem{yee2}
Ae~Ja Yee.
\newblock On the refined lecture hall theorem.
\newblock {\em Discrete Math.}, 248(1-3):293--298, 2002.

\end{thebibliography}



\end{document}
