\documentclass[12pt]{article}
\usepackage{amsmath,amssymb}

%%%%
\textwidth= 6.5in
\textheight= 9.0in
\topmargin = -20pt
\evensidemargin=0pt
\oddsidemargin=0pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
%%%


\def\theequation{\thesection.\arabic{equation}}
\def\supp{\mathop{\rm supp}}


\makeatletter %% this should really go into a style file!

\renewcommand\section{\@startsection {section}{1}{\z@}%
                                 % {-3.5ex \@plus -1ex \@minus -.2ex}%
        % here is your vskip of 30pt:
                                   {-30pt  \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\normalfont\normalsize\bfseries}}

\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
                                     {-3.25ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
        % add a point after section numbers:

\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad}

\makeatother

\begin{document}
\vspace*{-40pt}
\centerline{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7
(2007), \#A25}
\vskip 40pt
\begin{center}
{\bf COMPUTATION OF $q$-PARTIAL FRACTIONS}
\vskip 20pt
{\bf Augustine O. Munagi}\\
{\small \it The John Knopfmacher Centre for Applicable Analysis and Number Theory,
University of the Witwatersrand, Johannesburg 2050, South Africa}\\
{\tt munagi@maths.wits.ac.za}
\end{center}
\vskip 30pt
\centerline{\smallit Received: 8/2/06,
Revised: 1/18/07, Accepted: 4/24/07, Published: 5/14/07}
\vskip 30pt

\centerline{\bf Abstract}

\noindent We study a special partial fraction technique which is designed for rational
functions with poles on the unit circle, known as $q$-fractions. Even though
the theory of $q$-partial fractions has already been applied to the Rademacher 
Conjecture, no systematic computational development appeared.
In this paper we present two algorithms for the computation of $q$-partial 
fractions and highlight certain predictable coefficients which arise from the 
symmetry of the decompositions. We also examine the $q$-partial fraction content 
of reciprocals of the cyclotomic polynomials, and indicate how the technique can 
be used to facilitate the extraction of enumeration formulas from certain power 
series generating functions.

%\noindent Keywords: \ $q$-Fraction, partial fraction, algorithm, formula, coefficient,
%cyclotomic polynomial.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC 
JOURNAL OF COMBINATORIAL
NUMBER THEORY \smalltt 7 (2007), \#A25\hfill}

\thispagestyle{empty}
\baselineskip=15pt
\vskip30pt

\section{\normalsize Introduction} % 1

The methods to be discussed in this paper have their genesis in the work of
P.A. MacMahon who views his work as an extension of that of A. Cayley.
The motivation was the need to devise efficient closed forms for the numbers
$p(n,m)$ of the partitions of a positive integer $n$ into at most
$m$ parts for small $m$, the generating function of which is given by
\[
a(m,q) = \frac 1{(1-q)(1-q^2)
\cdots(1-q^m)}\,,\;   m\ge 0,\;   |q| < 1.
\]
In the present context the first complete examples of $q$-partial fraction
decompositions are the following expansions given by Cayley [8] and
MacMahon [12, p. 63], respectively:
\begin{eqnarray}
\sum_{n=0}^\infty p(n,2)q^n &= &a(2,q) = \frac{1/2}
{(1-q)^2} + \frac{1/2}{1-q^2}
\nonumber \\
\sum_{n=0}^\infty p(n,3) q^n &=& a(3,q)= \frac{1/4}{(1-q)^2} + \frac{1/6}{(1-q)^3}
+ \frac{1/4}{1-q^2}+ \frac{1/3}{1-q^3}.
\end{eqnarray}  %  (1.1)
MacMahon observed that (1.1) resulted in simpler formulas for the
functions $p(n, 2)$ and $p(n,3)$ than the following decompositions
recommended by Cayley:
\begin{eqnarray}
a(2,q) &=& \frac{1/4}{(1-q)} + \frac{1/2}{(1-q)^2} +
\frac{\frac 14(1-q)}{1-q^2}
\nonumber \\
a(3,q) &=& \frac{17/72}{1-q} + \frac{1/4}{(1-q)^2}
+ \frac{1/6}{(1-q)^3}
+ \frac{\frac 18(1-q)}{1-q^2}
+ \;\frac{\frac 19(q^2+q-2)}{1-q^3}.
\end{eqnarray}  %  (1.2) 
Indeed, by comparing the coefficients of $q^n$ on both sides of each
identity, after each summand on the right side is expanded as a power
series about
$q = 0$, the identities in (1.1) give
\begin{eqnarray}
p(n,2) &=& \frac 12 (n+1) + \frac 12 (1,0) cr2_n,
\nonumber \\
p(n,3) &=& \frac 1{12}(n+1)(n+5) + \frac 14(1,0) cr2_n + \frac 13(1,0,0)
cr3_n,
\end{eqnarray} %   (1.3)
while the identities in (1.2) lead to  
\begin{eqnarray}
p(n,2) &=& \frac 12 n+\frac 34 + \frac 14 (1,-1) pcr2_n,
\nonumber \\
p(n,3) &=& \frac 1{12}\left(n^2 + 6n + \frac{47}6 \right) + \frac 18 (1,-1) pcr 2_n
+ \frac 19 (2,-1,-1) pcr 3_n,
\end{eqnarray} %   (1.4)
where $(A_0, A_1,\dots, A_{M-1})crM_n$ is the so-called circulator (or
circulant) of period $M$ and represents the general coefficient in the power
series expansion about $q = 0$ of the periodic function
$(A_0+A_1q+\cdots+A_{M-1}q^{M-1})\big/(1-q^M)$. It is defined by
\[
(A_0, A_1,\dots, A_{M-1})crM_n = A_r \mbox{ if } n \equiv r ({\rm mod}\, M),\;
0 \le r \le M-1
\]
Cayley's formulas (1.4) contain the prime circulator $(A_0, A_1,\dots,
A_{M-1})pcrM_n$ which is a circulator subject to the additional conditions
$A_c + A_{c+s} + A_{c+2s} +\cdots+ A_{c+(b-1)s} = 0$,
$0 \le c \le s-1$, for every factorization of $M$ into two factors $M = sb$,
with $b > 1$.

The immediate advantage of the circulator notation is the elimination of
complex and irrational quantities from partition formulas [2, 10].

The $q$-partial fraction technique is specially designed for handling
rational functions whose poles consist of roots of unity, i.e., functions of
the type:
\[
A(q) = \frac{f(q)}{(1-q^{n_1})^{s_1}(1-q^{n_2})^{s_2}\cdots(1-q^{n_r})^{s_r}},
\quad   |q| < 1,
\]
where the $n_j$ and $s_j$ are positive integers, $1 \le j \le r,\; r > 0$, and 
degree($f$)$<\sum_{i=1}^{r}n_is_i$.

These are the $q$-fractions. Generally, the $q$-fractions consist of proper rational 
functions over the field $\mathbb{Q}$ of rational numbers in which the denominators 
can be factored into products of cyclotomic polynomials.

Most rational generating functions 
encountered in Combinatorics and $q$-Theory are sums and products of 
$q$-fractions [1, 3, 4, 7, 9].

Recall that the $n$th cyclotomic polynomial [16] for a positive integer $n$
is defined by
\begin{equation}
\Phi_n(q) = \prod_{d|n} (q^d -1)^{\mu(n/d)},
\end{equation} %  (1.5)
where $\mu(n)$ denotes the M\" obius function.

It is well-known that the prime circulators appearing in formulas belonging
to the class of those in (1.4) are uniquely determined following the
uniqueness of the Cayley-type partial fractions. The algorithm for the
latter essentially contains two simple steps:
 

\noindent{\bf Cayley:}\newline
\noindent Step 1: \ Obtain the decomposition of the $q$-fraction into
ordinary partial fractions over $\mathbb{Q}$, say
$\Sigma f_i(q)/\big(\Phi_i(q)\big)^k$;\\
Step 2: \ Translate each summand $f_i(q)/\big(\Phi_i(q)\big)^k$ into
an equivalent function with denominator of the form $(1-q^n)^s$,
by multiplying the numerator and denominator with the complementary
polynomial $(1-q^i)^s/\big(\Phi_i(q)\big)^k$.
 

On the other hand, Gupta, et al [10, p. xxv] observed that formulas in the
class of those in (1.3), which bear the simplest forms of the circulators,
could in general only be found by trial-and-error transformations of partial
fractions, when possible. Thus they suggested the problem of discovering a
systematic method for the prescribed partial fractions.

