[comment {-*- tcl -*- doctools manpage}] [manpage_begin math::combinatorics n 2.0] [moddesc {Tcl Math Library}] [titledesc {Combinatorial functions in the Tcl Math Library}] [category Mathematics] [require Tcl 8.2] [require math [opt 1.2.3]] [require Tcl 8.6] [require TclOO] [require math::combinatorics [opt 2.0]] [description] [para] The [package math] package contains implementations of several functions useful in combinatorial problems. The [package 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 [uri http://mathworld.wolfram.com {MathWorld website}] [section COMMANDS] [list_begin definitions] [call [cmd ::math::ln_Gamma] [arg z]] Returns the natural logarithm of the Gamma function for the argument [arg z]. [para] The Gamma function is defined as the improper integral from zero to positive infinity of [example { t**(x-1)*exp(-t) dt }] [para] The approximation used in the Tcl Math Library is from Lanczos, [emph {ISIAM J. Numerical Analysis, series B,}] volume 1, p. 86. For "[var 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 when [example { exp( ln_Gamma( x) ) }] is computed is expected to be precise to better than nine significant figures. [call [cmd ::math::factorial] [arg x]] Returns the factorial of the argument [arg x]. [para] For integer [arg x], 0 <= [arg x] <= 12, an exact integer result is returned. [para] For integer [arg x], 13 <= [arg x] <= 21, an exact floating-point result is returned on machines with IEEE floating point. [para] For integer [arg x], 22 <= [arg x] <= 170, the result is exact to 1 ULP. [para] For real [arg x], [arg x] >= 0, the result is approximated by computing [term Gamma(x+1)] using the [cmd ::math::ln_Gamma] function, and the result is expected to be precise to better than nine significant figures. [para] It is an error to present [arg x] <= -1 or [arg x] > 170, or a value of [arg x] that is not numeric. [call [cmd ::math::choose] [arg {n k}]] Returns the binomial coefficient [term {C(n, k)}] [example { 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. [para] Integer results are exact up to at least [arg n] = 34. Floating point results are precise to better than nine significant figures. [call [cmd ::math::Beta] [arg {z w}]] Returns the Beta function of the parameters [arg z] and [arg w]. [example { 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 [arg w] and [arg z] are both at least 1. [call [cmd ::math::combinatorics::permutations] [arg 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. [list_begin arguments] [arg_def int n] The number of items to be permuted. [list_end] [call [cmd ::math::combinatorics::variations] [arg n] [arg k]] Return the number of variations k items selected from the total of n items. The order of the items is taken into account. [list_begin arguments] [arg_def int n] The number of items to be selected from. [arg_def int k] The number of items to be selected in each variation. [list_end] [call [cmd ::math::combinatorics::combinations] [arg n] [arg k]] Return the number of combinations of k items selected from the total of n items. The order of the items is not important. [list_begin arguments] [arg_def int n] The number of items to be selected from. [arg_def int k] The number of items to be selected in each combination. [list_end] [call [cmd ::math::combinatorics::derangements] [arg n]] Return the number of derangements of n items. A derangement is a permutation where each item is displaced from the original position. [list_begin arguments] [arg_def int n] The number of items to be rearranged. [list_end] [call [cmd ::math::combinatorics::catalan] [arg n]] Return the n'th Catalan number. The number n is expected to be 1 or larger. These numbers occur in various combinatorial problems. [list_begin arguments] [arg_def int n] The index of the Catalan number [list_end] [call [cmd ::math::combinatorics::firstStirling] [arg n] [arg m]] Calculate a Stirling number of the first kind (signed version, m cycles in a permutation of n items) [list_begin arguments] [arg_def int n] Number of items [arg_def int m] Number of cycles [list_end] [call [cmd ::math::combinatorics::secondStirling] [arg n] [arg m]] Calculate a Stirling number of the second kind (m non-empty subsets from n items) [list_begin arguments] [arg_def int n] Number of items [arg_def int m] Number of subsets [list_end] [call [cmd ::math::combinatorics::partitionP] [arg n]] Calculate the number of ways an integer n can be written as the sum of positive integers. [list_begin arguments] [arg_def int n] Number in question [list_end] [call [cmd ::math::combinatorics::list-permutations] [arg n]] Return the list of permutations of the numbers 0, ..., n-1. [list_begin arguments] [arg_def int n] The number of items to be permuted. [list_end] [call [cmd ::math::combinatorics::list-variations] [arg n] [arg 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. [list_begin arguments] [arg_def int n] The number of items to be selected from. [arg_def int k] The number of items to be selected in each variation. [list_end] [call [cmd ::math::combinatorics::list-combinations] [arg n] [arg k]] Return the list of combinations of k numbers selected from the numbers 0, ..., n-1. The order of the items is ignored. [list_begin arguments] [arg_def int n] The number of items to be selected from. [arg_def int k] The number of items to be selected in each combination. [list_end] [call [cmd ::math::combinatorics::list-derangements] [arg n]] Return the list of derangements of the numbers 0, ..., n-1. [list_begin arguments] [arg_def int n] The number of items to be rearranged. [list_end] [call [cmd ::math::combinatorics::list-powerset] [arg n]] Return the list of all subsets of the numbers 0, ..., n-1. [list_begin arguments] [arg_def int n] The number of items to be rearranged. [list_end] [call [cmd ::math::combinatorics::permutationObj] new/create NAME [arg n]] Create a TclOO object for returning permutations one by one. If the last permutation has been reached an empty list is returned. [list_begin arguments] [arg_def int n] The number of items to be rearranged. [list_end] [call [cmd \$perm] next] Return the next permutation of n objects. [call [cmd \$perm] reset] Reset the object, so that the command [term next] returns the complete list again. [call [cmd \$perm] setElements [arg elements]] Register a list of items to be permuted, using the [term nextElements] command. [list_begin arguments] [arg_def list elements] The list of n items that will be permuted. [list_end] [call [cmd \$perm] setElements] Return the next permulation of the registered items. [call [cmd ::math::combinatorics::combinationObj] new/create NAME [arg n] [arg k]] Create a TclOO object for returning combinations one by one. If the last combination has been reached an empty list is returned. [list_begin arguments] [arg_def int n] The number of items to be rearranged. [list_end] [call [cmd \$combin] next] Return the next combination of n objects. [call [cmd \$combin] reset] Reset the object, so that the command [term next] returns the complete list again. [call [cmd \$combin] setElements [arg elements]] Register a list of items to be permuted, using the [term nextElements] command. [list_begin arguments] [arg_def list elements] The list of n items that will be permuted. [list_end] [call [cmd \$combin] setElements] Return the next combination of the registered items. [list_end] [vset CATEGORY math] [include ../common-text/feedback.inc] [manpage_end]