1\documentclass[nojss]{jss}
2
3\usepackage{dsfont}
4\usepackage{bbm}
5\usepackage{amsfonts}
6\usepackage{wasysym}
7
8%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9%% declarations for jss.cls %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
10%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11
12
13%% just as usual
14\author{Robin K. S. Hankin\\Auckland University of Technology}
15\title{Additive Integer Partitions in \proglang{R}}
16%\VignetteIndexEntry{Additive Integer Partitions}
17
18%% for pretty printing and a nice hypersummary also set:
19\Plainauthor{Robin K. S. Hankin}
20\Plaintitle{Integer Partitions in R}
21\Shorttitle{Integer Partitions in R}
22
23%% an abstract and keywords
24\Abstract{
25
26  This vignette is based on~\cite{hankin2006}.
27
28  This vignette introduces the \pkg{partitions} package of
29  \proglang{R} routines, for numerical calculation of integer
30  partititions.  Functionality for unrestricted partitions, unequal
31  partitions, and restricted partitions is provided in a small package
32  that accompanies this note; the emphasis is on terse, efficient
33  \proglang{C} code.  A simple combinatorial problem is solved using
34  the package.}
35
36\Keywords{Integer partitions, restricted partitions, unequal
37  partitions, \proglang{R}}
38\Plainkeywords{Integer partitions, restricted partitions, unequal
39  partitions, R}
40
41%% publication information
42%% NOTE: This needs to filled out ONLY IF THE PAPER WAS ACCEPTED.
43%% If it was not (yet) accepted, leave them commented.
44%% \Volume{13}
45%% \Issue{9}
46%% \Month{September}
47%% \Year{2004}
48%% \Submitdate{2004-09-29}
49%% \Acceptdate{2004-09-29}
50
51%% The address of (at least) one author should be given
52%% in the following format:
53\Address{
54  Robin K. S. Hankin\\
55  Auckland University of Technology\\
56  AUT Tower\\
57  Wakefield Street\\
58  Auckland, New Zealand\\
59  E-mail: \email{hankin.robin@gmail.com}
60}
61%% It is also possible to add a telephone and fax number
62%% before the e-mail in the following format:
63%% Telephone: +43/1/31336-5053
64%% Fax: +43/1/31336-734
65
66%% for those who use Sweave please include the following line (with % symbols):
67%% need no \usepackage{Sweave.sty}
68
69%% end of declarations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
70
71
72\SweaveOpts{echo=FALSE}
73\begin{document}
74
75\newsymbol\leqslant 1336
76
77\section{Introduction}
78A {\em partition} of a positive integer~$n$ is a non-increasing
79sequence of positive integers~$\lambda_1,\lambda_2,\ldots,\lambda_r$
80such that~$\sum_{i=1}^r\lambda_i=n$.  The
81partition~$\left(\lambda_1,\ldots,\lambda_r\right)$ is denoted
82by~$\lambda$, and we write~$\lambda\vdash n$ to signify that~$\lambda$
83is a partition of~$n$.  If, for~$1\leqslant j\leqslant n$,
84exactly~$f_j$ elements of~$\lambda$ are equal to~$j$, we
85write~$\lambda=\left(1^{f_1},2^{f_2},\ldots,n^{f_n}\right)$; this
86notation emphasises the number of times a particular integer occurs as
87a part.  The standard reference is \citet{andrews1998}.
88
89The partition function $p(n)$ is the number of distinct partitions
90of~$n$.  Thus, because
91\[
925=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1\] is a complete enumeration of
93the partitions of 5, $p(5)=7$ (recall that order is unimportant: a
94partition is defined to be a non-increasing sequence).
95%Euler proved that
96%\begin{equation}
97%p(n)=\sum_{1\leq\frac{\left(3k^2\pm k\right)}{2}\leq n}\left(-1\right)^{k-1}
98%p\left(n-\left(3k^2\pm k\right)/2\right)
99%\end{equation}
100
101Various restrictions on the nature of a partition are often
102considered.  One is to require that the~$\lambda_i$ are distinct; the
103number of such partitions is denoted~$q(n)$.  Because
104\[5=4+1=3+2\] is the complete subset of partitions of~$5$ with no
105repetitions, $q(5)=3$.
106%It is known \citep{abramowitz1965} that
107%\begin{equation}
108%\sum_{0\leq\frac{\left(3k^2\pm k\right)}{2}\leq n}\left(-1\right)^{k}
109%q\left(n-\left(3k^2\pm k\right)/2\right)=\left\{
110%\begin{array}{c}
111%\left(-1\right)^r\qquad\mbox{if~$n=3r^2\pm r$}\\
112%0\qquad\mbox{otherwise}
113%\end{array}
114%\right.
115%\end{equation}
116
117One may also require that~$n$ be split into {\em exactly} $m$ parts.
118The number of partitions so restricted may be denoted~$r(m,n)$.
119
120\section[Package partitions in use]{Package \pkg{partitions} in use}
121
122<<echo=FALSE,print=FALSE>>=
123<<results=hide>>=
124require(partitions)
125@
126
127The \proglang{R}~\citep{rmanual} package \pkg{partitions} associated
128with this paper may be used to evaluate the above functions
129numerically, and to enumerate the partitions they count.  In the
130package, the number of partitions is given by \code{P()}, and the
131number of unequal partitions by \code{Q()}.  For example,
132<<echo=TRUE>>=
133P(100)
134@
135agreeing with the value given by~\citet{abramowitz1965}.  The unequal
136partitions of an integer are enumerated by function \code{diffparts()}:
137<<echo=TRUE>>=
138diffparts(10)
139@
140where the columns are the partitions.  Finally, function
141\code{restrictedpartitions()} enumerates the partitions of an integer
142into a specified number of parts.
143
144\subsection{A combinatorial example}
145
146Consider random sampling, with replacement, from an alphabet of~$a$
147letters.  How many draws are required to give a~95\% probability of
148choosing each letter at least once?  I show below how the
149\pkg{partitions} package may be used to answer this question exactly.
150
151A little thought shows that the number of ways to draw each letter at
152least once in~$n$ draws is
153\begin{equation}
154N=
155\sum_{\lambda\vdash n;a}
156\frac{a!}{\prod_{i=1}^{r} f_i!}\cdot
157\frac{n!}{\prod_{j=1}^{n}\lambda_i!}
158\end{equation}
159where the sum extends over partitions~$\lambda$ of~$n$ into
160exactly~$a$ parts; the first term gives the number of ways of
161assigning a partition to letters; the second gives the number of
162distinct arrangements.
163
164The corresponding \proglang{R} idiom is to define a nonce function
165\code{f()} that returns the product of the two denominators, and to
166sum the requisite parts by applying \code{f()} over the appropriate
167restricted partitions.  The probability of getting all~$a$ letters
168in~$n$ draws is thus~$N/a^n$, computed by function \code{prob()}:
169
170<<echo=TRUE>>=
171f <- function(x){prod(factorial(x),factorial(tabulate(x)))}
172prob <- function(a,n){
173  jj <- restrictedparts(n,a,include.zero=FALSE)
174  N <- factorial(a)*factorial(n)*sum(1/apply(jj,2,f))
175  return(N/a^n)
176}
177@
178
179In the case of~$a=4$, we obtain~$n=16$
180because~$\mbox{\code{prob(4,15)}}\simeq\mbox{\Sexpr{round(prob(4,15),digits=3)}}$
181and~$\mbox{\code{prob(4,16)}}\simeq\mbox{\Sexpr{round(prob(4,16),digits=3)}}$.
182
183\section{Conclusions}
184The \pkg{partitions} package was developed to answer the combinatorial
185word question discussed above: it does so using fast \proglang{C}
186code.  Further work would include the enumeration of compositions and
187vector compositions.
188
189\subsection*{Acknowledgement}
190I would like to acknowledge the many stimulating and helpful comments
191made by the R-help list while preparing the package.
192
193\bibliography{partitions}
194\end{document}
195