The theory of $q$-partial fractions, which has already appeared in [13],
provides a solution to this problem. The primary motivation for the theory
there is demonstrated in the application to the proof of a restricted case
of the Rademacher Conjecture [15, p. 302], [2]. While reviewing literature
afterwards we found that the technique also addressed the formula problem of
Gupta and his collaborators.

We show below (Section 4) that $q$-partial fractions also provide a natural
platform for the elimination of the circulators in favour of binomial
coefficients. It is then immediate to write down formulas such as
\begin{eqnarray}
p(n,4) &=& \left\langle \frac{25}{144} {n+2\choose 1} + \frac 18
{n+2\choose 2} + \frac 1{24} {n+3\choose 3} + \frac 18 {\frac n2 + 1\choose 1}
\right\rangle ;
\\ [.10in] % (1.6)
p(n,5) &=& \left\langle \frac{11}{64} {n+2\choose 1} + \frac {31}{288}
{n+2\choose 2} + \frac 1{24} {n+3\choose 3} + \frac 1{120} {n + 4\choose 4}
\right. \nonumber \\
&& \left. \;+\; \frac 1{16}{\frac n2 +1\choose 1}\right\rangle,
\end{eqnarray} % (1.7)
where $\langle N\rangle$ is the nearest integer to $N$ and
${N\choose j} = 0$ if $N$ is not an integer.

These formulas should be compared with other representations given in
[2, 6, 8, 10].

The aim of this paper is to present certain algorithms for the computation of
$q$-partial fractions together with some special features of the
decompositions in order to bring the technique to the knowledge of a
broader audience.

The rest of the paper is organized as follows. Section 2 recaps the
fundamental theory, and Section 3 is devoted to the description of two
algorithms for computing $q$-partial fractions. Section 4 deals with an
application of the technique to the extraction of general coefficients of
certain power series. In Section 5 we examine the $q$-partial fraction
content of reciprocals of the cyclotomic polynomials. Lastly, Section 6
profiles a few predictable coefficients in the decomposition of certain
$q$-fractions.

\vskip 30pt

\section{The Basic Representation Theorem} % 2
\setcounter{equation}{0}

The key departure of $q$-partial fractions from the Cayley-type partial
fractions is the stipulation that for a summand $v(q)/(1-q^n)^s$ to be
admissible, the degree of $v(q)$ must be less than Euler's totient function
$\phi(n)$, rather than the standard requirement that the degree of
$v(q)$ be less than $ns$.
 

\noindent{\bf Definition 2.1 }
{\it The $q$-fraction $v(q)/(1-q^n)^s$ is called {\bf basic} if it satisfies
degree$ (v) < \phi(n)$.}
 

\noindent{\bf Definition 2.2 }
{\it The $q$-partial fraction decomposition of the $q$-fraction
$A(q)$ is a representation of $A(q)$ as a finite sum of  basic $q$-fractions
with distinct denominators.}
 

\noindent{\bf Theorem 2.3 }
{\it For any specified $q$-fraction, the representation asserted in
Definition 2.2 exists, and is unique up to the order of the summands.}

\noindent
{\it Sketch of Proof.} We sketch a constructive proof of the theorem by
writing the general
$q$-fraction $A(q)$ as a sum of basic $q$-partial fractions.
(A non-constructive proof of Theorem 2.3 is given in [13].)
We work throughout in the rational field $\mathbb{Q}$.

First obtain the ordinary partial fraction decomposition
\begin{equation}
A(q) = \Sigma f_i(q)\big/\big(\Phi_i(q)\big)^{k_i}
\end{equation} %   (2.1)
where $\deg(f_i) < \phi(i)$ for each $i,\, k_i > 0$. 

Express each summand $f_i(q)\big/\big(\Phi_i(q)\big)^{k_i}$ as a sum of
basic $q$-fractions, by first multiplying the numerator and denominator by
the factor $v_i(q) = (1-q^i)^{k_i}\big/\big(\Phi_i(q)\big)^{k_i}$
to get
\[
\frac{f_i(q)}{\big(\Phi_i(q)\big)^{k_i}}  = \frac 1{v_i(q)}
\left( \frac{v_i(q)f_i(q)}{\big(\Phi_i(q)\big)^{k_i}} \right)
= \frac{v_i(q)f_i(q)}{(1-q^i)^{k_i}}.
\]
If degree$(v_if_i) < \phi(i)$ in the third expression, then we have a
single basic $q$-fraction. Otherwise decompose the parenthesized
function in the middle into ordinary partial fractions,
\begin{equation}
\frac{f_i(q)}{\big(\Phi_i(q)\big)^{k_i}}  =
\frac 1{v_i(q)} \left( \sum_{j=0}^{k_i} \frac{r_j(q)}{\big(\Phi_i(q)\big)
^{k_i-j}} \right) = \frac{r_0(q)}{(1-q^i)^{k_i}} + \sum_{j=1}^{k_i}
\frac{r_j(q)}{v_i(q)\big(\Phi_i(q)\big)^{k_i-j}}
\end{equation} %  (2.2)
where degree$(r_j) < \phi(i)$. 

But the denominator of the general summand on the right side of (2.2)
(except the first), need not be of the required form, and is therefore
handled again like $A(q)$, {\it ab initio}. This procedure is iteratively
continued until we arrive at a single basic $q$-fraction, preceded by  a sum
of basic $q$-fractions with denominators $(1- q^c)^x$ such that $1\le c\le i$
and $1\le x\le k_i$. The process will terminate since both $i$ and $k_i$
are finite.

Thus it follows by mathematical induction on the number of distinct factors
of $(1-q^i)^{k_i}$ of the form $(1-q^n)^s$ that
\begin{equation}
\frac{f_i(q)}{\big(\Phi_i(q)\big)^{k_i}} = \sum_{\scriptstyle j\atop
\scriptstyle d|i} \frac{r_j(q)}{(1-q^d)^c}, \mbox{ degree}(r_j) <
\phi(d), \; c > 0;
\end{equation} % 2.3
and, substituting (2.3) into (2.1), gives $A(q) =\sum_i \sum_{j,\,d|i}
r_j(q)\big/(1-q^d)^c$.

Thus both the existence and uniqueness of the $q$-partial fraction
decomposition follow from those of the corresponding ordinary partial
fraction decomposition. \hfill$\Box$ 

\vskip 30pt

\section{Algorithms for $q$-Partial Fractions} % 3
\setcounter{equation}{0}
We present two algorithms for computing $q$-partial fractions.
The first ({\bf Iteratn}) is directly prescribed by the proof of Theorem 2.3.
The second ({\bf UndetCoef}) is an adaptation of
the familiar method of undetermined coefficients for obtaining ordinary
partial fractions.
 

\noindent{\bf 3.1 Iteratn}\\
Decompose the proper rational function $f(q)/h(q)$ into $q$-partial fractions:\\
(I) If $f(q)/h(q)$ is not a $q$-fraction, then FAIL; (generally,
test if $h(q)$ factors into a product of cyclotomic polynomials).\\
(II) Obtain the ordinary partial fraction decomposition of
$f(q)/h(q)$;\\
(III) Transform each summand into a sum of basic $q$-fractions
as explained in the proof of Theorem 2.3;\\
(IV) Substitute into the original decomposition and combine like terms.
 

\noindent{\bf Example }
We derive the second member of (1.1).
The ordinary partial fraction decomposition is 
\begin{equation}
\frac 1{(1-q)(1-q^2)(1-q^3)} = \frac{17/72}{1-q} + \frac{1/4}{(q-1)^2}
+\frac{1/6}{(1-q)^3} + \frac{1/8}{q+1} + \frac{\frac 19(q+2)}{q^2+q+1}.
\end{equation} %  (3.1)
Transform each summand on the right into a sum of basic $q$-fractions
(the first three fractions are already basic):
\begin{eqnarray}
\frac{1/8}{q+1} &=& - \frac{\frac 18 (1-q)}{(1+q)(1-q)} = -\frac{\frac{1}8
(1-q)}{1-q^2} = \frac 1{1-q} \left( -\frac 18 +\frac{1/4}{1+q} \right)
\nonumber \\[.10in]
&=& \frac{-1/8}{1-q} + \frac{1/4}{1-q^2},
\end{eqnarray} % (3.2)
\begin{equation}
\frac{\frac 19 (q+2)}{q^2+q+1} = \frac 1{1-q} \left( - \frac 19 +
\frac{1/3}{1+q+q^2} \right) = \frac{-1/9}{1-q} + \frac{1/3}{1-q^3}.
\end{equation} % (3.3)
Substitute (3.2), (3.3) into (3.1) and add like terms to get the
required decomposition:
\[              
\frac 1{(1-q)(1-q^2)(1-q^3)} = \frac{1/4}{(1-q)^2} + \frac{1/6}{(1-q)^3}
+ \frac{1/4}{1-q^2} + \frac{1/3}{1-q^3}.
\]
 

