# combinatorics - Man Page

Combinatorial functions in the Tcl Math Library

## Synopsis

`package require `

**Tcl 8.2**

`package require `

**math ?1.2.3?**

`package require `

**Tcl 8.6**

`package require `

**TclOO**

`package require `

**math::combinatorics ?2.0?**

**::math::ln_Gamma** *z*

**::math::factorial** *x*

**::math::choose** *n k*

**::math::Beta** *z w*

**::math::combinatorics::permutations** *n*

**::math::combinatorics::variations** *n k*

**::math::combinatorics::combinations** *n k*

**::math::combinatorics::derangements** *n*

**::math::combinatorics::catalan** *n*

**::math::combinatorics::firstStirling** *n m*

**::math::combinatorics::secondStirling** *n m*

**::math::combinatorics::partitionP** *n*

**::math::combinatorics::list-permutations** *n*

**::math::combinatorics::list-variations** *n k*

**::math::combinatorics::list-combinations** *n k*

**::math::combinatorics::list-derangements** *n*

**::math::combinatorics::list-powerset** *n*

**::math::combinatorics::permutationObj** new/create NAME *n*

**$perm** next

**$perm** reset

**$perm** setElements *elements*

**$perm** setElements

**::math::combinatorics::combinationObj** new/create NAME *n k*

**$combin** next

**$combin** reset

**$combin** setElements *elements*

**$combin** setElements

## Description

The **math** package contains implementations of several functions useful in combinatorial problems. The **math::combinatorics** extends the collections based on features in Tcl 8.6. Note: the meaning of the partitionP function, Catalan and Stirling numbers is explained on the *MathWorld website* [http://mathworld.wolfram.com]

## Commands

**::math::ln_Gamma***z*Returns the natural logarithm of the Gamma function for the argument

*z*.The Gamma function is defined as the improper integral from zero to positive infinity of

t**(x-1)*exp(-t) dt

The approximation used in the Tcl Math Library is from Lanczos,

*ISIAM J. Numerical Analysis, series B,*volume 1, p. 86. For "**x**> 1", the absolute error of the result is claimed to be smaller than 5.5*10**-10 -- that is, the resulting value of Gamma whenexp( ln_Gamma( x) )

is computed is expected to be precise to better than nine significant figures.

**::math::factorial***x*Returns the factorial of the argument

*x*.For integer

*x*, 0 <=*x*<= 12, an exact integer result is returned.For integer

*x*, 13 <=*x*<= 21, an exact floating-point result is returned on machines with IEEE floating point.For integer

*x*, 22 <=*x*<= 170, the result is exact to 1 ULP.For real

*x*,*x*>= 0, the result is approximated by computing*Gamma(x+1)*using the**::math::ln_Gamma**function, and the result is expected to be precise to better than nine significant figures.It is an error to present

*x*<= -1 or*x*> 170, or a value of*x*that is not numeric.**::math::choose***n k*Returns the binomial coefficient

*C(n, k)*C(n,k) = n! / k! (n-k)!

If both parameters are integers and the result fits in 32 bits, the result is rounded to an integer.

Integer results are exact up to at least

*n*= 34. Floating point results are precise to better than nine significant figures.**::math::Beta***z w*Returns the Beta function of the parameters

*z*and*w*.Beta(z,w) = Beta(w,z) = Gamma(z) * Gamma(w) / Gamma(z+w)

Results are returned as a floating point number precise to better than nine significant digits provided that

*w*and*z*are both at least 1.**::math::combinatorics::permutations***n*Return the number of permutations of n items. The returned number is always an integer, it is not limited by the range of 32-or 64-bits integers using the arbitrary precision integers available in Tcl 8.5 and later.

- int
*n* The number of items to be permuted.

- int
**::math::combinatorics::variations***n k*Return the number of variations k items selected from the total of n items. The order of the items is taken into account.

- int
*n* The number of items to be selected from.

- int
*k* The number of items to be selected in each variation.

- int
**::math::combinatorics::combinations***n k*Return the number of combinations of k items selected from the total of n items. The order of the items is not important.

- int
*n* The number of items to be selected from.

- int
*k* The number of items to be selected in each combination.

- int
**::math::combinatorics::derangements***n*Return the number of derangements of n items. A derangement is a permutation where each item is displaced from the original position.

- int
*n* The number of items to be rearranged.

- int
**::math::combinatorics::catalan***n*Return the n'th Catalan number. The number n is expected to be 1 or larger. These numbers occur in various combinatorial problems.

- int
*n* The index of the Catalan number

- int
**::math::combinatorics::firstStirling***n m*Calculate a Stirling number of the first kind (signed version, m cycles in a permutation of n items)

- int
*n* Number of items

- int
*m* Number of cycles

- int
**::math::combinatorics::secondStirling***n m*Calculate a Stirling number of the second kind (m non-empty subsets from n items)

- int
*n* Number of items

- int
*m* Number of subsets

- int
**::math::combinatorics::partitionP***n*Calculate the number of ways an integer n can be written as the sum of positive integers.

- int
*n* Number in question

- int
**::math::combinatorics::list-permutations***n*Return the list of permutations of the numbers 0, ..., n-1.

- int
*n* The number of items to be permuted.

- int
**::math::combinatorics::list-variations***n k*Return the list of variations of k numbers selected from the numbers 0, ..., n-1. The order of the items is taken into account.

- int
*n* The number of items to be selected from.

- int
*k* The number of items to be selected in each variation.

- int
**::math::combinatorics::list-combinations***n k*Return the list of combinations of k numbers selected from the numbers 0, ..., n-1. The order of the items is ignored.

- int
*n* The number of items to be selected from.

- int
*k* The number of items to be selected in each combination.

- int
**::math::combinatorics::list-derangements***n*Return the list of derangements of the numbers 0, ..., n-1.

- int
*n* The number of items to be rearranged.

- int
**::math::combinatorics::list-powerset***n*Return the list of all subsets of the numbers 0, ..., n-1.

- int
*n* The number of items to be rearranged.

- int
**::math::combinatorics::permutationObj**new/create NAME*n*Create a TclOO object for returning permutations one by one. If the last permutation has been reached an empty list is returned.

- int
*n* The number of items to be rearranged.

- int
**$perm**nextReturn the next permutation of n objects.

**$perm**resetReset the object, so that the command

*next*returns the complete list again.**$perm**setElements*elements*Register a list of items to be permuted, using the

*nextElements*command.- list
*elements* The list of n items that will be permuted.

- list
**$perm**setElementsReturn the next permulation of the registered items.

**::math::combinatorics::combinationObj**new/create NAME*n k*Create a TclOO object for returning combinations one by one. If the last combination has been reached an empty list is returned.

- int
*n* The number of items to be rearranged.

- int
**$combin**nextReturn the next combination of n objects.

**$combin**resetReset the object, so that the command

*next*returns the complete list again.**$combin**setElements*elements*Register a list of items to be permuted, using the

*nextElements*command.- list
*elements* The list of n items that will be permuted.

- list
**$combin**setElementsReturn the next combination of the registered items.

## Bugs, Ideas, Feedback

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category *math* of the *Tcllib Trackers* [http://core.tcl.tk/tcllib/reportlist]. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide *unified diffs*, i.e the output of **diff -u**.

Note further that *attachments* are strongly preferred over inlined patches. Attachments can be made by going to the **Edit** form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.

## Category

Mathematics