%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-10/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{alg}[thm]{Algorithm}
\newtheorem{ex}[thm]{Example}
\numberwithin{equation}{section}

\title{On the partition function of a finite set
\footnote{Most of the work for this paper was done during a stay at the Institute of Mathematics, Academia Sinica, Taipei, Taiwan.}}
\author {T. C. Brown \\
Department of Mathematics\\
¶¡ÏãÔ°AV\\
Burnaby, BC\\
Canada V5A 1S6\\
email: \texttt{tbrown@sfu.ca}\\
\and
Wun-Seng Chou\\
Institute of Mathematics\\
Academia Sinica\\
Nankang, Taipei 11529, ROC\\
email: \texttt{macws@ccvax.sinica.edu.tw}\\
and\\
Peter J-S Shiue\footnote{The auther thanks the Institute of Mathematics, Academia Sinica, Taipei, Taiwan for support and a pleasant
stay.}\\
Department of Mathematical Sicences\\
University of Nevada at Las Vegas\\
Las Vegas, Nevada 89154-4020, USA\\
email: \texttt{shiue@nevada.edu}}
\maketitle
\begin{center}{\small {\bf Citation data:} Tom~C. Brown, Wun-Seng Chou, and Peter J.-S. Shiue, \emph{On the partition
  function of a finite set}, Australas. J. Combin. \textbf{27} (2003),
  193--204.}\bigskip\end{center}