\noindent{\bf 3.2 UndetCoef}\\ 
Decompose the proper rational function $f(q)/h(q)$ into $q$-partial fractions:\\
(I) If $f(q)/h(q)$ is not a $q$-fraction, then FAIL;\\
(II) Re-write $f(q)/h(q)$ as $F(q)/H(q)$, if necessary, so that
$H(q)$ is a product of factors of the form $(1-q^n)^s$ only;\\
(III) Obtain the $q$-factorization $G(q)$ of $H(q)$: the
$q$-factorization of $(1-q^{n_1})^{s_1}(1-q^{n_2})^{s_2}\cdots(1-q^{n_r})
^{s_r}$ is obtained by replacing each factor $1-q^{n_i}$ by $\prod(1-q^d)$,
where $d|n_i$;\\
(IV) State the theoretical decomposition of $f(q)/h(q)$, i.e.,
identify the given function with a sum of basic $q$-fractions with unknown
polynomial coefficients $f_i(q)$ such that each factor $(1-q^d)^k$ of $G(q)$
contributes the sum $f_1(q)/(1-q^d) +\cdots+ f_k(q)/(1-q^d)^k$,
where degree$(f_j) < \phi(d)$;\\
(V) Clear fractions and compare coefficients of powers of $q$ on
both sides to determine unknown coefficients;\\
(VI) Substitute into the theoretical decomposition in (IV).                                                                          
 

\noindent{\bf Example }
We decompose $R(q)$ into q-partial fractions using ${\bf UndetCoef}$. 
We have
\[R(q)=\frac{3q^8+5q^4+4q^2-2}{(1-q^4)(1-q^5)}.\]
The $q$-factorization of $(1-q^4)(1-q^5$) is $(1-q)^2(1-q^2)(1-q^4)(1-q^5)$.
Thus we set
\begin{eqnarray}
R(q)= \frac{A}{1-q} + \frac{B}{(1-q)^2}
+ \frac{C}{1-q^2} + \frac{D+Eq}{1-q^4} + \frac{F+Gq+Hq^2+Jq^3}{1-q^5}.
\end{eqnarray} %    (3.4)
(Note that each summand $v(q)/(1-q^d)^k$ on the right side satisfies
degree$(v)< \phi(d)$.)

It is a routine matter to clear fractions and compare coefficients of
powers of $q$ on both sides to obtain $A= -3,\; B = 1/2,\; C= 5/2,\;
D = 1,\; E = 1,\; F = -3,\; G = 1,\; H = 3,\; J = 1$.
Then substitute for the coefficients in (3.4) to obtain the required
decomposition:
\[
\frac{3q^8+5q^4+4q^2-2}{(1-q^4)(1-q^5)} = \frac{-3}{1-q} + \frac{1/2}
{(1-q)^2} + \frac{5/2}{1-q^2} + \frac{1+q}{1-q^4} +
\frac{-3+q+3q^2+q^3}{1-q^5}.
\]
 

\noindent{\it Remarks. }
{\bf Iteratn} is the algebraically more complicated of the two
algorithms since it subsumes a full classical partial fraction algorithm
over $\mathbb{Q}$. Clearly the version of the latter which employs the Euclidean
algorithm may not be adapted to $q$-partial fractions because the concept of
relative primeness is irrelevant to $q$-factorization.

The expansion of $A(q)$ into $q$-partial fractions contains at most
$s_1\tau(n_1)+\cdots+ s_r\tau(n_r$) summands, which is the same number as in
the ordinary partial fraction algorithm, where $\tau(N)$ is the number of
positive divisors of $N$. In particular the number of unknown coefficients to 
be computed by {\bf UndetCoef} for $a(q)$ is
$\sum_{1\le k\le m}\left\lfloor\frac mk\right\rfloor \phi(k) = (m+1)m/2$,
where $\lfloor N\rfloor$ is the floor function.

We deduce that the decomposition of $A(q)$ into $q$-partial fractions is at
worst as computationally costly as the ordinary partial fraction
decomposition of $A(q)$ over $\mathbb{Q}$, using the corresponding versions of
{\bf UndetCoef}.\\
The determination of the coefficients of basic $q$-fractions is much
simplified by one or more of the following nice situations:
\begin{itemize}
\item The $q$-factorization of the function $1-q^n$ is obviously easier
than the ordinary factorization over the integers.
\item Certain coefficients are predictable (see Section 6).
In particular the coefficient of the basic fraction $1/(1-q)$ is mostly 0
(Theorem 6.1).
\item The denominators of basic $q$-fractions have larger degrees
than those of ordinary partial fraction summands. So the clearing of
fractions reduces the magnitude of coefficients of powers of $q$, thus
simplifying the system of equations to be solved.
\end{itemize}


\section{Application to Enumeration Formulas} % 4
\setcounter{equation}{0}
\vspace{-10pt}
We give an illustration with a typical ordinary power series
generating function.\\
In this section and the next, the $q$-fraction $1/(1-q^n)^s$ is also
represented by $F_n^s$.

