\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 Cambridge}
\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{

  This vignette is based on~\cite{hankin2006}.

  This vignette introduces the \pkg{partitions} package of
  \proglang{R} routines, for numerical calculation of integer
  partititions.  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 Cambridge\\
  19 Silver Street\\
  Cambridge CB3 9EP\\
  United Kingdom\\
  E-mail: \email{hankin.robin@gmail.com}
}
%% 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

\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}
