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