Movatterモバイル変換

Compute the Bell numbers

Description

This function computes the Bell numbers, which is the summ of Stirlingnumbers of the second kind,S(n, k), overk = 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 distinctobjects 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 whichdefines

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

fork > 0with the inital conditionsS(0, 0) = 1 andS(n, 0) = S(0, n) =0. Ifn andn have different lengths thenexpand.gridis 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 checkto see if this is a sensible thing to do. Users are advised to check howmany permutations are possible using themultinom function in thispackage.

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 ofpermutations may be very large. In addition, all working is handled entirelyin memory, and so this may cause it to crash if the request isexeceptionally large.

Author(s)

James M. Curran

See Also

initMC,multinom

Examples

## a small numeric example with 6 permuationsx = c(1,1,2,2)m = initMC(x)allPerm(m)## a large character example - 60 possibilitiesx = rep(letters[1:3], 3:1)multinom(x) ## calculate the number of permutationsm = 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 theinteger partitions of an integer n. The method works by consideringcompositions 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. Itmakes no check to see if this is a sensible thing to do. It also does it ina lazy way in that in the restricted case it generates all partitions andthen only returns those that satistfy the length constraint. Users areadvised to check how many partitions are possible using partition numberfunction which is implemented theP function in thepartionspackage. 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 ofpartitions may be very large. In addition, all working is handled entirelyin memory, and so this may cause it to crash if the request isexeceptionally large.

Author(s)

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

References

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

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

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

Examples

## a small numeric example with all 11 partitions of 6genComp(6)## a small example with the integer partitions of 6 of length 3 with empty partitions addedgenComp(6, 3, TRUE)## a larger example - 627 partions of 20, but restricted to those of length 3 or smallergenComp(20, 3)

Initialise the permutation object

Description

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

Usage

initMC(x)

Arguments

Value

a object of classmc 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 examplex = 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, thisbeing the multinomial coefficient. If a setX containsk uniqueelementsx_1, x_2, \ldots, x_k with associate counts (ormultiplicities) ofn_1, n_2, \ldots, n_k, then this function returns

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

wheren= \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 athttp://tamivox.org/dave/multinomial/code.html. The code may requirethe STL algorithm library to be included in order to compile it.

Value

A single integer representing the multinomial coefficient for thegiven 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! = 60x = 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 countsmultinom(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 beforenextPerm can be called.

Usage

nextPerm(mcObj)

Arguments

Value

either a vector with the next permutation of the multiset orFALSE 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 lettersx = letters[1:4]m2 = initMC(x)nextPerm(m2)nextPerm(m2)## and so on