\newcommand{\partn}[1]{\ensuremath{p_{_A}({#1})}}


\begin{abstract} Let $A = \{ a_1, a_2, \ldots, a_k\}$ be a set of $k$
relatively prime positive integers. Let $\partn{n}$ denote the partition function
of $n$ with parts in $A$, that is, $p_{_A}$ is the number of partitions of $n$
with parts belonging to $A$.

We survey some known results on $\partn{n}$ for general $k$, and then concentrate on
the cases $k = 2$ (where the exact value of $\partn{n}$ is known for all $n$), and
the more interesting case $k = 3$. We also describe an approach using the cycle
indicator formula.

Let $A = \{ a, b, c \}$, where $a$, $b$, $c$ are pairwise relatively prime. It
has long been known (Ehrhart, J. Reine Angew. Math. 226 (1967), 1–29) that the
problem of finding the value of $\partn{n}$ reduces to the problem of finding the
value of $\partn{r}$, where $0 \leq r < abc$. Sert\"oz and \"Ozl\"uk (Istanbul
Tek. \"Univ. B\"ul. 39 (1986), 41–51) have handled the case $abc - a - b - c <
r < abc$. Our main contribution is a recursive method for computing the value
of $\partn{r}$ in the case $r \leq abc - a - b -c$.
\end{abstract}

\section{Introduction\label{s1}}
Let $n$ be a positive integer. A \emph{partition} of $n$ is a representation of
$n$ as a sum of positive integers. The order of the terms of this sum does not
matter. The \emph{partition function}, denoted by $p(n)$, counts the number of
partitions of $n$. For example, $p(4) = 5$, since $4$ has exactly $5$ partitions:
$1 + 1 + 1 + 1$, $1 + 1 + 2$, $1 + 3$, $2 + 2$, and $4$.

Now, let $A = \{a_1, a_2,\dots, a_k\}$ be a set of $k$ relatively prime positive
integers. A \emph{partition of $n$ with parts in $A$} is a representation of $n$
as a sum of not necessarily distinct elements of $A$. Again, the order of the
terms of this sum does not matter. The \emph{partition function} in this situation,
denoted by $\partn{n}$, counts the number of partitions of $n$ with parts in $A$,
see Stanley \cite{stanley1986}. Obviously, $\partn{n}$ is the number of non-negative
integer solutions $(x_1, x_2,\dots, x_k)$ of the equation
\[ a_1x_1 + a_2x_2 + \cdots + a_kx_k = n. \]
as mentioned by Comtet \cite{comtet1974}. It is well known that for all sufficient
large $n$ the equation has a solution. Trivially, if $A = \{1, 2,\dots, n\}$,
then $p_{_A}(n) = p(n)$ (see \cite{niven+zuckerman+montgomery1991}).

The famous problem of Frobenius is to find the largest natural number $g$ such
that $\partn{g} = 0$, that is, the largest natural number $g$ which cannot be
expressed in the form $a_1x_1 + a_2x_2 + \dots + a_kx_k$, where the $x_i$ are
non-negative integers.

The Frobenius problem has a long history (See, for example, \cite{guy1994,roberts1956}).
Sylvester \cite{sylvester1882} completely solved the problem for $k = 2$ in 1882,
and Glaisher \cite{glaisher1909} simplified the proof in 1909: When $A = \{a_1, a_2\}$
and $a_1$, $a_2$ are relatively prime, then every $n \geq (a_1 - 1)(a_2 - 1)$ can be
expressed in the form $n = a_1x + a_2y$, where $x$, and $y$ are non-negative integers,
and $a_1a_2 - a_1 - a_2$ cannot be so expressed. Thus the number $g$ in this case
is $g = a_1a_2 - a_1 - a_2$.

When $k = 3$, no closed-form expression for $g$ is known, except in some special
cases, although there do exist explicit algorithms for calculating it. See for example
\cite{chen1984,davison1994,greenberg1988,hujter+visvari1987,kan+stechkin+sharkov1997,rodseth1978,selmer1977}.

It seems very difficult to calculate $g$ when $k \geq 4$ (however, see
\cite{sertoz+ozluk1986}). In the general case, various upper bounds are known (for
instance, see \cite{chen1956}), and closed-form expressions are known in a few
special cases, for example in the case that $a_1, a_2, \cdots, a_k$ is an arithmetic
progression (See \cite{roberts1956}). In fact, it has been long conjectured that
the Frobenius problem is NP-hard, and this is proved by Ramirez-Alfonsin
\cite{ramirez-alfonsin1996}.

This paper is devoted to th study of $\partn{n}$ when $k = 2$ and $3$. Our main
contribution is a recursive method for computing the value $\partn{n}$ when $n
\leq a_1a_2a_3 - a_1 - a_2 - a_3$ where $a_1,a_2,a_3$ ar pairwise relatively
prime integers. We also provide a short proof of a known result when $k = 2$
(see Theorem \ref{t41}). Our proof yields a complete explicit formula for
$\partn{n}$ in the case $k = 2$ (see Corollary \ref{c43}).

In Sections \ref{s2} and \ref{s3}, we survey some known results on $\partn{n}$
for general $k$. In Section \ref{s4}, we forucs our attention on the cases
$k=2$ and $k=3$ (see \cite{ehrhart1967-1,ehrhart1967-2} for some results
concerning the case $k=4$). Section \ref{s5} describes an approach using the
cycle indicator formula.

\section{Asymptotic formula for $\partn{n}$ and $p(n)$\label{s2}}

If $A = \{a_1, a_2,\dots, a_k\}$ is a set of $k$ relatively prime positive
integers, it is known that
\[ \partn{n} \sim \frac{n^{k-1}}{a_1a_2\cdots a_k(k - 1)!} \]
(see \cite[pp. 134, Problem 15C]{vanlint+wilson1992}). A proof of this result
appears in \cite{polya+szego1978}, Problem $27$. The proof there is based on the
generating function of $\partn{n}$. Elementary proofs are given in
\cite{nathanson2000,sertoz+ozluk1991,wright1961}. For the case $A = \{1, 2,
\cdots, k\}$, an elementary proof of this formula was given by Erd\H{o}s
\cite{erdos1942}.

For the unrestricted partition function $p(n)$, Rademacher \cite{rademacher1937}
(see also \cite{apostol1976}) gives an asymptotic formula as
\[ p(n) \sim \frac{\exp(\pi(2/3)^{1/2}n^{1/2})}{4\sqrt{3}n}, \]
a result which was proved earlier by Hardy and Ramanujan \cite{hardy+ramanujan1918}.
Erd\H{o}s \cite{erdos1942} gave an elementary proof of the relation
\[ p(n) \sim \frac{a\cdot\exp(\pi(2/3)^{1/2}n^{1/2})}{n}, \]
but was unable to show that $a = \frac{1}{4\sqrt{3}}$. Kr\"atzel
\cite{kratzel1970} proved the bound $p(n) \leq 5^{n/4}$, with equality only
when $n = 4$.

\section{Recurrence relation for $\partn{n}$ and $p(n)$\label{s3}}

Apostol \cite{apostol1976} (see also \cite{andrews1976}) shows by analytical
methods that
\[ n\partn{n} = \sum_{k=1}^n\sigma_{_A}(k)\partn{n - k}, \]
where $\sigma_{_A}(n)$ denotes the sum of those divisors of $n$ which belong to $A$.

This result generalizes a result of Euler, who proves this identity for the case
$A = \{1, 2, \dots, k\}$. This result holds for an arbitrary set $A$ of positive
integers, not necessarily finite. Hence when $A$ is the set of all positive
integers, this becomes
\[ np(n) = \sum_{k=1}^np(n - k)\sigma(k). \]

Bell \cite{bell1943} shows that if $A = \{a_1, a_2, \dots, a_k\}$ and $a$ is the
least common multiple of $\{a_1, a_2, \dots, a_k\}$, then
\[ \partn{an + b} = c_0 + c_1n + c_2n^2 + \cdots + c_{k-1}n^{k-1}, \]
where $c_0, c_1, c_2, \dots, c_k$ are constants independent of $n$ and $b$,
$0 \leq b < a$. (See also \cite{raczunas+chrzpolhkastowski-watchtel1993,wright1961}.)

The constants are fully determined if $\partn{an + b}$ is known for $k$ different
values of $n$. This can be done using Lagrange's interpolation formula. For example,
if $A = \{a_1, a_2, a_3\}$, then
\begin{align*}
2\partn{an + b}
&= (n - 2)(n - 3)p_{_A}(a + b) - 2(n - 1)(n - 3)\partn{2a + b} \\
&\qquad + (n - 1)(n - 2)\partn{3a + b}.
\end{align*}
This formula does not however provide an effective way to calculate $\partn{n}$.
Later, Kuriki \cite{kuriki1978} proves a somewhat different recursion formula
for $\partn{n}$.

Although there are a number of algorithms for finding the largest number not
representable in the form $a_1x_1 + a_2x_2 + \cdots + a_kx_k$ (see for example
\cite{greenberg1980,lewin1975,sertoz+ozluk1986}), it would be of interest to
find a fast algorithm for calculating $\partn{n}$.

\section{Cases $|A| = 2$ and $|A| = 3$\label{s3}}

In the first part of this section, we consider the case $|A| = 2$. It is quite
well known that $\partn{n} = \left[\frac{n}{ab}\right]$ or $\left[\frac{n}{ab}\right]
+ 1$ (see \cite{niven+zuckerman+montgomery1991}). However, one unified formulae
has been obtained as stated in the following theorem. This theorem is proved
independently by Sert\"oz in 1998 \cite{sertoz1998}, Tripathi in 2000
\cite{tripathi2000} and Beck and Robins \cite{beck+robins}. Their proofs involve generating functions. There is also a
simple direct proof, which we give below. We then give a simple algorithm for
calculating $\partn{n}$ based on the proof of this theorem.

\begin{thm}\label{t41} Let $A = \{a, b\}$ with $(a, b) = 1$. Define $a'(n)$
and $b'(n)$ by $a'(n)a \equiv -n \mod b$, with $1 \leq a'(n) \leq b$ and
$b'(n)b \equiv -n \mod a$ with $1 \leq b'(n) \leq a$, respectively. Then for
all $n \geq 1$,
\[ \partn{n} = \frac{n + aa'(n) + bb'(n)}{ab} - 1. \]
\end{thm}
\begin{proof}It is well known (see for example Brown and Shiue
\cite{brown+shiue1993}) that for all $n \geq 0$, if $n = qab + r$ with $0 \leq
r < ab$ then $\partn{n} = q + \partn{r}$, that for all $0 < n < ab$, $\partn{n}
= 0$ or $1$, that $\partn{n} = 1$ for $ab - a - b < n < ab$, and that $\partn{n}
= 0$ if $n = ab - a - b$. Therefore to prove the theorem we may assume that
$0 < n < ab - a - b$.

Note that $ab$ divides $aa'(n) + bb'(n) + n$, since each of $a$ and $b$ divides
$aa'(n) + bb'(n) + n$. Also, $0 < aa'(n) + bb'(n) + n < 3ab$, so that either
$aa'(n) + bb'(n) + n = ab$ or $aa'(n) + bb'(n) + n = 2ab$. Now we only need
to show that
\begin{enumerate}
\item[(i)] $aa'(n) + bb'(n) + n = ab$ implies $p_{_A}(n) = 0$;
\item[(ii)] $aa'(n) + bb'(n) + n = 2ab$ implies $p_{_A}(n) = 1$.
\end{enumerate}

If $aa'(n) + bb'(n) + n = ab$ and $as + bt = n$ for some $s, t \geq 0$, then
$aa'(n) + bb'(n) + as + bt = ab$, or $a(a'(n) + s) + b(b'(n) + t) = ab$, so
$a|(b'(n) + t)$ and $b|(a'(n) + s)$. Since $0 < b'(n) + t \leq a$ and $0 <
a'(n) + s \leq b$, this gives $a = b'(n) + t$ and $b = a'(n) + s$, hence
$2ab = ab$, a contradiction. This proves (i). To prove (ii), simply note that
if $aa'(n) + bb'(n) + n = 2ab$, then $n = a(b - a'(n)) + b(a - b'(n))$.
\end{proof}

This theorem is easy to generalize to the case $(a, b) = d$ in the following
corollary. We omit its trivial proof.

\begin{cor}\label{c42} Let $A = \{a, b\}$ with $(a, b) = d$. If $d$ divides $n$,
define $a'(n)$ and $b'(n)$ by $a'(n)\frac{a}{d} \equiv -\frac{n}{d} \mod
\frac{b}{d}$ and $b'(n)\frac{b}{d} \equiv -\frac{n}{d} \mod \frac{a}{d}$,
respectively, as those in Theorem \ref{t41}. Then for all $n \geq 1$,
\[ \partn{n} = \left\{ \begin{array}{cl}
0 & \textnormal{if $d$ does not divide $n$} \\
\frac{n + aa'(n) + bb'}{\textnormal{lcm}\{a, b\}} - 1 & \textnormal{if $d$ divides $n$.} \end{array} \right. \]
\end{cor}

From the statement and the proof of Theorem \ref{t41}, if $(a, b) = 1$, we can
compute $p_{_A}(n)$ in the following

\begin{alg} \label{c43} Let $A = \{a, b\}$ with $(a, b) = 1$. Let $n = qab + r$
with $0 \leq r < ab$. If $ab - a - b < r < ab$, then $\partn{n} = q + 1$. If
$r = ab - a - b$, then $\partn{n} = q$. For the remaining value of $r$, we have
$\partn{n} = q$ if $aa'(r) + bb'(r) + r = ab$ and $\partn{n} = q + 1$ if $aa'(r)
+ bb'(r) + r = 2ab$. (Here $a'(r)$ and $b'(r)$ are defined as in the statement
of the theorem.)
\end{alg}

We now give examples using this corollary. We do not write down all partitions
and only compute the number $\partn{n}$ instead.

\begin{ex} \label{e44} \cite{sertoz1998} Let $n = 123456789012345$ and $A =
\{a,b\}$, where $a = 1234567$, $b = 12345678$. Write $q = 8$ and $r = 1524255800937$.
Then we have $n = q\cdot ab + r$. Moreover, $a'(r) = 462963$ and $b'(r) = 1064806$.
Hence, $aa'(r) + bb'(r) + r = 15241566651426 = ab$. By Corollary \ref{c43}, we
have $\partn{n} = 8$.\end{ex}

We now consider the case $|A| = 3$ in the remaining part of this section. The
case is a little bit more complicated. First of all, we need the following lemma.
In this lemma and afterwards, $u_v'(t)$ will denote the number $1 \leq u_v'(t)
\leq v$ satisfying $uu_v'(t) \equiv -t \mod v$, whenever $u, v \geq 1$ and $t$
are integers satisfying $(u, v) = 1$.

\begin{lem}\label{l45} Let $A = \{a, b, c\}$, where $a, b$, and $c$ are relatively
prime positive integers. Write $d_3 = (a, b)$, $d_1 = (b, c)$, and $d_2 = (c, a)$.
Then for any integer $n > 0$, the number $n' = n - (d_1 - a_{d_1}'(n))a - (d_2 -
b_{d_2}'(n))b - (d_3 - c_{d_3}'(n))c$ is divisible by $d_1d_2d_3$. Moreover,
$\partn{n} = p_{_{A'}}(\frac{n'}{d_1d_2d_3})$, where $A' = \{\frac{a}{d_2d_3},
\frac{b}{d_3d_1}, \frac{c}{d_1d_2}\}$ and where we use the convention that
$p_{_{A'}}(0) = 1$ and $p_{_{A'}}(\frac{n'}{d_1d_2d_3}) = 0$ if $n' < 0$.
\end{lem}
\begin{proof} If $ax + by + cz = n$ with $x, y, z \geq 0$, then $d_3$ divides
$n - cz = ax + by$. Since $d_3 - c_{d_3}'(n)$ is the smallest nonnegative integer
$u$ such that $d_3$ divides $n - uc$, $z = d_3z' + (d_3 - c_{d_3}'(n))$ for some
nonnegative integer $z'$. Similarly, $x = d_1x' + (d_1 - a_{d_1}'(n))$ and $y
= d_2y' + (d_2 - b_{d_2}'(n))$ for some nonnegative integers $x'$ and $y'$,
respectively. So, $ax + by + cz = n$ with $x, y, z \geq 0$ if and only if
$a(x - (d_1 - a_{d_1}'(n))) + b(y - (d_2 - b_{d_2}'(n))) + c(z - (d_3 - c_{d_3}'(n)))
= n'$ with $x - (d_1 - a_{d_1}'(n)), y - (d_2 - b_{d_2}'(n)), z - (d_3 - c_{d_3}')
\geq 0$. This implies that $d_1d_2d_3$ divides $n'$. Moreover,
\[ \frac{a(x - (d_1 - a_{d_1}'(n)))}{d_1d_2d_3} +
\frac{b(y - (d_2 - b_{d_2}'(n)))}{d_1d_2d_3} +
\frac{c(z - (d_3 - c_{d_3}'(n)))}{d_1d_2d_3} = \frac{n'}{d_1d_2d_3}. \]
This implies $\partn{n} = p_{_{A'}}(\frac{n'}{d_1d_2d_3})$.\end{proof}

From this lemma, it is enough to consider, afterwards, the set $A = \{a, b, c\}$
such that positive integers $a, b$, and $c$ are relatively prime in pairs, i.e.,
$(a, b) = (b, c) = (c, a) = 1$. The following two theorems are quite well-known.

\begin{thm}[Ehrhart \cite{ehrhart1967-1}] \label{t46} Let $A = \{a, b, c\}$,
where positive integers $a, b$, and $c$ are relatively prime in pairs. Let
$n = q\cdot abc + r$ with $0 \leq r < abc$. Then
\[ \partn{n} = \partn{r} + \frac{q(n + r + a + b + c)}{2}. \]
In particular,
\[ \partn{abc} = \frac{abc + a + b + c}{2} + 1. \]
\end{thm}

\begin{thm}[Sert\"oz and \"Ozl\"uk \cite{sertoz+ozluk1991}] \label{t47}
Let $A = \{a, b, c\}$ where $a, b$, and $c$ are relatively prime in pairs.
Let $n = q\cdot abc + r$ with $0 \leq r < abc$. Then, for $1 \leq x \leq a + b + c - 1$,
\[ \partn{abc - x} = \frac{abc + a + b + c}{2} - x. \]
In particular,
\[ \partn{abc - a - b - c + 1} = \frac{abc - a - b - c}{2} + 1. \]
\end{thm}

It seems that it is not easy to find a ``simple'' closed form for computing
$\partn{n}$ whenever $n \leq abc - a - b - c$. Here, we are going to give a
method to compute such $\partn{n}$. For this purpose, we need the following

\begin{prop} \label{p48} Let $A = \{ a,b,c\}$ where positive integers $a,b,c$
are pairwise relatively prime and let $n$ be a non-negative integer. Then
\[ \partn{n} = \left\{ \begin{array}{cl}
\partn{n - a - b - c} + q_{_A}(n) & \textnormal{if $n\geq a + b + c$} \\
q_{_A}(n) & \textnormal{if $1 \leq n < a + b + c$}\end{array}\right. \]
where $q_{_A}(n) = p_{_{A\setminus\lbrace a\rbrace}}(n) + p_{_{A\setminus\lbrace b\rbrace}}(n)
+ p_{_{A\setminus\lbrace c\rbrace}}(n) - \epsilon_a(n) - \epsilon_b(n) - \epsilon_c(n)$
with
\[ \epsilon_d(m) = \left\{\begin{array}{cl} 1&\textnormal{ if } d|m\\0&\textnormal{otherwise.}\end{array}\right. \]
\end{prop}
\begin{proof} Write $E_{\{a,b,c}\}(n) = \{(x,y,z) | x,y,z\geq 0 \text{ are integers,
and } xa + yb + zc = n \}$. Let $(x_1,y_1,z_1)\in E_{\{a,b,c}\}(n)$. If $0 < n <
a + b + c$ then $x_1y_1z_1 = 0$. Thus, $\partn{n - a - b - c} = |E_{\{a,b,c}\}(n)
\setminus\{E_{\{a,b,0\}}(n)\cup E_{\{a,0,c}\}(n)\cup E_{\{0,b,c}\}(n)\}|$ and the
result follows by the inclusion-exclusion formula.\end{proof}

In the following corollary the values $\partn{abc - a - b - c}$ and $\partn{abc
- a - b -c - 1}$ are obtained as particular cases of Proposition \ref{p48}.

\begin{cor}\label{c49} Let $A = \{a,b,c\}$ where $a$, $b$ and $c$ are positive
pairwise relatively prime integers. Then
\[ \partn{abc - a - b - c} = \frac{abc -a -b -c}2 + 1. \]
and
\[ \partn{abc - a - b - c - 1} = \frac{abc -a -b -c}2 - 1. \]
\end{cor}
\begin{proof} From Proposition \ref{p48}, we have $\partn{abc - a - b - c}
= \partn{abc} - p_{_{A\setminus\lbrace a\rbrace}}(abc) - p_{_{A\setminus\lbrace b\rbrace}}(abc)
- p_{_{A\setminus\lbrace c\rbrace}}(abc) + \epsilon_a(abc) + \epsilon_b(abc) + \epsilon_c(abc)$.
By Theorem \ref{t46}, we have that $\partn{abc} = \frac{abc + a + b + c}2 + 1$ and, by
Corollary \ref{c43}, we obtain that $p_{_{A\setminus\lbrace a\rbrace}}(abc) = a + 1$,
$p_{_{A\setminus\lbrace b\rbrace}}(abc) = b + 1$, and $p_{_{A\setminus\lbrace c\rbrace}}(abc)
= c + 1$. Since $\epsilon_a(abc) = \epsilon_b(abc) = \epsilon_c(abc) = 1$ then $\partn{abc
-a -b -c} = \frac{abc - a - b - c}2 + 1$.

Now again, from Proposition \ref{p48}, we have $\partn{abc - a - b - c - 1} =
\partn{abc - 1} - p_{_{A\setminus\lbrace a\rbrace}}(abc - 1) - p_{_{A\setminus\lbrace b\rbrace}}(abc - 1)
- p_{_{A\setminus\lbrace c\rbrace}}(abc-1) + \epsilon_a(abc-1) + \epsilon_b(abc-1) + \epsilon_c(abc-1)$.
By Theorem \ref{t47}, we have that $\partn{abc - 1} \frac{abc +a+b+c}2 - 1$ and, by
Corollary \ref{c43}, we obtain that $p_{_{A\setminus\lbrace a\rbrace}}(abc-1) =
p_{_{A\setminus\lbrace a\rbrace}}((a-1)bc+ (bc -1)) = a$ (similarly, $p_{_{A\setminus\lbrace b\rbrace}}(abc-1)
= b$ and $p_{_{A\setminus\lbrace c\rbrace}}(abc-1) = c$). Since $\epsilon_a(abc - 1)
= \epsilon_b(abc - 1) = \epsilon_c(abc - 1) = 0$ then $\partn{abc - a - b - c - 1}
= \frac{abc - a -b -c}2 - 1$.\end{proof}

Using Proposition \ref{p48}, we will give a method to compute $\partn{n}$ for
$n \leq abc - a - b - c$ in the following theorem. For this purpose, we need
the notation that for positive integers $u$ and $v$ with $(u,v) = 1$, write
$v_u'(n)$ instead of $v'(n)$ as in Theorem \ref{t41}.

\begin{thm}\label{t410} Let $A = \{a,b,c\}$ where positive integers $a$, $b$
and $c$ are pairwise relatively prime. Let $n$ be a positive integer and let
$t$ be the largest integer such that $n - t(a + b + c) \geq 0$. Then,
\begin{align*}
\partn{n}
&= \frac{2n(t+1)s_3 - t(t+1)s_3^2}{2abc} + \frac1a\sum_{i=0}^t(b_a'(n - is_3) + c_a'(n - is_3)) \\
&\qquad + \frac1b\sum_{i=0}^t(c_b'(n - is_3) + a_b'(n - is_3))
+ \frac1c\sum_{i=0}^t(a_c'(n - is_3) + b_c'(n - is_3)) \\
&\qquad - 3(t+1) - \sum_{i=0}^t(\epsilon_a(n - is_3) + \epsilon_b(n - is_3) + \epsilon_c(n - is_3))
\end{align*}
where $s_3 = a + b + c$ with $\epsilon_d(m)$ defined as in Proposition \ref{p48}.
\end{thm}
\begin{proof} By applying recursively Proposition \ref{p48}, we have that
\[ \partn{n} = \sum_{i=0}^{t-1}q_{_A}(n - is_3) + \partn{n - ts_3} = \sum_{i=0}^t q_{_A}(n - is_3) \]
where $q_{_A}(m)$ is defined as in Proposition \ref{p48}. Hence,
\begin{align*}
\sum_{i=0}^t q_{_A}(n - is_3)
&= \sum_{i=0}^t(p_{_{A\setminus\lbrace a\rbrace}}(n - is_3) + p_{_{A\setminus\lbrace b\rbrace}}(n - is_3) + p_{_{A\setminus\lbrace c\rbrace}}(n - is_3)) \\
&\qquad - \sum_{i=0}^t (\epsilon_a(n - is_3) + \epsilon_b(n - is_3) + \epsilon_c(n - is_3)).
\end{align*}
The result follows by using Theorem \ref{t41}.
\end{proof}

We give the following example as an illustration of the theorem.

\begin{ex}\label{e411} Consider $A = \{5,7,11\}$ and $n = 41$. Write $a = 5$,
$b = 7$ and $c = 11$ for convenience. Then, $s_3 = a + b + c = 23$. Since
$41 = 1\times23 + 18$, $t = 1$. It is easy to see that the first term in
the theorem equals
\[ \frac{2n(t+1)s_3 - t(t+1)s_3^2}{2abc} = \frac{1357}{385}. \]

For positive integers $u$ and $v$ with $(a, b) = 1$, let $u_v^{-1}$ be the
multiplicative inverse of $u$ modulo $v$. It easy to see that $a_b^{-1} = 3$,
$a_c^{-1} = 9$, $b_a^{-1} = 3$, $b_c^{-1} = 8$, $c_a^{-1} = 1$, and $c_b^{-1}
= 2$. Write $k = 18$. Then,
$a_b'(k+is_3) \equiv -a_b^{-1}k - i(1 + a_b^{-1}c) \equiv 2 + i$ (mod 7)
for $i = 0,1$. Also,
$a_c'(k+is_3) \equiv 3 + 2i$ (mod 11),
$b_a'(k+is_3) \equiv 1 + i$ (mod 5),
$b_c'(k+is_3) \equiv 10 + 3i$ (mod 11),
$c_a'(k+is_3) \equiv 2 + 2i$ (mod 5), and
$c_b'(k+is_3) \equiv 6 + 3i$ (mod 7) for $i = 0,1$.
So,
$\frac1a\sum_{i=0^1}(b_a'(k + is_3) + c_a'(k + is_3) = \frac95$,
$\frac1b\sum_{i=0^1}(a_b'(k + is_3) + c_b'(k + is_3) = \frac{13}7$,
$\frac1c\sum_{i=0^1}(a_c'(k + is_3) + b_c'(k + is_3) = \frac{20}{11}$.
Moreover, neither 18 nor 41 is divided by any one of 5, 7 and 11. Hence,
$\epsilon_a(k + is_3) = \epsilon_b(k + is_3) = \epsilon_c(k + is_3) = 0$
for $i = 0,1$. Combining all results above together, we have
\[ \partn{A}(41) = \frac{1357}{385} + \frac95 + \frac{13}7 + \frac{20}{11} - 3(1 + 1) - 0 = 3. \]

Indeed, there are exactly 3 partitions of 41 with parts in $A$, namely
\begin{align*}
41 &= 5 + 5 + 5 + 5 + 7 + 7 + 7 \\
&= 5 + 5 + 5 + 5 + 5 + 5 + 11 \\
&= 5 + 7 + 7 + 11 + 11.
\end{align*}
\end{ex}

\section{The cycle indicator formula\label{s5}}

The cycle indicator $C_n$ of the symmetric permutation group of $n$ letters is
an effective tool in enumerative combinatorics, which may be written in the form
(cf. \cite{riordan1980})
\[ C_n(t_1, t_2, \dots, t_n) = \sum\frac{n!}{k_1!k_2!\cdots k_n!}\left( \frac{t_1}{1} \right)^{k_1} \left( \frac{t_2}{2} \right)^{k_2}
\cdots \left( \frac{t_n}{n} \right)^{k_n}, \]
where $t_1, t_2, \dots, t_n$ are real numbers and the summation is over all
non-negative integer solutions $k_1, k_2, \dots, k_n$ of the equation $k_1 +
2k_2 + \cdots + nk_n = n$.

Let $\sigma(n) = \sum_{d|n}d$. Then Hsu and Shiue \cite{hsu+shiue2001} obtain
\[ p(n) = \frac{1}{n!}C_n(\sigma(1), \sigma(2), \dots, \sigma(n)), \]
where $p(n)$ is the unrestricted partition function from Section \ref{s1} above.
From this, they obtain by purely combinatorial methods the previously mentioned
recurrence relation
\[ np(n) = \sum_{k=1}^{n}\sigma(k)p(n - k). \]

The cycle indicator equality above can be generalized in the following way. Let
$A$ be any given set of positive integers. ($A$ can be finite or infinite.)
Define $\partn0 = 1$ and $\sigma_{_A}(n) = \sum_{d|n, d\in A}d$. Then Hsu and
Shiue \cite{hsu+shiue2001} obtain
\[ \partn{n} = \frac{1}{n!}C_n(\sigma_{_A}(1), \sigma_{_A}(2), \dots, \sigma_{_A}(n)), \]
and consequently they deduce, again by purely combinatorial methods,
\[ n\partn{n} = \sum_{k=1}^{n}\sigma_{_A}(k)p_{_A}(n - k). \]

As a particular instance, let us take $H = \{2^0, 2^1, 2^2, \dots\}$, so that
$b(n) = p_H(n)$ is the number of \emph{binary partitions} of $n$. Let $\beta(n)
= \sum_{2^i|n}2^i$. Then the above equations become
$b(n) = \frac{1}{n!}C_n(\beta(1), \beta(2), \dots, \beta(n))$ and
$nb(n) = \sum_{k=1}^n\beta(k)b(n - k)$.

\section*{Acknowledgment}

The authors wish to express their sincere thanks to the referee for very helpful
comments and suggestions that led to a considerable improvement of this paper.

%\bibitem{As}
%G. E. Andrews, The Theory of Partition, Encyclopedia of Mathematics and its Applications, Vol. 2. Addison-Wesley, Reading, Mass.,
%1976.
%\bibitem{Al}
%T. M. Apostol, Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg,
%1976.
%
%\bibitem{Bl}
%E. T. Bell, {\it Interpolated denumerants and Lambert series}, Amer. J. Math. {\bf 65} (1943), 382-386.
%
%\bibitem{BS}
%T. C. Brown and P. J.-S. Shiue, {\it A remark related to the Frobenius problem}, Fibonacci Quart. {\bf 31} (1993), 32-36.
%
%\bibitem{Cn1}
%Z.-M. Chen, {\it A theorem on linear form with integral coefficient} (in Chinese), Sichuan Daxue Xuebao, {\bf } (1956), No. 1, 1-3.
%
%\bibitem{Cn2}
%Z.-M. Chen, {\it An algorithm to find $M_3$} (in Chinese), J. Southwest Teachers College {\bf 3} (1984), 2-8.
%
%\bibitem{Ct}
%L. Comtet, Advanced Combinatorics, The Art of Finite and Infinite Expansions, Revised and enlarged edition, D. Reidel, Dordrecht,
%1974
%
%\bibitem{Dn}
%J. L. Davison, {\it On the linear Diophantine problem of Frobenius}, J. Number Theory {\bf 48} (1994), 353-363.
%
%\bibitem{Et1}
%E. Ehrhart, {\it Sur un probl$\grave{e}$me de g$\acute{e}$om$\acute{e}$trie diophantienne lin$\acute{e}$aire. I. Poly$\grave{e}$dres
%et r$\acute{e}$seaux} (French), J. Reine Angew. Math. {\bf 226} (1967), 1-29.
%
%\bibitem{Et2}
%E. Ehrhart, {\it Sur un probl$\grave{e}$me de g$\acute{e}$om$\acute{e}$trie diophantienne lin$\acute{e}$aire. II. Syst$\grave{e}$mes
%diophantiens lin$\acute{e}$aires} (French), J. Reine Angew. Math. {\bf 227} (1967), 25-49.
%
%\bibitem{Es}
%P. Erd$\ddot{\mbox{o}}$s, {\it On an elementary proof of some asymptotic formulas in the theory of partition}, Ann. of Math. (2)
%{\bf 43} (1942), 437-450.
%
%\bibitem{Gg}
%H. Greenberg, {\it An algorithm for a linear Diophantine equation and a problem of Frobenius}, Numer. Math. {\bf 43} (1980),
%349-352.
%
%\bibitem{Gg1}
%H. Greenberg, {\it Solution to a linear Diophantine equation for nonnegative integers}, J. Algorithms {\bf 9} (1988), 343-353.
%
%\bibitem{Gr}
%J. W. L. Glaisher, {\it Formulae for partitions into given elements, derived from Sylvester's theorem}, Quart. J. Math., vol. {\bf
%40} (1909), 275-348.
%
%\bibitem{Gy}
%R. K. Guy, Unsolved Problem in Number Theory, Second edition. Problem Books in Mathematics. Unsolved Problems in Intuitive
%Mathematics, I, Springer-Verlag, New York, 1994.
%
%\bibitem{HR}
%G. H. Hardy and S. Ramanujan, Proc. London Math. Soc. {\bf 17} (1918), 75-115.
%
%\bibitem{HS}
%L. C. Hsu and P. J.-S. Shiue, {\it Cycle indicator and special polynomials}, Annals of Combinatorics, to appear. 2001
%
%\bibitem{HV}
%M. Hujter and B. Vizv$\acute{\mbox{a}}$ri, {\it The exact solutions to the Frobenius problem with three variables}, J. Ramanujan
%Math. Soc. {\bf 2} (1987), 117-143.
%
%\bibitem{KSS}
%I. D. Kan, B. S. Stechkin, and I. V. Sharkov, {\it On the Frobenius problem for three arguments} (Russian), Mat. Zametki {\bf 62}
%(1997), 626-629; translation in Math. Notes {\bf 62} (1997), 521-523.
%
%\bibitem{Kl}
%E. Kr$\ddot{\mbox{a}}$tzel, {\it Die maximale Ordnung der Anzahl der wesentlich verschiedenen abelschen Gruppen \$n\$-ter Ordnung}
%(German), Quart. J. Math. Oxford Ser. (2) {\bf 21} (1970), 273-275.
%
%\bibitem{Ki}
%S. Kuriki, {\it Sur une m$\acute{e}$thode de calcul du d$\acute{e}$num$\acute{e}$rant}, TRU Math. {\bf 14} (1978), 47-48.
%
%\bibitem{Ln}
%M. Lewin, {\it An algorithm for a solution of a problem of Frobenius}, J. Reine Angew. Math. {\bf 276} (1975), 68-82.
%
%\bibitem{Nn}
%M. B. Nathanson, {\it Partition with parts in a finite set}, Proc. Amer. Math. Soc. {\bf 128} (2000), 1269-1273.
%
%\bibitem{NZM}
%I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to The Theory of Numbers, fifth ed., Wiley, New York, 1991.
%
%\bibitem{PS}
%G. P$\acute{\mbox{o}}$lya and G. Szeg$\ddot{\mbox{o}}$, Problems and Theorems in Analysis. I. Series, Integral Calculus, Theory of
%Functions. Translated from the German by D. Aeppli. Corrected printing of the revised translation of the fourth German edition.
%Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 193. Springer-Verlag, Berlin-New
%York, 1978.
%
%\bibitem{RC}
%M. Raczunas and P. Chrzpolhkastowski-Wachtel, {\it A Diophantine problem of Frobenius in terms of the least common multiple},
%Selected papers in honor of Paul Erd$\ddot{\mbox{o}}$s on the occasion of his $80$th birthday (Keszthely, 1993), Discrete Math. {\bf
%150} (1996), 347-357.
%
%\bibitem{Rr}
%H. Rademacher, {\it On the partition function p(n)}, Proc. London Math. Soc. {\bf 43} (1937), 241-254.
%
%\bibitem{R-A}
%J. L. Ramirez-Alfonsin, {\it Complexity of the Frobenius problem}, Combinatorica {\bf 16} (1996), 143-147.
%
%\bibitem{Rn}
%J. Riordan, An Introduction to Combinatorial Analysis, reprint of the 1958 edition, Princeton University Press, Princeton, N.J.,
%1980.
%
%\bibitem{Rs}
%J. B. Roberts, {\it Note on linear forms}, Proc. Amer. Math. Soc. {\bf 7} (1956), 465-469.
%
%\bibitem{Rh}
%$\ddot{\mbox{O}}$. J. R$\ddot{\mbox{o}}$dseth, {\it On a linear diophantine problem of Frobenius}, J. reine angew. Math. {\bf 301}
%(1978), 171-178.
%
%\bibitem{Sr}
%E. S. Selmer, {\it On the linear Diophantione problem of Frobenius}, J. Reine Angew. Math. {\bf 293/294} (1977), 1-17.
%
%\bibitem{Sz}
%S. Sert$\ddot{\mbox{o}}$z, {\it On the number of solutions of a Diophantine equation of Frobenius}, Discrete Math. Appl. {\bf 8}
%(1998), 153-162.
%
%\bibitem{SO1}
%S. Sert$\ddot{\mbox{o}}$z and A. E. $\ddot{\mbox{O}}$zl$\ddot{\mbox{u}}$k, {\it On a Diophantine problem of Frobenius}, Istanbul
%Tek. $\ddot{\mbox{U}}$niv. B$\ddot{\mbox{u}}$l. {\bf 39} (1986), 41-51.
%
%\bibitem{SO2}
%S. Sert$\ddot{\mbox{o}}$z and A. E. $\ddot{\mbox{O}}$zl$\ddot{\mbox{u}}$k, {\it On the number of representations of an integer by a
%linear form}, Istanbul $\ddot{\mbox{U}}$niv. Fen Fak. Mat. Derg. {\bf 50} (1991), 67-77.
%
%\bibitem{Sr}
%J. J. Sylvester, {\it Excursus on rational fractions and partitions}, Amer. J. Math., vol. {\bf 5} (1882), 119-136.
%
%\bibitem{Sy}
%R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth \& Brooks Co., Monterey, California, 1986.
%
%\bibitem{Ti}
%A. Tripathi, {\it The number of solutionS to $ax + by = n$}, Fibonacci Quart. {\bf 38} (2000), 290-293.
%
%\bibitem{LW}
%J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, Cambridge, 1992 (p. 134, problem 15C).
%
%\bibitem{Wt}
%E. M. Wright, {\it A simple proof of a known result in partitions}, Amer. Math. Monthly {\bf 68} (1961), 144-145.
%

\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}