\documentclass[11pt]{article}
\textwidth=6.25in
\textheight=9.0in
\topmargin=10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
\usepackage{amssymb,latexsym}

\begin{document}

\begin{center}
{\bf ON PARTITIONS AND CYCLOTOMIC POLYNOMIALS}
\vskip 20pt
{\bf Neville Robbins}\\
{\smallit Mathematics Department, San Francisco State University, San
Francisco, CA 94132}\\
{\tt robbins@math.sfsu.edu}\\
\end{center}
\vskip 30pt
\centerline{\smallit Received: November 12, 1999,
Revised: May 22, 2000, Accepted: June 2, 2000, Published: June 6, 2000 }
\vskip 30pt

\centerline{\bf Abstract}

\noindent
Let $m$ denote a squarefree number.  Let $f_m(n)$ denote the number
of partitions of $n$ into parts that are relatively prime to $m$.
Let $\Phi_m(z)$ denote the $m^{th}$ cyclotomic polynomial.  We
obtain a generating function for $f_m(n)$ that involves factors
$\Phi_m(z^n)$.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF
COMBINATORIAL NUMBER THEORY \smalltt 0 (2000), \#A06\hfill}

\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt

\section*{\normalsize 1. Introduction}

If $z$ is a complex variable, let $\Phi_m(z)$ denote the $m$th
cyclotomic polynomial, that is

\[ \Phi_m(z) = \prod_{d|m}(z^d-1)^{\mu(m/d)}  \]

\noindent
where $\mu(n)$ denotes the M\"obius function. If $p$ is prime,
let $b_p(n)$ denote the number of \emph{p-regular}
partitions of $n$, that is, the number of partitions of $n$ such that
no part occurs $p$ or more times.  It is well-known that $b_p(n)$
also counts the number of partitions of $n$ into parts, $k$, such
that $(k,p) = 1$.  (See [1],[2], and [3].)  Furthermore, $b_p(n)$ has a
generating function given by

\begin{equation}
\sum_{n=0}^{\infty}b_p(n)z^{n} =
\prod_{n=1}^{\infty}\frac{1-z^{pn}}{1-z^{n}} = \prod_{n=1}^{\infty}
\Phi_p(z^n)
\end{equation}

\noindent
where  $|z|<1$ .  In particular, if $q(n)$
denotes the number of partitions of $n$ into distinct parts (or odd
parts), so that $q(n) = b_2(n)$, then

\begin{equation}
\sum_{n=0}^{\infty}q(n)z^{n} = \sum_{n=0}^{\infty}b_2(n)z^{n} =
\prod_{n=1}^{\infty}(1+z^{n}) = \prod_{n=1}^{\infty}\Phi_2(z^{n}).
\end{equation}

In this note, we generalize (1) as follows.  Let $m$ be the product
of $r$ distinct primes.  Let $f_m(n)$ denote the number of partitions
of $n$ into parts, $k$, such that $(k,m) = 1$.  That is, $f_m(n)$
denotes the number of partitions of $n$ into parts that are not
divisible by any of the $r$ distinct primes.  We obtain a
generating function for $f_m(n)$ as an infinite product of factors
$\Phi_m(z^{n})$ or $1/\Phi_m(z^{n})$, accordingly as $r$ is odd or even,
respectively.
\vskip 25pt
\section*{\normalsize 2. Preliminaries}

\noindent
\textbf{Theorem 0}
{\it
\hspace{.05in} If $H\subset N$, 
let  $p_H(n)$ denote the number of partitions of $n$
into parts belonging to $H$;
let $q_H(n)$ denote the number of
partitions of $n$ into distinct parts belonging to $H$;
let $q_H^{E}(n)$ denote the number of partitions of $n$ into evenly many
distinct parts from $H$; 
let $q_H^{O}(n)$ denote the number of
partitions of $n$ into oddly many distinct parts from $H$. 
Further, let
$q_H^{*}(n) = q_H^{E}(n) - q_H^{O}(n)$ and define $p_H(0) = q_H(0) =
q_H^{E}(0) = q_H^{*}(0) = 1$. 
Let $z$ be a complex variable such
that $|z|<1$.  Then}

\begin{equation}
\sum_{n=0}^{\infty}p_H(n)z^{n} = \prod_{n\in H}(1-z^n)^{-1}
\end{equation}

\begin{equation}
\sum_{n=0}^{\infty}q_H(n)z^{n} = \prod_{n\in H}(1+z^{n})
\end{equation}

\begin{equation}
\sum_{n=0}^{\infty}q_H^{*}(n)z^{n} = \prod_{n\in H}(1-z^{n}).
\end{equation}

\noindent
{\it Remarks:}
Equation (3) is Theorem 1.1, (1.2.4) in [1]; (4) follows from the same
theorem; (5) is proven for the case $H = N$ in [1].  The proof extends
easily to the case: $H\subset N$.
\vskip 25pt
\section*{\normalsize 3. The Main Results}

\noindent
\textbf{Theorem 1}
{\it 
\hspace{.05in}
Let $m = \prod_{i=1}^{r}p_i$ , where $r\geq 1$ and the $p_i$ are
distinct primes.  Let $f_{m}(n)$ be the number of partitions of $n$ into
parts, $k$, such that $(k,m) = 1$.  Let $\Phi_m(z)$ denote the $m$th
cyclotomic polynomial, where $z$ is a complex variable, with $|z|<1$.
Then}

\begin{equation}
\sum_{n=0}^{\infty}f_m(n)z^{n} =
\prod_{n=1}^{\infty}(\Phi_m(z^{n}))^{(-1)^{r-1}}.
\end{equation}