Let $T(n)$ denote the number of triangles with integer sides and perimeter
$n$. Hirschhorn [11] derives the formula
\begin{equation}
T(n) = \left\{ \begin{array}{ll}
\left\langle n^2/48\right\rangle, &\mbox{if $n$ is even}
\\[.10in]
\left\langle (n+3)^2/48\right\rangle, &\mbox{if $n$ is odd}
\end{array} \right.
\end{equation} %    (4.1)
where $\langle N\rangle$ is the nearest integer to $N$.

His method involves a combinatorial argument, followed by the application of
the well-known formula: $p(n, 3) = \left\langle (n+3)^2/12 \right\rangle$.

We give an alternative derivation of (4.1) from the generating function
for $T(n)$ ([5, p. 557]) via $q$-partial fractions. Consider the $q$-partial
fraction expansion
\begin{eqnarray}
\sum_{n=0}^\infty T(n)q^n &=& q^3F_2F_3F_4
\nonumber \\
& = & \frac 1{16} F_1^2 + \frac 1{24}
F_1^3 + \frac 1{16} F_2 - \frac 14 F_2^2 + \frac 13 F_3 - \frac 14 (1+q)F_4.
\end{eqnarray} %   (4.2)
If we expand each summand on the right as a power series about $q = 0$,
and then equate the coefficients of $q^n$ on both sides, we first obtain
the exact formula
\begin{eqnarray}
T(n) &=& \frac{n^2+6n+5}{48} - \frac 14 \left(\frac n2 + 1\right)(1,0)
cr2_n + \frac 1{16} (1,0)cr2_n 
\nonumber \\
&& \;+\; \frac 13 (1,0,0)cr3_n - \frac 14 (1,1,0,0)cr4_n.
\end{eqnarray} % (4.3)
Thus, if $n$ is even we have 
\begin{equation}
T(n) = \frac{n^2}{48} + \frac 5{48} - \frac 14 + \frac 1{16} +\frac 13
(1,0,0)cr3_n - \frac 14 (1,1,0,0)cr4_n.
\end{equation} %  (4.4)
But noticing that 
\[
\left| \frac 5{48} - \frac 14 + \frac 1{16} + \frac 13 (1,0,0)
cr3_n - \frac 14 (1,1,0)cr 4_n \right|
\le  \left| \frac 5{48} - \frac 14 + \frac 1{16} + \frac 13 \right|
< \frac 12,
\]
we can subtract the terms before the first inequality from the right side
of (4.4) to obtain the first part of (4.1).

If $n$ is odd then (4.3) becomes
\[
T(n) = \frac{N^2+6n+5}{48} + \frac 13(1,0,0)cr3_n - \frac 14(1,1,0,0)cr4_n,
\]
and since
\[
\left| \frac 13 (1,0,0)cr3_n -\frac 14 (1,1,0,0)cr4_n\right| -
\frac 1{12} \le \frac 13 - \frac 1{12} < \frac 12  ,
\]
we can subtract the terms before the first inequality
from the right side to obtain the second part of (4.1).  \hfill $\Box$
 

The simplicity of the coefficients of basic $q$-fractions makes it
convenient to read off formulas directly from expansions.

If the definition of the binomial coefficient is slightly adjusted to read,
for a nonnegative integer $K$,
\[
{N\choose K} = \left\{ \begin{array}{ll}
\frac{N!}{K!(N-K)!}, &\mbox{if $N$ is an integer and $N\ge K$},
\\
0, &\mbox{otherwise},
\end{array} \right.
\]
then the circulator may be replaced by a sum of binomial coefficients:
\[
(A_0,\dots, A_{M-1})crM_n = \sum_{k=0}^{M-1} A_k {\frac{n-k}M \choose 0}.
\]
It is now routine to read off the following formula directly from (4.2): 
\begin{equation}
T(n) = \left\langle \frac 1{16} {n+1\choose 1} + \frac 1{24} {n+2\choose 2}
-\frac 14 {\frac n2 +1\choose 1} \right\rangle.
\end{equation} %   (4.5)

Similarly, beginning with the decompositions,
\begin{eqnarray*}
F_1F_2F_3F_4 &=& \frac{25}{144} F_1^2 + \frac 18 F_1^3 + \frac 1{24} F_1^4
+ \frac 1{16}F_2 + \frac 18 F_2^2
+ \frac 19 (2+q) F_3 + \frac 14 F_4,
\\
F_1F_2F_3F_4F_5 &=& \frac{11}{64} F_1^2 + \frac{31}{288} F_1^3
+ \frac 1{24} F_1^4 + \frac 1{120}F_1^5 + \frac {11}{64}F_2
+ \frac1{16}F_2^2 
\\
&& +\; \frac 19 (2+q) F_3 + \frac 18(1+q) F_4 + \frac 15 F_5,
\end{eqnarray*}
one reads off the formulas (1.6) and (1.7) respectively. 
Obviously such formulas for $p(n, m)$ continue for larger $m$.

To specify the above formulas, we note, for instance, the following
version of (4.3) in which binomial coefficients correspond one-to-one with
the summands in (4.2):
\begin{eqnarray*}
T(n) &=& \frac 1{16} {n+1\choose 1} + \frac 1{24}{n+2\choose 2} +
\frac 1{16} {\frac n2\choose 0} - \frac 14 {\frac n2 + 1\choose 1}
+ \frac 13 {\frac n3\choose 0}
\\
&& -\; \frac 14 {\frac n4\choose 0}
- \frac 14 {\frac{n-1}4\choose 0}.
\end{eqnarray*}
Then (4.5) follows from the fact that
\[
\left| \frac 1{16} {\frac n2\choose 0} + \frac 13 {\frac n3\choose 0}
- \frac 14 {\frac n4\choose 0} - \frac 14 {\frac{n-1}4\choose 0} \right|
\le \left| \frac 1{16} + \frac 13 \right| < \frac 12.
\]

\vskip 30pt

\section{Reciprocals of Cyclotomic Polynomials} % 5
\setcounter{equation}{0}

In this section we find the $q$-partial fraction decomposition of the
reciprocal of the cyclotomic polynomial (1.5) for some values of $n$.

The factorization of $q^n - 1$ over the integers $q^n-1 =\prod_{d|n}
\Phi_d(q)$, gives the following recursion for the cyclotomic polynomials:
\[
\Phi_1(q)=q-1,\; \Phi_n(q) = \frac{q^n-1}{\prod_{d|n,\;d<n} \Phi_d(q)},
\; n\ge 2.
\]
This in turn gives
\begin{equation}
\frac 1{\Phi_n(q)} = \frac{-\prod_{d|n,\;d<n} \Phi_d(q)}{1-q^n},\;
n \ge 2.
\end{equation} % 5.1
Thus $\big(\Phi_n(q)\big)^{-1}$ is equivalent to a standard $q$-fraction with a single
denominator factor. It follows that the $q$-partial fraction decomposition
of $\big(\Phi_n(q))^{-1}$ has exactly one summand if $n < 2\phi(n)$.
Such $q$-partial fraction decompositions are called {\it trivial}
and may be obtained by applying {\bf Cayley} to $\big(\Phi_n(q)\big)^{-1}$.

Clearly the decomposition of $\big(\Phi_n(q)\big)^{-1}$ cannot be trivial if
$n$ is even. We observe that $\big(\Phi_n(q)\big)^{-1}$ has nontrivial decompositon
if and only if $\big(\Phi_m(q)\big)^{-1}$ does, where $m$ denotes the largest 
squarefree divisor of $n$.

The next theorem determines all trivial $q$-partial fraction decompositions
of $\big(\Phi_n(q)\big)^{-1}$ when $n$ is at most the product of powers of
four distinct primes. The straightforward derivation is omitted.
 

\noindent{\bf Theorem 5.1} 
{\it Let $N$ be an odd number with the factorization $N=p_1^{m_1} p_2^{m_2}
\cdots p_r^{m_r}$  into primes
$p_i,\, p_1 < p_2 <\cdots< p_r$, where $m_i\ge 1,\; r\ge 1$.
Then the $q$-partial fraction decomposition of $\big(\Phi_N(q)\big)^{-1}$
is trivial only in the following cases, for $1 \le r \le 4$:
\begin{itemize}
\item[(i) ] $r =1,\, 2$;
\item[(ii) ] $r = 3$, excluding all $N$ determined by
$(p_1, p_2, p_3) = (3,5,7),\, (3,5,11),\, (3,5,13)$;
\item[(iii)] $r = 4$, excluding all $N$ determined by members of the sets
\begin{itemize}
\item[(a)] $\{(3,5,7,p_4)\mid p_4>7\}$, $\{(3,5,11,p_4) \mid p_4>11\}$,
$\{(3,5,13,p_4) \mid p_4>13\}$;
\item[(b)] $\{(3,5,17,p_4) \mid 19 \le p_4 \le 251\}$, 
\item[(c)] $\{(3,5,19,p_4) \mid 23 \le p_4 \le 89\}$, 
\item[(d)] $\{(3,5,23,p_4) \mid 29 \le p_4 \le 47\}$, 
\item[(e)] $\{(3,5,29,31)\}$, 
\item[(f)] $\{(3,7,11,p_4) \mid 13 \le p_4 \le 23\}$, 
\item[(g)] $\{(3,7,13,17)\}$.     
\end{itemize}
\end{itemize} }
 

\noindent{\bf Theorem 5.2 }
{\it Let $k, m,n$ denote positive integers and let $p, p_1, p_2$ be odd primes,
$p_1 < p_2$. The following $q$-partial fraction decompositions are valid.
\begin{itemize}
\item[(i) ] $\big(\Phi_{2^k}(q)\big)^{-1} = -F_{2^{k-1}} + 2F_{2^k}$. 

\item[(ii) ] $\big(\Phi_{2^kp^m}(q)\big)^{-1} =
(-F_{2^{k-1}p^m} + 2F_{2^kp^m})\prod\limits_{i=0}^{m-1}\Phi_{2^kp^i}(q),\quad  p\ge 5$.
\item[(iii) ]  $\big(\Phi_{2^kp_1^mp_2^n}(q)\big)^{-1} = (-F_{2^{k-1}p_1^m p_2^n} + 2F_{2^kp_1^m p_2^n})
\left(\prod\limits_{i=0}^{n-1} \Phi_{2^kp_1^mp_2^i}(q)\right) \left(
\prod\limits_{s=0}^{m-1}\prod\limits_{j=0}^{n} \Phi_{2^kp_1^sp_2^j(q)}\right),\\  p_1\ge 5$.
\end{itemize} }
 

\noindent{\it Proof. } For (i),
we apply {\bf Iteratn} to get  
\[
\frac 1{\Phi_{2^k}(q)} = \frac{1-q^{2^{k-1}}}{1-q^{2^k}} = \frac 1
{1-q^{2^{k-1}}} \left( \frac{1-q^{2^{k-1}}}{1+q^{2^{k-1}}} \right) =
\frac 1{1-q^{2^{k-1}}} \left( -1 + \frac 2{1+q^{2^{k-1}}} \right).
\]
Hence
$\displaystyle
\frac 1{\Phi_{2^k}(q)} = \frac{-1}{1-q^{2^{k-1}}} + \frac 2{1-q^{2^k}}.
$

For (ii), write
$\displaystyle
\big( \Phi_{2^kp^m}(q)\big)^{-1} = \Phi_{2^k} (q^{p^{m-1}})
\big(\Phi_{2^k}(q^{p^m})\big)^{-1}.
$
Hence using part (i) we obtain
$\displaystyle
\big(\Phi_{2^kp^m}(q)\big)^{-1}  = \Phi_{2^k} (q^{p^{m-1}})
(-F_{2^{k-1}p^m} + 2F_{2^kp^m}),
$
which simplifies to the desired result.
For the first summand to be basic, we need degree$\big(\Phi_{2^k}
(q^{p^{m-1}})\big) < \phi(2^{k-1}p^m)$, or
$2^{k-1}p^{m-1} < 2^{k-2}(p-1)p^{m-1}$, or $p\ge 5$.

The proof of (iii) is analogous to that of part (ii).  \hfill$\Box$

 

\noindent{\it Remark}
The decomposition in Theorem 5.2 (ii) merely fails to hold in
general when $p = 3$. For instance, it holds for $\big(\Phi_{18}(q)\big)^{-1}$,
but fails for ($\Phi_{12}(q)\big)^{-1}$ $(= -F_2 + qF_3 - qF_6 + 2\Phi_4
(q)F_{12}$.) An analogous remark applies to Theorem 5.2 (iii).

\vskip 30pt

\section{Computation of Special Coefficients} % 6
\setcounter{equation}{0}

We highlight certain predictable coefficients in the $q$-partial fraction
decompositions of $A(q)$ and $a(q)$.

In the hope of extending the proof in [13], which is based on the
coefficient of $(1-q)^{-1}$, we compute the coefficient of $(1-q)^{-2}$
in the $q$-partial fraction decomposition of
$f(q)/(1-q^n)^s$, when $f(q)$ is a polynomial function of specified type.

We will use the notation $\{g(q)\}F(q)$ to denote the coefficient of the
basic $q$-fraction $g(q)$ in the $q$-partial fraction expansion of $F(q)$.

The following result is established in [13].
 

\noindent{\bf Theorem 6.1}{\it (Munagi [13]) } {\it
\[\{(1-q)^{-1}\}A(q) = \left\{ \begin{array}{ll}
(-1)^{s_1+s_2+\cdots+s_r-1}lc(f), &\mbox{if degree}(f)=\sum\limits_{i=1}^r
n_is_i-1
\\  [.10in]
0, &\mbox{if degree}(f) < \sum\limits_{i=1}^r n_is_i-1
\end{array} \right.\]
where $lc(f)$ is the leading coefficient of $f(q)$.
}
 

\noindent{\bf Theorem  6.2 } {\it 
If $r > 1$, or $r = 1$ and $n_1 = 1$, in $A(q)$, then with the notation
$s=\sum_{i=1}^r s_i$, we have
\[
\{(1-q)^{-s}\}A(q) = \frac{f(1)}{n_1^{s_1}n_2^{s_2}\cdots n_r^{s_r}} .
\] }

\noindent{\it Proof.} 
For $r > 0$ let the theoretical decomposition of $A(q)$ via {\bf UndetCoef} be given by
\begin{eqnarray*}
\frac{f(q)}{h(q)} &\equiv& \frac{C_{1,s,0}}{(1-q)^s} + \frac{C_{1,s-1,0}}
{(1-q)^{s_1}} +\cdots+ \frac{C_{1,1,0}}{(1-q)}
\\
&& + \;\sum_{d\ge 2} \sum_{j\ge 1}
\frac{C_{d,j,0}+C_{d,j,1}q+\cdots+ C_{d,j,\phi(d)-1}q^{\phi(d)-1}}
{(1-q^d)^j},
\end{eqnarray*}
where  $h(q)=(1-q^{n_1})^{s_1}(1-q^{n_2})^{s_2}\cdots (1-q^{n_r})^{s_r}$.
Multiply through with $h(q)$ to obtain
\begin{eqnarray*}
f(q) &=& C_{1,s,0}(1+q+\cdots+ q^{n_1-1})^{s_1} (1+q+\cdots+ q^{n_2-1})^{s_2}
\cdots (1+q+\cdots+q^{n_r-1})^{s_r}
\\
&& \quad\quad +\; \mbox{ (terms in } (1-q)).
\end{eqnarray*}
Setting $q = 1$ in the last expression proves the theorem. \hfill$\Box$
 

\noindent \textbf{Corollary 6.3} {\it
Some coefficient formulas in the $q$-partial fraction decomposition of
$a(m,q)$:
\begin{itemize}
\item[(1)] $\quad \left\{(1-q)^{-1}\right\}a(m,q)=1/m,\qquad \left\{(1-q)^{-m}\right\}a(m,q)=1/m!,\quad m\ge 1;$

\item[(2)] For each $m>2$ there is a sequence of coefficients 
$\left\{(1-q)^{-(m-k)}\right\}a(m,q),\, 1\le k\le \lfloor\frac{m-1}{k}\rfloor$, 
with the following initial terms.
\begin{itemize}
\item[(i)] \[ \{(1-q)^{-(m-1)}\}a(m,q) = \frac 1{4(m-2)!},\; m\ge 3,\]
\item[(ii)]
\[ \{(1-q)^{-(m-2)}\}a(m,q) = \frac{26-13m+9m^2}{288(m-2)!},\quad m \ge 5,\]
\item[(iii)]
\[ \{(1-q)^{-(m-3)}\}a(m,q) = \frac{56-42m+33m^2-10m^3+3m^4}{1152(m-2)!},\quad m \ge 7.\]
\end{itemize}
\end{itemize} }
 

\noindent {\it Proof.}
The proofs follow from Theorem 6.2, and Cayley's formula [4, p.81], given by
\begin{eqnarray}
\frac 1{(1-q)(1-q^2)\cdots(1-q^m)} &=& \sum \frac 1{1^{p_1}2^{p_2}\cdots
m^{p_m}p_1!p_2!\cdots p_m!}
\nonumber \\[.10in]
&& \times\; \frac 1{(1-q)^{p_1}(1-q^2)^{p_2}\cdots(1-q^m)^{p_m}}
\end{eqnarray} % (6.1)
where the summation runs over all partitions
$(1^{p_1},2^{p_2},3^{p_3},\dots,m^{p_m})$  of $m$, with $p_j \ge  0,\; 1 \le j \le m$.

First, evaluate the right side of (6.1) at the partitions
$(1^m)$ and $(m^1)$ to get, respectively,
\[ \frac{1/m!}{(1-q)^m} \mbox{ and } \frac{1/m}{1-q^m},\]
which, since they are basic q-fractions, prove part (1).

For part (2), each $\{(1-q)^{-m+k}\}a(m,q),\, k\ge 1$, receives contributions, via (6.1), 
from a finite set of partitons of $m$ of the form 
\begin{equation}(1^{-m+j}\pi(j,c)_{>1}),\quad j\ge 2,\, 1\le c\le k\end{equation} 
where $\pi(j,c)_{>1}$ is a  partition of $j$ into $c$ parts, each $>1$. 
For fixed $j$, it follows that $k=j-c$. Hence, the total number of 
contributing partitions is exactly $p(1)+p(2)+\cdots+p(k)$, where $p(N)$ is the 
number of all partitions of $N$.

A series of basic fractions generated by a partition can 
be obtained using (6.1) and Theorem 6.2.
For example, evaluating the right side of (6.1) at $(1^{m-2}2)$ gives 
$$Q(1^{m-2}2)=\frac{1}{2(m-2)!(1-q)^{m-2}(1-q^2)};$$ 
on applying Theorem 6.2 to $2(m-2)!Q(1^{m-2}2)$ and subtracting, we obtain 
$$Q(1^{m-2}2)=
\frac{1}{2(m-2)!}\left(\frac{1/2}{(1-q)^{m-1}}+\frac{1/2}{(1-q)^{m-3}(1-q^2)}\right).$$ 
Iterating this procedure, gives, after four steps,
$$Q(1^{m-2}2)=\frac{1}{2(m-2)!}\left(\frac{1/2}{(1-q)^{m-1}}+\frac{1/4}{(1-q)^{m-2}}
+\frac{1/8}{(1-q)^{m-3}}+\frac{1/16}{(1-q)^{m-4}}+\cdots\right)$$
Similarly,
$$Q(1^{m-3}3)=\frac{1}{3(m-3)!}\left(\frac{1/3}{(1-q)^{m-2}}+\frac{1/3}{(1-q)^{m-3}}
+\frac{2/9}{(1-q)^{m-4}}+\frac{1/9}{(1-q)^{m-5}}+\cdots\right)$$
$$Q(1^{m-4}2^2)=\frac{1}{8(m-4)!}\left(\frac{1/4}{(1-q)^{m-2}}+\frac{1/4}{(1-q)^{m-3}}
+\frac{3/16}{(1-q)^{m-4}}+\frac{1/8}{(1-q)^{m-5}}+\cdots\right)$$
$$Q(1^{m-4}4)=\frac{1}{4(m-4)!}\left(\frac{1/4}{(1-q)^{m-3}}+\frac{3/8}{(1-q)^{m-4}}
+\frac{5/16}{(1-q)^{m-5}}+\frac{5/32}{(1-q)^{m-2}}+\cdots\right)$$

Thus part $2(i)$ is given by the first term of $Q(1^{m-2}2)$, and $2(ii)$ by the 
sum of coefficients of terms from $Q(1^{m-2}2),Q(1^{m-3}3)$, and $Q(1^{m-4}2^2)$, that
is,   
$$\left\{(1-q)^{-(m-2)}\right\}a(m,q)=\frac{1/4}{2(m-2)!}+\frac{1/3}{3(m-3)!}+\frac{1/4}{8(m-4)!}
=\frac{26-13m+9m^2}{288(m-2)!},$$
and so forth.
Finally, note that (6.2) implies $m>j=k+c$, which implies that $m>2k$, for
fixed $m$.  So the degree of the polynomial numerator of each coefficient
is $(2k-1)-2+1=2(k-1)$. 
\hfill$\Box$
 

\noindent{\bf Theorem 6.4 } {\it
For $m>0$, let
\[
B(q) = \frac{b_0+b_1q+b_2q^2+\cdots+b_{(m+1)(n-1)}q^{(m+1)(n-1)}}
{(1-q^n)^{m+1}}.
\]
Then
\[
\{(1-q)^{-2}\}B(q) = \frac 1{m!n^m} \prod_{s=1}^m (sn+1) \sum_{u=1}^m
(-1)^{u+1}\; \frac{\prod\limits_{1\le k\le m-u} (kn-1)}
{\prod\limits_{u\le p\le m} (pn+1)} b_{un-1}.
\]}

To prove Theorem 6.4 we will need the following lemma.
 

\noindent{\bf Lemma 6.5 }
{\it Let $n, d, k$ be positive integers such that $d|n,\; d\ge 2$
and $1\le k\le N$; also let
\[
F(q) = \frac{C_0+C_1q+\cdots+ C_{\phi(d)-1}q^{\phi(d)-1}}
{(1-q^d)^k}.
\]
Then the polynomial $F(q)(1-q^n)^N$ has no terms in $q^{in-1},\,
1\le i\le N$.}
 

\noindent{\it Proof.} We have 
\begin{eqnarray*}
\lefteqn{F(q)(1-q^n)^N = \frac{C_0+C_1q+\cdots+ C_{\phi(d)-1}q^{\phi(d)-1}
(1-q^n)^N}{(1-q^d)^k} }
\\
&=& \left(C_0+C_1q+\cdots+ C_{\phi(d)-1}q^{\phi(d)-1}\right)
\left(1+q^d+q^{2d}+\cdots+ q^{n-d}\right)^k (1-q^n)^{N-k}.
\end{eqnarray*}
When expanded, the set $X$ of degrees of the terms on the right side is
given by
\[
X = \big\{ s+kdt+(N-k)u \mid 0\le s\le \phi(d)-1,\, 0\le t\le n/d-1,\,
u = 0,n\big\}.
\]
If $in-1$ belongs to $X$ then  $s = in-1$ (with $t = 0 = u$) for some 
$i,\,\Rightarrow 0 \le in -1 \le \phi(d)-1$. But this contradicts:
$d > 1$ and $d|n \Rightarrow in >\phi(d)$. \hfill$\Box$
 

\noindent{\it Proof of Theorem 6.4 }
Let $\{(1-q)^{-2}\}B(q)$ be represented by $C_{120}$. We employ
{\bf UndetCoef}.
The theoretical decomposition of $B(q)$ into $q$-partial fractions is given
by
\begin{equation}
B(q) = \sum_{r=0}^{(n-1)(m+1)} b_rq^r(1-q^n)^{-m-1}
= \sum_{k=2}^{m+1} \frac{C_{1,k,0}}{(1-q)^k} + \sum_{\scriptstyle d|n
\atop \scriptstyle d\ge 2} \sum_{k=1}^{m+1} \frac{P_{d,k}(q)}{(1-q^d)^k}
\end{equation} %   (6.3)
where
$
P_{d,k}(q) = C_{d,k,0} + C_{d,k,1}\, q+\cdots+ C_{d,k,\phi(d)-1}\,
q^{\phi(d)-1}.
$
Since the degree of the numerator of $B(q)$ exceeds the degree of the
denominator by $m+1\ge 2$ it follows, by Theorem 6.1, that
$\{(1-q)^{-1}\}B(q)$ vanishes in the right side of (6.3).

Multiplying both sides of (6.3) by $(1-q^n)^{m+1}$ gives          
\begin{equation}
\sum_{r=0}^{(n-1)(m+1)} b_rq^r = \sum_{k=2}^{m+1}
\frac{C_{1,k,0}(1-q^n)^{m+1}}{(1-q)^k} + T(q),                                                                
\end{equation} % 6.4
where
\[
T(q) = \sum_{\scriptstyle d|n \atop\scriptstyle d\ge 2} \sum_{k=1}^{m+1}
\frac{P_{d,k}(q)(1-q^n)^{m+1}}{(1-q^d)^k}.
\]
By Lemma 6.5, $T(q)$ has no terms in $q^{in-1},\; 1\le i\le m$, and the
powers
$q^{in-1}$ on both sides completely determine the coefficients $C_{1,k,0}$.
We note that                
\begin{eqnarray*}
\frac{(1-q^n)^{m+1}}{(1-q)^k} &=& \sum_{s=0}^{m+1} {m+1\choose s} (-q^n)^s
\sum_{c\ge 0} {c+k-1\choose c} q^c
\\
&=& \sum_{N\ge 0} q^N \sum_{s=0}^{m+1} (-1)^s {m+1\choose s}
{N+k-1-sn\choose k-1},
\end{eqnarray*}
where $c+sn = N$. Hence (6.4) becomes
\begin{eqnarray*}
\sum_{r=0}^{(n-1)(m+1)} b_rq^ r
&=& \sum_{k=2}^{m+1} C_{1,k,0} \sum_{N\ge 0}q^N \sum_{s=0}
^{m+1}(-1)^s {m+1\choose s}{N+k-1-sn\choose k-1} + T(q)
\\
&=& \sum_{k=2}^{m+1} C_{1,k,0} \left\{ \sum_{r=0}^{m+1}
(-1)^r {m+1\choose s}{in+k-2-sn\choose k-1} q^{in-1}
\right.
\\
&& \left. \phantom{\sum_{r^k}} +\; \mbox{(terms in } q^v,\, v\ne in-1,\,
1\le i\le m) \right\} + T(q).
\end{eqnarray*}
Observe that $s$ can be restricted to the range $1\le s\le i-1$ since
${in+k-2-sn\choose k-1}\ge 0 \Leftrightarrow s \le i-1$.
\begin{eqnarray*}
\sum_{r=0}^{(n-1)(m+1)} b_rq^r
&=& \sum_{k=2}^{m+1} C_{1,k,0} \left\{ \sum_{s=0}^{i-1}
(-1)^s{m+1\choose s}{(i-s)n+k-2\choose k-1} q^{in-1}
\right.
\\
&& \left. \phantom{\sum_{r^k}} +\; \mbox{(terms in } q^v,\, v\ne in-1,\,
1\le i\le m) \right\} + T(q).
\end{eqnarray*}
To determine the $C_{1,k,0}$, equate the coefficients of the $q^{in-1}$
on both sides to obtain the system of $m$ equations
\[
\begin{array}{l}
\sum\limits_{k=2}^{m+1} C_{1,k,0} {n+k-2\choose k-1} = b_{n-1}
\\[.10in]
\sum\limits_{k=2}^{m+1} C_{1,k,0} \sum_{s=0}^{1} (-1)^s
{m+1\choose s}{(2-s)n+k-2\choose k-1}
= b_{2n-1}
\\
\hskip 100pt\vdots
\\
\sum\limits_{k=2}^{m+1} C_{1,k,0} \sum\limits_{s=0}^{m-1} (-1)^s {m+1\choose s}
{(m-s)n+k-2\choose k-1} = b_{nm-1}
\end{array} \; .
\]
That is, $A\bar c = \bar b$, where ($j\equiv k-1$) 
\[(A)_{ij} = \sum_{s=0}^{i-1} (-1)^s {m+1\choose s}{(i-s)n+j-1\choose j},
\; \bar{c} = \left[ \begin{array}{c} C_{1,2,0}\\ \vdots\\
C_{1,m+1,0} \end{array}\right],\;
\bar{b} = \left[ \begin{array}{c} b_{n-1}\\ \vdots \\ b_{mn-1}
\end{array} \right].\]

Let the matrix obtained by replacing the first column of $A$ with
$\bar b$ be $A_1$.
Then, according to Cramer's Rule,
\begin{equation}
\{(1-q)^{-2}\}B(q) = C_{1,2,0}= \frac{\det (A_1)}{\det(A)}.
\end{equation} %    (6.5)
Let $\Lambda_1^u$ denote the matrix obtained from $A$ after deleting the
$u$th row and first column. Then
\[
\det(A_1) = \sum_{u=1}^m (-1)^{u+1} \det (\Lambda_1^u) b_{un-1}.
\]
Thus (6.5) becomes
\begin{equation}
\{(1-q)^{-2}\}B(q) = \frac 1{\det(A)} \sum_{u=1}^m (-1)^{u+1}
\det(\Lambda_1^u)b_{un-1}.
\end{equation} %     (6.6)
 

\noindent{\tt Claim.}\ $\det(A) = n^{m(m+1)/2}$  

\noindent We use elementary row operations to evaluate $\det(A)$.
Since
\[
(A)_{ij} = {in+j-1\choose j} + \sum_{s=1}^{i-2} (-1)^s {m+1\choose s}
{(i-s)n+j-1\choose j} + {n+j-1\choose j}  ,
\]
it follows that $\det(A) = \det(C)$, where $C$ is the matrix defined by
\[
(C)_{ij}= {in+j-1\choose j},\quad 1\le i\le m,\; 1\le j\le m,
\]
and is obtained on applying the following operations successively to the
rows of $A$:
\begin{equation}
R_i \mapsto  R_i - \sum_{k=1}^{i-1}(-1)^k {m+1\choose k} R_{i-k},
\quad  2\le i\le j,
\end{equation} % (6.7)
where $R_i$ denotes the ith row and the other symbols have their usual meanings.
The result then follows from the fact that $\det(C)$ is a special
``combinatorial determinant'' [17] corresponding to the case $f = 1+x$
(see [17, p. 3]).
But our row operations approach yields
\[
\det(A) = \det(C) = \frac{nn^2\cdots n^m}{1!2!\cdots(m-1)!} V(1,2,\dots,m)
\]
where $V(x_1,x_2,\dots,x_N)=\prod_{1\le j\le i\le N}(x_i-x_j)$ is the
$N$th order Vandermonde determinant.
Since $V(1,2,\dots,m) = 1!2!\cdots(m-1)!$, we obtain $\det(A) = n^{m(m+1)/2}$
as claimed.

Substituting for $\det(A)$ in (6.6) gives
\begin{equation}
\{(1-q)^{-2}\}B(q) = \frac 1{n^{m(m+1)/2}} \sum_{u=1}^m (-1)^{u+1}
\det(\Lambda_1^u)b_{un-1}.
\end{equation} %   (6.8)
It remains to evaluate $\det(\Lambda_1^u)$. 
We prove the following Lemma, from which Theorem 6.4 clearly follows.
 \hfill $\Box$

\noindent{\bf Lemma 6.6 } {\it
\[
\det(\Lambda_1^u) = \frac{n^{m(m-1)/2}}{m!}\;
\frac{\prod\limits_{1\le s\le m} (sn+1)\prod\limits_{1\le k\le m-u}(kn-1)}
{\prod\limits_{u\le p\le m} (pn+1)}.
\]}
 

\noindent{\it Proof. }
We apply the following modified form of the row operations (6.7) successively
to the rows of $\Lambda_1^u$, in order:
\begin{eqnarray}
R_i &\mapsto& R_i -\sum_{k=1}^s (-1)^{i-k} {m+1\choose i-k} R_k,
\quad 2\le i\le j-1,\; s = \min(u-1, i-1);    %   (6.9)
\\
R_i &\mapsto&  R_i - \sum_{k=u}^{i-1} (-1)^{i-k} {m+1\choose i-k} R_k,
\quad u+1 \le i \le j-1. %          (6.10)
\end{eqnarray}
The resulting $(m-1)$-square matrix $Y_1^u$ is given by
\begin{equation}
(Y_1^u)_{ij} = \left\{ \begin{array}{ll}
{in+j-1\choose j}, & 1\le i<u
\\[.10in]
{(u+t)n+j-1\choose j} -E(m,t) {un+j-1\choose j}, & 1\le t\le m-u
\end{array} \right. .
\end{equation} %  (6.11)
We claim that
\begin{equation}
E(m,t) = {m+t\choose t}.
\end{equation} %   (6.12)
The proof is by induction on the number $t$ of rows $u,\, u+1,\dots$
in which every entry has exactly two summands following applications of
the row operations (6.9) to all the rows,  and (6.10) down to the
$(u+t)$th row. For brevity denote $\quad \Psi(i) = {in+j-1\choose j}$.

By the definition of the matrix A the effect of the row operations (6.9)
down to the $u$th row is the general $u$th-row entry
$\Psi(u+1) - E(m,1)\Psi(u)$. Hence (6.12) holds for $t = 1$. \\ 
Assume that (6.12) is true for all positive integers up to $t-1$, i.e., 
the rows from number $u$ through $u+t-2$ all have the required form.
Then application of the row operations (6.10) to the
$(u+t-1)^{\mathrm{st}}$ row gives
\begin{eqnarray*}
R_{u+t-1} &\mapsto&  R_{u+t-1} - \sum_{k=u}^{u+t-2} (-1)^{u+t-1-k}
{m+1\choose u+t-1-k} R_k
\\
&=& \sum_{s=0}^t (-1)^s {m+1\choose s} \Psi(u+t-s)
\\
&& -\; \sum_{k=u}^{u+t-2} (-1)^{u+t-1-k} {m+1\choose u+t-1-k}
\big(\Psi(k+1)-E(m,k-u+1)\Psi(u)\big)
\\
&=& \Psi(u+t) + (-1)^t {m+1\choose t} \Psi(u)
+\; \sum_{s=1}^{t-1} (-1)^s {m+1\choose s} E(m,t-s)\Psi(u)
\\
&=& \Psi(u+t) +  \sum_{s=1}^{t} (-1)^s {m+1\choose s} E(m,t-s)\Psi(u).
\end{eqnarray*}
The last step in the proof is to establish the Vandermonde-convolution-type
identity
\begin{equation}
\sum_{k=1}^t (-1)^k {m+1\choose k}{m+t-k\choose t-k} = -
{m+t\choose t}.
\end{equation} %   (6.13)
Let $S_t$ denote the left side:
\[
S_t = \sum_{k=0}^{t-1} (-1)^{k+1} {m+1\choose k+1} {m+t-k-1\choose m}
= \sum_k a_k,
\]
where $a_0=-(m+1){m+t-1\choose m}$.
Then we obtain
\[
\frac{a_{k+1}}{a_k} = \frac{(k-m)(k-t+1)}{(k+2)(k-m-t+1)}\;
\frac{(k+1)}{(k+1)},
\]
after routine simplification.
Thus $S_t$ can be written in hypergeometric notation as follows
\[
S_t=a_0\,{}_3F_2  \left( \begin{array}{cc} -m,\,-t+1,\, 1\\ & ,1\\
2,\, -m-t+1 \end{array}\right).
\]
By setting $a=-m,\,b=1,\, n=t-1,\,c=2$ and noting that $-m-t+1=1+a+b-c-n$,
we see that the ${}_3F_2$-term satisfies
the Pfaff-Saalschutz Theorem [5, p. 69], namely
\[
{}_3F_2 \left(\begin{array}{cc} 1,\, -n\, ,b\\ & ,1\\
c,\, 1+a+b-c-n\end{array} \right)
= \frac{(c-a)_n(c-b)_n}{(c)_n(c-a-b)_n},
\]
where the Pochhammer symbol $(x)_k$ is defined by
$(x)_k = x(x+1)\cdots(x+k-1),\; k\ge 1,\; (x)_0 = 1$.
Hence
\[
S_t = a_0\cdot \frac{(2+m)_{t-1}(1)_{t-1}}{(2)_{t-1}(1+m)_{t-1}}
= -(m+1) {m+t-1\choose m} \cdot \frac{(2+m)_{t-1}(1)_{t-1}}
{(2)_{t-1}(1+m)_{t-1}}
\]
which gives, after simplification, $S_t = -{m+t\choose t} = -E(m,t)$. 
Hence the claim follows.
\hfill $\Box$
 

\noindent{\it Remark}
Call (6.13) an identity of order 0. If we concentrate on retaining exactly
three summands per entry from the $(u+1)$st row downward, the coefficients
of $\Psi(u)$ will lead, as above, to the analogous identity of order 1:
\[
\sum_{k=1}^t (-1)^{k+1} {m+1\choose k+1}{m+t-k\choose t-k} = t
{m+t\choose t+1}.
\]
By a similar argument it can be shown that the identity of order 2 is   
\[
\sum_{k=1}^t (-1)^{k+1} {m+t\choose k+2}{m+t-k\choose t-k} =
{t+1\choose 2}{m+t\choose t+2}.
\]
The general form of such identities of fixed order $d,\, 0\le d\le m-t+1$,
with $1\le t\le m$, is given by
\[
\sum_{k=1}^t (-1)^{k+1} {m+1\choose k+d}{m+t-k\choose t-k} =
{t+d-1\choose d}{m+t\choose t+d}.
\]
 

\noindent{\it Remark}
We recall an important property of determinants [14, p. 2].
Let $D,\, U,\, V$ be determinants of order $n$ with $ij$-entries given by
$(D)_{ij},\, (U)_{ij},\, (V)_{ij}$, such that for a fixed index
$k,\, 1\le k\le n$, we have
\[
(D)_{ik} = \alpha x_{ik} +\beta y_{ik},\; (U)_{ik} = \alpha x_{ik},\;
(V)_{ik} = \beta y_{ik}, \mbox{ and }
(D)_{ij} = (U)_{ij} = (V)_{ij}, \mbox{if}\, j \ne k.
\]
Then $D = \alpha U+\beta V$, where $\alpha$ and $\beta$ are real numbers.    

Since $\det(\Lambda_1^u) = \det(Y_1^u)$, we can use the above remark 
repeatedly to write $\det(\Lambda_1^u)$ as a linear combination of the
determinants
$\det(C_1^v)$, where each $C_1^v$ is the matrix obtained from $C$,
after deleting the $v$th row and first column.
Then it follows from (6.11) that
\begin{eqnarray}
\det(\Lambda_1^u) = \sum_{t=0}^{m-u} (-1)^t E(m,t)\det (C_1^{u+t})
= \sum_{t=0}^{m+t} (-1)^t {m+t\choose t} \det(C_1^{u+t}).
\end{eqnarray} %   (6.14)
Each determinant $\det(C_1^v)$ can be evaluated by reduction
to a Vandermonde determinant.
\[
\det(C_1^v) = \frac{n^{(m-1)(m-2)/2}}{2!3!\cdots m!} \prod_{1\le s\le m,\,s\ne v}
sn(sn+1) V(1,2,\dots,v-1,v+1,\dots,m).
\]
Now use the relation
$\displaystyle
V(1,2,\dots,v-1,v+1,\dots,m) = \frac{1!2!\cdots(m-1)!}{(v-1)!(m-v)!},
$ to obtain
\begin{equation}
\det(C_1^v) = \frac{n^{m(m-1)/2}}{m!} {m\choose v} \prod_{1\le s\le
m,\,s\ne v} (sn+1).
\end{equation} %        (6.15)
Substituting for (6.15) in (6.14) gives
\begin{equation}
\det(\Lambda_1^v) = \frac{n^{m(m-1)/2}}{m!}  \prod_{s=1}^m (sn+1)
\sum_{t=0}^{m-u} (-1)^t {m+t\choose t} \frac{ {m\choose u+t}}
{\big((u+t)n+1\big)}.
\end{equation} %     (6.16)
Lastly we eliminate the summation symbol by transformation into
hypergeometric notation. As before we have
\[
\sum_{t=0}^{m-u} (-1)^t {m+t\choose t} \frac{ {m\choose u+t}}
{\big((u+t)n+1\big)} = \frac{{m\choose u}}{un+1} {}_3F_2
\left( \begin{array}{cc}
m+1,\, -m+u,\, \frac 1n (nu+1) \\
& ,1\\
u+1,\, \frac 1n(nu+n+1) \end{array} \right).
\]
The Pfaff-Saalschultz Theorem applies again and we obtain, after routine
simplifications,
\begin{eqnarray*}
\lefteqn{ \sum_{t=0}^{m-u} (-1)^t {m+t\choose t} \frac{{m\choose u+t}}
{\big((u+t)n+1\big)} }
\\
&=& \frac{{m\choose u}}{un+1} \cdot \frac{(-m+u)_{m-u}\left( \frac{n-1}n
\right)_{m-u}}{(u+1)_{m-u} \left( \frac{-n m-1}{b}\right)_{m-u}}
= \frac{\prod\limits_{k=1}^{m-u} (kn-1)}{\prod\limits_{p=u}^m (pn+1)}.
\end{eqnarray*}
Substituting the last result into (6.16) gives the Lemma. \hfill$\Box$
 

\noindent{\bf Acknowledgement }  The author is grateful to his advisor,
George E. Andrews, who is responsible for inventing $q$-partial fractions.

\vskip 30pt

\begin{thebibliography}{99} \footnotesize
\bibitem{1} G.E. Andrews.  Applications of basic hypergeometric functions.
{\it SIAM Review},  16:441--484, 1974.
\bibitem{2} G.E. Andrews. Partitions: At the interface of $q$-Series and Modular Forms.
{\it Ramanujan Journal} 7 (1, 2, 3):385--400, 2003.
\bibitem{3} G.E. Andrews. $q$-Series: Their Development and Application in Analysis, Number 
          Theory, Combinatorics, Physics, and Computer Algebra.
          Volume 66 of CBMS
          Regional Conference Series in Mathematics, Published for the Conference
          Board of the Mathematical Sciences, Washington, D. C., 1986.
\bibitem{4} G.E. Andrews. The Theory of Partitions. Addison-Wesley, Reading, 1976;
 reprinted by Cambridge University Press, Cambridge in 1984, 1998.  

\bibitem{5} G.E. Andrews, R. Askey and R. Roy. Special Functions. Cambridge University
          Press 1999.
\bibitem{6} J. Arkin. Researches on Partitions.
{\it Duke Math. J.}, 38:403--409, 1970. 
\bibitem{7} A. Bjorner and R.P. Stanley. A Combinatorial Miscellany.
{\it L'Enseignement Math.} (to appear).
\bibitem{8} A. Cayley. Researches in the Partition of Numbers.
{\it Collected Math. Papers}, 2:2 35--249, 506--512, 1898.
\bibitem{9} G. Gasper and M. Rahman. Basic Hypergeometric Series.
Cambridge University
          Press 1990.
\bibitem{10}  H. Gupter, M.M. Gwyther and J.C.P. Miller. Tables of Partitions.
Royal Soc. Math. Tables, Vol. 4, Cambridge Univ Press, Cambridge, 1958.
\bibitem{11}  M.D. Hirschhorn, Triangles with Integer Sides Revisited.
Math. Mag., 73:53-56, 2000.
\bibitem{12}  P.A. MacMahon. Combinatory Analysis. Vol. 2, Cambridge Univ. Press, 
         Cambridge 1916; reprinted by Chelsea, New York in 1960.
\bibitem{13}  A.O. Munagi. The Rademacher Conjecture and $q$-Partial Fractions.
{\it Ramanujan Journal} (to appear).
\bibitem{14}  V.V. Prasolov. Problems and Theorems in Linear Algebra.
{\it Translations of
          Mathematical Monographs}, Vol. 134, AMS, Providence, 1994.     
\bibitem{15}  H. Rademacher. Topics in Analytic Number Theory. Springer, New York, 1973.
\bibitem{16}  E.W. Weisstein. ``Cyclotomic Polynomial''
From MathWorld--A Wolfram
         Web Resource. <http://mathworld.wolfram.com/ CyclotomicPolynomial.html>.
\bibitem{17} H. Wilf. A Combinatorial Determinant. Eprint arXiv:math.CO/9809120, 09/1998.
\end{thebibliography}

\end{document}