# parts: Enumerate the partitions of an integer In partitions: Additive Partitions of Integers

## Description

Given an integer, return a matrix whose columns enumerate various partitions.

Function `parts()` returns the unrestricted partitions; function `diffparts()` returns the unequal partitions; function `restrictedparts()` returns the restricted partitions; function `blockparts()` returns the partitions subject to specified maxima; and function `compositions()` returns all compositions of the argument.

## Usage

 ```1 2 3 4 5``` ```parts(n) diffparts(n) restrictedparts(n, m, include.zero=TRUE, decreasing=TRUE) blockparts(f, n=NULL, include.fewer=FALSE) compositions(n, m=NULL, include.zero=TRUE) ```

## Arguments

 `n` Integer to be partitioned. In function `blockparts()`, the default of `NULL` means to return all partitions of any size `m` In functions `restrictedparts()` and `compositions()`, the order of the partition `include.zero` In functions `restrictedparts()` and `compositions()`, Boolean with default `FALSE` meaning to include only partitions of n into exactly m parts; and `TRUE` meaning to include partitions of n into at most m parts (because zero parts are included) `include.fewer` In function `blockparts()`, Boolean with default `FALSE` meaning to return vectors whose sum is exactly `n` and `TRUE` meaning to return partitions whose sum is at most `n` `decreasing` In `restrictedparts()`, Boolean with default `TRUE` meaning to return partitions whose parts are in decreasing order and `FALSE` meaning to return partitions in lexicographical order, as appearing in Hindenburg's algorithm. Note that setting to `decreasing` to `FALSE` has the effect of making `conjugate()` return garbage `f` In function `blockparts()`, a vector of strictly positive integers that gives the maximal number of blocks; see details

## Details

• Function `parts()` uses the algorithm in Andrews. Function `diffparts()` uses a very similar algorithm that I have not seen elsewhere. These functions behave strangely if given an argument of zero.

• Function `restrictedparts()` uses the algorithm in Andrews, originally due to Hindenburg. For partitions into at most m parts, the same Hindenburg's algorithm is used but with a start vector of `c(rep(0,m-1),n)`.

If m>n, the partitions are padded with zeros.

• Function `blockparts()` enumerates the compositions of an integer subject to a maximum criterion: given vector y=(y_1,...,y_p) all sets of a=(a_1,...,a_p) satisfying sum(a_i)=n subject to 0 <= a_i <= y_i for all i are given in lexicographical order. If argument `y` includes zero elements, these are treated consistently (ie a position with zero capacity).

If `n` takes its default value of `NULL`, then the restriction sum(a_i)=n is relaxed (so that the numbers may sum to anything). Note that these solutions are not necessarily in standard form, so functions `durfee()` and `conjugate()` may fail.

• With a single argument, `compositions(n)` returns all 2^(n-1) ways of partitioning an integer; thus `4+1+1` is distinct from `1+4+1` or `1+1+4`.

With two arguments, `compositions(n,m)` returns all nonnegative solutions to x_1+...+x_m=n.

This function is different from all the others in the package in that it is written in R; it is not clear that C would be any faster.

## Note

These vectorized functions return a matrix whose columns are the partitions. If this matrix is too large, consider enumerating the partitions individually using the functionality documented in `nextpart.Rd`.

One commonly encountered idiom is `blockparts(rep(n,n),n)`, which is equivalent to `compositions(n,n)` [Sloane's `A001700`].

## Author(s)

Robin K. S. Hankin

## References

• G. E. Andrews. “The theory of partitions”, Cambridge University Press, 1998

• R. K. S. Hankin 2006. “Additive integer partitions in R”. Journal of Statistical Software, Volume 16, code snippet 1

• R. K. S. Hankin 2007. “Urn sampling without replacement: enumerative combinatorics in R”. Journal of Statistical Software, Volume 17, code snippet 1

• R. K. S. Hankin 2007. “Set partitions in R”. Journal of Statistical Software, Volume 23, code snippet 2

• N. J. A. Sloane, 2008, The On-Line Encyclopedia of Integer Sequences, www.research.att.com/~njas/sequences/, Sequence A001700

`nextpart`
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20``` ```parts(5) diffparts(10) restrictedparts(9,4) restrictedparts(9,4,FALSE) restrictedparts(9,4,decreasing=TRUE) blockparts(1:4) blockparts(1:4,3) blockparts(1:4,3,include.fewer=TRUE) blockparts(c(4,3,3,2),5) # Knuth's example, Fascicle 3a, p16 compositions(4) # not the same as parts(4) compositions(4,4) # With 10 blocks, enumerate all partitions with maxima of 1:5 and minima # of c(0,1,1,2,1): a <- c(0,1,1,2,1) sweep(blockparts(1:5-a,10-sum(a)),1,a,"+") ```