Compute the Bell numbers

Description

This function computes the Bell numbers, which is the summ of Stirling numbers of the second kind, S(n, k), over k = 1,\ldots, n, i.e.

B_n = \sum_{k=1}^{n}S(n, k),n \ge 1

Usage

Bell(n)

B(n)

Arguments

Value

An vector of Bell numbers

Functions

• B(): Compute the Bell numbers

Author(s)

James Curran

References

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Recurrence_relation

See Also

Stirling2

Examples

## returns B(6)
Bell(6)

## returns B(1), B(2), ..., B(6)
B(1:6)

Compute Stirling numbers of the second kind

Description

This function computes Stirling numbers of the second kind, S(n, k), which count the number of ways of partitioning n distinct objects in to k non-empty sets.

Usage

Stirling2(n, k)

S2(n, k)

Arguments

Details

The implementation on this function is a simple recurrence relation which defines

S(n, k) = kS(n - 1, k), + S(n - 1, k - 1)

for k > 0 with the inital conditions S(0, 0) = 1 and S(n, 0) = S(0, n) = 0. If n and n have different lengths then expand.grid is used to construct a vector of (n, k) pairs

Value

An vector of Stirling numbers of the second kind

Functions

• S2(): Compute Stirling numbers of the second kind

Author(s)

James Curran

References

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Recurrence_relation

Examples

## returns S(6, 3)
Stirling2(6, 3)

## returns S(6,1), S(6,2), ..., S(6,6)
S2(6, 1:6)

## returns S(6,1), S(5, 2), S(4, 3)
S2(6:4, 1:3)

Generate and return all permutations of a multiset

Description

This function will return all permutations of a multiset

Usage

allPerm(mcObj)

Arguments

Details

This function will return all permutations of a multiset. It makes no check to see if this is a sensible thing to do. Users are advised to check how many permutations are possible using the multinom function in this package.

Value

A matrix with each row being a different permutation of the multiset

Note

This function does not warn the user that the requested set of permutations may be very large. In addition, all working is handled entirely in memory, and so this may cause it to crash if the request is execeptionally large.

Author(s)

James M. Curran

See Also

initMC, multinom

Examples

## a small numeric example with 6 permuations
x = c(1,1,2,2)
m = initMC(x)
allPerm(m)

## a large character example - 60 possibilities
x = rep(letters[1:3], 3:1)
multinom(x) ## calculate the number of permutations
m = initMC(x)
allPerm(m)

Generate all, or a subset, of the integer partitions of an integer n.

Description

This function will return either all, or a length restricted subset of the integer partitions of an integer n. The method works by considering compositions rather than partions, hence the name.

Usage

genComp(n, len = TRUE, addZeros = FALSE)

Arguments

Details

This function will return all partions, or a subset, of an integer n. It makes no check to see if this is a sensible thing to do. It also does it in a lazy way in that in the restricted case it generates all partitions and then only returns those that satistfy the length constraint. Users are advised to check how many partitions are possible using partition number function which is implemented the P function in the partions package. Having said this P(50) is approximately 200 thousand, and P(100) around 190 million, so the function should work well for smallish n.

Value

A list with each list element representing an integer partition

Note

This function does not warn the user that the requested set of partitions may be very large. In addition, all working is handled entirely in memory, and so this may cause it to crash if the request is execeptionally large.

Author(s)

Jerome Kelleher (algorithm and Python version) and James M. Curran (C++ version/R interface)

References

Kelleher, J. (2005), Encoding Partitions As Ascending Compositions, PhD thesis, University College Cork.

Kelleher, J. and O'Sullivan, B. (2009), Generating All Partitions: A Comparison Of Two Encodings, https://arxiv.org/abs/0909.2331.

Kelleher, J. (2010) Generating Integer Partitions,https://jeromekelleher.net/tag/integer-partitions.html.

Examples

## a small numeric example with all 11 partitions of 6
genComp(6)

## a small example with the integer partitions of 6 of length 3 with empty partitions added
genComp(6, 3, TRUE)

## a larger example - 627 partions of 20, but restricted to those of length 3 or smaller
genComp(20, 3)

Initialise the permutation object

Description

This function initialises the permutation object. It must be called before nextPerm can be called

Usage

initMC(x)

Arguments

Value

a object of class mc which is a list containing elements

Author(s)

James M. Curran

See Also

nextPerm

Examples

x = c(1,1,2,2)
m1 = initMC(x)
m1

## a non-integer example

x = rep(letters[1:4],c(2,1,2,2))
m2 = initMC(x)
m2

Calculate multinomial coefficients

Description

This function calculates the number of permutations of a multiset, this being the multinomial coefficient. If a set X contains k unique elements x_1, x_2, \ldots, x_k with associate counts (or multiplicities) of n_1, n_2, \ldots, n_k, then this function returns

\frac{n!}{n_1!n_2!\ldots n_k!}

where n = \sum_{i=1}{k}n_i.

Usage

multinom(x, counts = FALSE, useDouble = FALSE)

Arguments

Details

multinom depends on C++ code written by Dave Barber which can be found at http://tamivox.org/dave/multinomial/code.html. The code may require the STL algorithm library to be included in order to compile it.

Value

A single integer representing the multinomial coefficient for the given multiset, or given set of multiplicities.

Author(s)

James M. Curran, Dave Barber

References

http://tamivox.org/dave/multinomial/code.html

Examples

## An example with a multiset X = (a,a,a,b,b,c)
## There are 3 a s, 2 b s and 1 c, so the answer should be
## (3+2+1)!/(3!2!1!) = 6!/3!2!1! = 60
x = rep(letters[1:3],3:1)
multinom(x)

## in this example x is a vector of counts
## the answer should be the same as above as x = c(3,2,1)
x = rep(letters[1:3],3:1)
x = as.vector(table(x)) #coerce x into a vector of counts
multinom(x, counts = TRUE)


## An example of integer overflow. x is a vector of counts
## c(12,11,8,8,6,5). The true answer from Maple is
## 11,324,718,121,789,252,764,532,876,767,840,000
## The error in the integer based answer is obvious.
## The error using floating point is not, but from Maple is
## 0.705057123232160000e+10
## Thanks to Lev Dashevskiy for calling my attention to this.
## Not run: x = c(12,11,8,8,6,5)
multinom(x, counts = TRUE, useDouble = FALSE)
multinom(x, counts = TRUE, useDouble = TRUE)

## End(Not run)

Return the next permutation of the multiset

Description

This function returns the next permuation of the multiset if there is one. initMC called before nextPerm can be called.

Usage

nextPerm(mcObj)

Arguments

Value

either a vector with the next permutation of the multiset or FALSE when all permutations have been returned

Author(s)

James M. Curran

See Also

nextPerm

Examples

x = c(1,1,2,2)
m1 = initMC(x)

for(i in 1:6){
  cat(paste(paste(nextPerm(m1),collapse=","),"\n"))
}

## an example with letters
x = letters[1:4]
m2 = initMC(x)
nextPerm(m2)
nextPerm(m2)
## and so on