\documentclass[nojss]{jss}

\usepackage{dsfont}
\usepackage{bbm}
\usepackage{amsfonts}
\usepackage{wasysym}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% declarations for jss.cls %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%% just as usual
\author{Robin K. S. Hankin\\University of Stirling}
\title{Additive Integer Partitions in \proglang{R}}
%\VignetteIndexEntry{Additive Integer Partitions}

%% for pretty printing and a nice hypersummary also set:
\Plainauthor{Robin K. S. Hankin}
\Plaintitle{Integer Partitions in R} 
\Shorttitle{Integer Partitions in R}

%% an abstract and keywords
\Abstract{

  To cite the \pkg{partitions} package in publications, please
  use~\cite{hankin2006}.  This vignette introduces the
  \pkg{partitions} package of \proglang{R} routines, for numerical
  calculation of integer partitions.  Functionality for unrestricted
  partitions, unequal partitions, and restricted partitions is
  provided in a small package that accompanies this note; the emphasis
  is on terse, efficient \proglang{C} code.  A simple combinatorial
  problem is solved using the package.}

\Keywords{Integer partitions, restricted partitions, unequal
  partitions, \proglang{R}}
\Plainkeywords{Integer partitions, restricted partitions, unequal
  partitions, R}

%% publication information
%% NOTE: This needs to filled out ONLY IF THE PAPER WAS ACCEPTED.
%% If it was not (yet) accepted, leave them commented.
%% \Volume{13}
%% \Issue{9}
%% \Month{September}
%% \Year{2004}
%% \Submitdate{2004-09-29}
%% \Acceptdate{2004-09-29}

%% The address of (at least) one author should be given
%% in the following format:
\Address{
  Robin K. S. Hankin\\
  University of Stirling\\
  Scotland\\
  \email{hankin.robin@gmail.com}\\
  {\rule{10mm}{0mm}}\hfill\includegraphics[width=1in]{\Sexpr{system.file("help/figures/partitions.png",package="partitions")}}
}
%% It is also possible to add a telephone and fax number
%% before the e-mail in the following format:
%% Telephone: +43/1/31336-5053
%% Fax: +43/1/31336-734

%% for those who use Sweave please include the following line (with % symbols):
%% need no \usepackage{Sweave.sty}

%% end of declarations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\SweaveOpts{echo=FALSE}
\begin{document}

\newsymbol\leqslant 1336

\hfill\includegraphics[width=1in]{\Sexpr{system.file("help/figures/partitions.png",package="partitions")}}

\section{Introduction}
A {\em partition} of a positive integer~$n$ is a non-increasing
sequence of positive integers~$\lambda_1,\lambda_2,\ldots,\lambda_r$
such that~$\sum_{i=1}^r\lambda_i=n$.  The
partition~$\left(\lambda_1,\ldots,\lambda_r\right)$ is denoted
by~$\lambda$, and we write~$\lambda\vdash n$ to signify that~$\lambda$
is a partition of~$n$.  If, for~$1\leqslant j\leqslant n$,
exactly~$f_j$ elements of~$\lambda$ are equal to~$j$, we
write~$\lambda=\left(1^{f_1},2^{f_2},\ldots,n^{f_n}\right)$; this
notation emphasises the number of times a particular integer occurs as
a part.  The standard reference is \citet{andrews1998}.

The partition function $p(n)$ is the number of distinct partitions
of~$n$.  Thus, because
\[
5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1\] is a complete enumeration of
the partitions of 5, $p(5)=7$ (recall that order is unimportant: a
partition is defined to be a non-increasing sequence).
%Euler proved that
%\begin{equation}
%p(n)=\sum_{1\leq\frac{\left(3k^2\pm k\right)}{2}\leq n}\left(-1\right)^{k-1}
%p\left(n-\left(3k^2\pm k\right)/2\right)
%\end{equation}

Various restrictions on the nature of a partition are often
considered.  One is to require that the~$\lambda_i$ are distinct; the
number of such partitions is denoted~$q(n)$.  Because
\[5=4+1=3+2\] is the complete subset of partitions of~$5$ with no
repetitions, $q(5)=3$.  
%It is known \citep{abramowitz1965} that
%\begin{equation}
%\sum_{0\leq\frac{\left(3k^2\pm k\right)}{2}\leq n}\left(-1\right)^{k}
%q\left(n-\left(3k^2\pm k\right)/2\right)=\left\{
%\begin{array}{c}
%\left(-1\right)^r\qquad\mbox{if~$n=3r^2\pm r$}\\
%0\qquad\mbox{otherwise}
%\end{array}
%\right.
%\end{equation}

One may also require that~$n$ be split into {\em exactly} $m$ parts.
The number of partitions so restricted may be denoted~$r(m,n)$.

\section[Package partitions in use]{Package \pkg{partitions} in use}

<<echo=FALSE,print=FALSE>>=
<<results=hide>>=
require(partitions)
@ 

The \proglang{R}~\citep{rmanual} package \pkg{partitions} associated
with this paper may be used to evaluate the above functions
numerically, and to enumerate the partitions they count.  In the
package, the number of partitions is given by \code{P()}, and the
number of unequal partitions by \code{Q()}.  For example,
<<echo=TRUE>>=
P(100)
@ 
agreeing with the value given by~\citet{abramowitz1965}.  The unequal
partitions of an integer are enumerated by function \code{diffparts()}:
<<echo=TRUE>>=
diffparts(10)
@
where the columns are the partitions.  Finally, function
\code{restrictedpartitions()} enumerates the partitions of an integer
into a specified number of parts.

\subsection{A combinatorial example}

Consider random sampling, with replacement, from an alphabet of~$a$
letters.  How many draws are required to give a~95\% probability of
choosing each letter at least once?  I show below how the
\pkg{partitions} package may be used to answer this question exactly.

A little thought shows that the number of ways to draw each letter at
least once in~$n$ draws is
\begin{equation}
N=
\sum_{\lambda\vdash n;a}
\frac{a!}{\prod_{i=1}^{r} f_i!}\cdot
\frac{n!}{\prod_{j=1}^{n}\lambda_i!}
\end{equation}
where the sum extends over partitions~$\lambda$ of~$n$ into
exactly~$a$ parts; the first term gives the number of ways of
assigning a partition to letters; the second gives the number of
distinct arrangements.

The corresponding \proglang{R} idiom is to define a nonce function
\code{f()} that returns the product of the two denominators, and to
sum the requisite parts by applying \code{f()} over the appropriate
restricted partitions.  The probability of getting all~$a$ letters
in~$n$ draws is thus~$N/a^n$, computed by function \code{prob()}:

<<echo=TRUE>>=
f <- function(x){prod(factorial(x),factorial(tabulate(x)))}
prob <- function(a,n){
  jj <- restrictedparts(n,a,include.zero=FALSE)
  N <- factorial(a)*factorial(n)*sum(1/apply(jj,2,f))
  return(N/a^n)
}
@ 

In the case of~$a=4$, we obtain~$n=16$
because~$\mbox{\code{prob(4,15)}}\simeq\mbox{\Sexpr{round(prob(4,15),digits=3)}}$
and~$\mbox{\code{prob(4,16)}}\simeq\mbox{\Sexpr{round(prob(4,16),digits=3)}}$.

\section{Conclusions}
The \pkg{partitions} package was developed to answer the combinatorial
word question discussed above: it does so using fast \proglang{C}
code.  Further work would include the enumeration of compositions and
vector compositions.

\subsection*{Acknowledgement}
I would like to acknowledge the many stimulating and helpful comments
made by the R-help list while preparing the package.

\bibliography{partitions}
\end{document}