\noindent
{\it Proof.} If $r=1$, then $f_m(n) = f_p(n) = b_p(n)$ = the number of
p-regular
partitions of $n$ , so (by (1))

\[
\sum_{n=0}^{\infty}f_m(n)z^{n} = \sum_{n=0}^{\infty}b_p(n)z^{n} =
\prod_{n=1}^{\infty}\frac{1-z^{pn}}{1-z^{n}} =
\prod_{n=1}^{\infty}\Phi_p(z^{n}).
\]

\noindent
Now suppose that $m$ has $r$ distinct prime factors, and $p$ is a
prime such that $p\not|m$.  Then $pm$ has $r+1$ distinct prime
factors.  By induction hypothesis,

\[
\sum_{n=0}^{\infty}f_m(n)z^{n} =
\prod_{n=1}^{\infty}(\Phi_m(z^{n}))^{(-1)^{r-1}}.
\]

\noindent
Now

$$
\begin{array}{lll}
\sum_{n=0}^{\infty}f_{pm}(n)z^{n}
&= \prod_{(p,n)=1}(\Phi_m(z^{n}))^{(-1)^{r-1}}
&=\prod_{n=1}^{\infty}\left(\frac{\Phi_m(z^{n})}{\Phi_m(z^{pn})}\right)
^{(-1)^{r-1}}
\\ \\
&= \prod_{n=1}^{\infty}(1/\Phi_{pm}(z^{n}))^{(-1)^{r-1}}
&=\prod_{n=1}^{\infty}(\Phi_{pm}(z^{n}))^{(-1)^{r}},
\end{array}
$$

\noindent
so we are done.

\noindent
{\it Remarks:}
Let $\omega(d)$ denote the number of distinct prime factors of $d$.
Then (6) could be restated as:

\begin{equation}
\sum_{n=0}^{\infty}f_m(n)z^{n} =
\prod_{n=1}^{\infty}\prod_{d|m}(1-z^{dn})^{(-1)^{1+\omega(d)}}.
\end{equation}

\vspace{.1in}
\noindent
Since $d$ is squarefree by hypothesis, we have $(-1)^{\omega(d)} =
\mu(d)$.  Thus (7) becomes:

\begin{equation}
\sum_{n=0}^{\infty}f_m(n)z^n =
\prod_{n=1}^{\infty}\prod_{d|m}(1-z^{dn})^{-\mu(d)}.
\end{equation}

\vspace{.1 in}
\noindent
A shorter, alternate proof is based on the inclusion-exclusion
principle, namely


%\[ \sum_{n=0}^{\infty}f_m(n)z^n =  \]
\begin{equation}
\sum_{n=0}^{\infty}f_m(n)z^n =  
\prod_{n=1}^{\infty}(1-z^n)^{-1}\prod_{p|m}(1-z^{pn})\prod_{p_1p_2|m}(1-z^{p_1p_
2n})^{-1}
\prod_{p_1p_2p_3|m}(1-z^{p_1p_2p_3n})\cdots
\end{equation}

\[ = \prod_{n=1}^{\infty}\prod_{d|m}(1-z^{dn})^{-\mu(d)}. \]

\noindent
(In the products above, the $p_i$ are distinct prime divisors of $m$.)

\noindent
Furthermore, $f_m(n)$ may be computed recursively by the repeated use
of
Theorem 2 below, whose elementary proof is omitted.

\noindent
\textbf{Theorem 2}
{\it 
Let $m$, $r$, $f_m(n)$, $z$ be as in the hypothesis of Theorem 1.
Let $p$ be a prime such that $p \nmid m$.  Then}

\[
f_{pm}(n) + \sum_{j=1}^{[n/p]}f_{pm}(n-pj)f_m(j) = f_m(n).
\]

\noindent
For example, suppose we wish to compute the number of partitions of
$n$ into parts that are not divisible by 2, 3, or 5.  That is, we wish
to compute $f_{30}(n)$.  According to Theorem 1, we have:

\[ \sum_{n=0}^{\infty}f_{30}(n)z^{n} =
\prod_{n=1}^{\infty}\Phi_{30}(z^n) =
\prod_{n=1}^{\infty}(z^{8n}+z^{7n}-z^{5n}-z^{4n}-z^{3n}+z^{n}+1).  \]

\noindent
We conclude with the following theorem, which follows easily from
Theorems 1 and 0.

\noindent
\textbf{Theorem 3}
{\it 
Let $m$, $r$, $n$, $z$ be as in the hypothesis of Theorem 1.  Let
$q_m^{E}(n)$, $q_m^{O}(n)$ denote respectively the number of
partitions of $n$ into evenly, oddly many distinct parts, $k$, such that
$(k,m)$ = 1.  Then}

\[
\prod_{n=1}^{\infty}(\Phi_m(z^{n}))^{(-1)^{r}} =
\sum_{n=0}^{\infty}(q_m^{E}(n)-q_m^{O}(n))z^{n}.
\]

\vspace{.1 in}
\noindent
{\it Proof.}
This follows from the hypothesis, Theorem 1, and Theorem 0, part (iii).
\vskip 30pt

\section*{\normalsize References}

\noindent
1.   George E. Andrews,  ``The Theory of
Partitions,''  Cambridge
University Press (1984).
\vskip 5pt
\noindent
2.   J. W. L. Glaisher, ``A theorem in partitions,''
 Messenger of Math. {\bf 12} (1883), 158-170.
\vskip 5pt
\noindent
3.   G. D. James \& A. Kerner,  ``The representation theory
of the
symmetric group,'' Addison-Wesley, Reading, MA (1981).

\vfill \noindent \footnotesize{AMS Classification: 11P83, 11P81}

\end{document}