'\"
'\" Generated from file 'combinatorics\&.man' by tcllib/doctools with format 'nroff'
'\"
.TH "math::combinatorics" 3tcl 2\&.0 tcllib "Tcl Math Library"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,
.\"	and indent is equivalent to second arg of .IP (shouldn't ever be
.\"	needed;  use .AS below instead)
.\"
.\" .AS ?type? ?name?
.\"	Give maximum sizes of arguments for setting tab stops.  Type and
.\"	name are examples of largest possible arguments that will be passed
.\"	to .AP later.  If args are omitted, default tab stops are used.
.\"
.\" .BS
.\"	Start box enclosure.  From here until next .BE, everything will be
.\"	enclosed in one large box.
.\"
.\" .BE
.\"	End of box enclosure.
.\"
.\" .CS
.\"	Begin code excerpt.
.\"
.\" .CE
.\"	End code excerpt.
.\"
.\" .VS ?version? ?br?
.\"	Begin vertical sidebar, for use in marking newly-changed parts
.\"	of man pages.  The first argument is ignored and used for recording
.\"	the version when the .VS was added, so that the sidebars can be
.\"	found and removed when they reach a certain age.  If another argument
.\"	is present, then a line break is forced before starting the sidebar.
.\"
.\" .VE
.\"	End of vertical sidebar.
.\"
.\" .DS
.\"	Begin an indented unfilled display.
.\"
.\" .DE
.\"	End of indented unfilled display.
.\"
.\" .SO ?manpage?
.\"	Start of list of standard options for a Tk widget. The manpage
.\"	argument defines where to look up the standard options; if
.\"	omitted, defaults to "options". The options follow on successive
.\"	lines, in three columns separated by tabs.
.\"
.\" .SE
.\"	End of list of standard options for a Tk widget.
.\"
.\" .OP cmdName dbName dbClass
.\"	Start of description of a specific option.  cmdName gives the
.\"	option's name as specified in the class command, dbName gives
.\"	the option's name in the option database, and dbClass gives
.\"	the option's class in the option database.
.\"
.\" .UL arg1 arg2
.\"	Print arg1 underlined, then print arg2 normally.
.\"
.\" .QW arg1 ?arg2?
.\"	Print arg1 in quotes, then arg2 normally (for trailing punctuation).
.\"
.\" .PQ arg1 ?arg2?
.\"	Print an open parenthesis, arg1 in quotes, then arg2 normally
.\"	(for trailing punctuation) and then a closing parenthesis.
.\"
.\"	# Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
.if t .wh -1.3i ^B
.nr ^l \n(.l
.ad b
.\"	# Start an argument description
.de AP
.ie !"\\$4"" .TP \\$4
.el \{\
.   ie !"\\$2"" .TP \\n()Cu
.   el          .TP 15
.\}
.ta \\n()Au \\n()Bu
.ie !"\\$3"" \{\
\&\\$1 \\fI\\$2\\fP (\\$3)
.\".b
.\}
.el \{\
.br
.ie !"\\$2"" \{\
\&\\$1	\\fI\\$2\\fP
.\}
.el \{\
\&\\fI\\$1\\fP
.\}
.\}
..
.\"	# define tabbing values for .AP
.de AS
.nr )A 10n
.if !"\\$1"" .nr )A \\w'\\$1'u+3n
.nr )B \\n()Au+15n
.\"
.if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
.nr )C \\n()Bu+\\w'(in/out)'u+2n
..
.AS Tcl_Interp Tcl_CreateInterp in/out
.\"	# BS - start boxed text
.\"	# ^y = starting y location
.\"	# ^b = 1
.de BS
.br
.mk ^y
.nr ^b 1u
.if n .nf
.if n .ti 0
.if n \l'\\n(.lu\(ul'
.if n .fi
..
.\"	# BE - end boxed text (draw box now)
.de BE
.nf
.ti 0
.mk ^t
.ie n \l'\\n(^lu\(ul'
.el \{\
.\"	Draw four-sided box normally, but don't draw top of
.\"	box if the box started on an earlier page.
.ie !\\n(^b-1 \{\
\h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.el \}\
\h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.\}
.fi
.br
.nr ^b 0
..
.\"	# VS - start vertical sidebar
.\"	# ^Y = starting y location
.\"	# ^v = 1 (for troff;  for nroff this doesn't matter)
.de VS
.if !"\\$2"" .br
.mk ^Y
.ie n 'mc \s12\(br\s0
.el .nr ^v 1u
..
.\"	# VE - end of vertical sidebar
.de VE
.ie n 'mc
.el \{\
.ev 2
.nf
.ti 0
.mk ^t
\h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
.sp
-1
.fi
.ev
.\}
.nr ^v 0
..
.\"	# Special macro to handle page bottom:  finish off current
.\"	# box/sidebar if in box/sidebar mode, then invoked standard
.\"	# page bottom macro.
.de ^B
.ev 2
'ti 0
'nf
.mk ^t
.if \\n(^b \{\
.\"	Draw three-sided box if this is the box's first page,
.\"	draw two sides but no top otherwise.
.ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.\}
.if \\n(^v \{\
.nr ^x \\n(^tu+1v-\\n(^Yu
\kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
.\}
.bp
'fi
.ev
.if \\n(^b \{\
.mk ^y
.nr ^b 2
.\}
.if \\n(^v \{\
.mk ^Y
.\}
..
.\"	# DS - begin display
.de DS
.RS
.nf
.sp
..
.\"	# DE - end display
.de DE
.fi
.RE
.sp
..
.\"	# SO - start of list of standard options
.de SO
'ie '\\$1'' .ds So \\fBoptions\\fR
'el .ds So \\fB\\$1\\fR
.SH "STANDARD OPTIONS"
.LP
.nf
.ta 5.5c 11c
.ft B
..
.\"	# SE - end of list of standard options
.de SE
.fi
.ft R
.LP
See the \\*(So manual entry for details on the standard options.
..
.\"	# OP - start of full description for a single option
.de OP
.LP
.nf
.ta 4c
Command-Line Name:	\\fB\\$1\\fR
Database Name:	\\fB\\$2\\fR
Database Class:	\\fB\\$3\\fR
.fi
.IP
..
.\"	# CS - begin code excerpt
.de CS
.RS
.nf
.ta .25i .5i .75i 1i
..
.\"	# CE - end code excerpt
.de CE
.fi
.RE
..
.\"	# UL - underline word
.de UL
\\$1\l'|0\(ul'\\$2
..
.\"	# QW - apply quotation marks to word
.de QW
.ie '\\*(lq'"' ``\\$1''\\$2
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\$2
..
.\"	# PQ - apply parens and quotation marks to word
.de PQ
.ie '\\*(lq'"' (``\\$1''\\$2)\\$3
.\"" fix emacs highlighting
.el (\\*(lq\\$1\\*(rq\\$2)\\$3
..
.\"	# QR - quoted range
.de QR
.ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
..
.\"	# MT - "empty" string
.de MT
.QW ""
..
.BS
.SH NAME
math::combinatorics \- Combinatorial functions in the Tcl Math Library
.SH SYNOPSIS
package require \fBTcl  8\&.2\fR
.sp
package require \fBmath  ?1\&.2\&.3?\fR
.sp
package require \fBTcl  8\&.6\fR
.sp
package require \fBTclOO \fR
.sp
package require \fBmath::combinatorics  ?2\&.0?\fR
.sp
\fB::math::ln_Gamma\fR \fIz\fR
.sp
\fB::math::factorial\fR \fIx\fR
.sp
\fB::math::choose\fR \fIn k\fR
.sp
\fB::math::Beta\fR \fIz w\fR
.sp
\fB::math::combinatorics::permutations\fR \fIn\fR
.sp
\fB::math::combinatorics::variations\fR \fIn\fR \fIk\fR
.sp
\fB::math::combinatorics::combinations\fR \fIn\fR \fIk\fR
.sp
\fB::math::combinatorics::derangements\fR \fIn\fR
.sp
\fB::math::combinatorics::catalan\fR \fIn\fR
.sp
\fB::math::combinatorics::firstStirling\fR \fIn\fR \fIm\fR
.sp
\fB::math::combinatorics::secondStirling\fR \fIn\fR \fIm\fR
.sp
\fB::math::combinatorics::partitionP\fR \fIn\fR
.sp
\fB::math::combinatorics::list-permutations\fR \fIn\fR
.sp
\fB::math::combinatorics::list-variations\fR \fIn\fR \fIk\fR
.sp
\fB::math::combinatorics::list-combinations\fR \fIn\fR \fIk\fR
.sp
\fB::math::combinatorics::list-derangements\fR \fIn\fR
.sp
\fB::math::combinatorics::list-powerset\fR \fIn\fR
.sp
\fB::math::combinatorics::permutationObj\fR new/create NAME \fIn\fR
.sp
\fB$perm\fR next
.sp
\fB$perm\fR reset
.sp
\fB$perm\fR setElements \fIelements\fR
.sp
\fB$perm\fR setElements
.sp
\fB::math::combinatorics::combinationObj\fR new/create NAME \fIn\fR \fIk\fR
.sp
\fB$combin\fR next
.sp
\fB$combin\fR reset
.sp
\fB$combin\fR setElements \fIelements\fR
.sp
\fB$combin\fR setElements
.sp
.BE
.SH DESCRIPTION
.PP
The \fBmath\fR package contains implementations of several
functions useful in combinatorial problems\&. The \fBmath::combinatorics\fR
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
\fIMathWorld website\fR [http://mathworld\&.wolfram\&.com]
.SH COMMANDS
.TP
\fB::math::ln_Gamma\fR \fIz\fR
Returns the natural logarithm of the Gamma function for the argument
\fIz\fR\&.
.sp
The Gamma function is defined as the improper integral from zero to
positive infinity of
.CS


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

.CE
.sp
The approximation used in the Tcl Math Library is from Lanczos,
\fIISIAM J\&. Numerical Analysis, series B,\fR volume 1, p\&. 86\&.
For "\fBx\fR > 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
.CS


  exp( ln_Gamma( x) )

.CE
.IP
is computed is expected to be precise to better than nine significant
figures\&.
.TP
\fB::math::factorial\fR \fIx\fR
Returns the factorial of the argument \fIx\fR\&.
.sp
For integer \fIx\fR, 0 <= \fIx\fR <= 12, an exact integer result is
returned\&.
.sp
For integer \fIx\fR, 13 <= \fIx\fR <= 21, an exact floating-point
result is returned on machines with IEEE floating point\&.
.sp
For integer \fIx\fR, 22 <= \fIx\fR <= 170, the result is exact to 1
ULP\&.
.sp
For real \fIx\fR, \fIx\fR >= 0, the result is approximated by
computing \fIGamma(x+1)\fR using the \fB::math::ln_Gamma\fR
function, and the result is expected to be precise to better than nine
significant figures\&.
.sp
It is an error to present \fIx\fR <= -1 or \fIx\fR > 170, or a value
of \fIx\fR that is not numeric\&.
.TP
\fB::math::choose\fR \fIn k\fR
Returns the binomial coefficient \fIC(n, k)\fR
.CS


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

.CE
.IP
If both parameters are integers and the result fits in 32 bits, the
result is rounded to an integer\&.
.sp
Integer results are exact up to at least \fIn\fR = 34\&.  Floating point
results are precise to better than nine significant figures\&.
.TP
\fB::math::Beta\fR \fIz w\fR
Returns the Beta function of the parameters \fIz\fR and \fIw\fR\&.
.CS


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

.CE
.IP
Results are returned as a floating point number precise to better than
nine significant digits provided that \fIw\fR and \fIz\fR are both at
least 1\&.
.TP
\fB::math::combinatorics::permutations\fR \fIn\fR
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\&.
.RS
.TP
int \fIn\fR
The number of items to be permuted\&.
.RE
.TP
\fB::math::combinatorics::variations\fR \fIn\fR \fIk\fR
Return the number of variations k items selected from the total of n items\&.
The order of the items is taken into account\&.
.RS
.TP
int \fIn\fR
The number of items to be selected from\&.
.TP
int \fIk\fR
The number of items to be selected in each variation\&.
.RE
.TP
\fB::math::combinatorics::combinations\fR \fIn\fR \fIk\fR
Return the number of combinations of k items selected from the total of n items\&.
The order of the items is not important\&.
.RS
.TP
int \fIn\fR
The number of items to be selected from\&.
.TP
int \fIk\fR
The number of items to be selected in each combination\&.
.RE
.TP
\fB::math::combinatorics::derangements\fR \fIn\fR
Return the number of derangements of n items\&. A derangement is a permutation
where each item is displaced from the original position\&.
.RS
.TP
int \fIn\fR
The number of items to be rearranged\&.
.RE
.TP
\fB::math::combinatorics::catalan\fR \fIn\fR
Return the n'th Catalan number\&. The number n is expected to be 1 or larger\&.
These numbers occur in various combinatorial problems\&.
.RS
.TP
int \fIn\fR
The index of the Catalan number
.RE
.TP
\fB::math::combinatorics::firstStirling\fR \fIn\fR \fIm\fR
Calculate a Stirling number of the first kind
(signed version, m cycles in a permutation of n items)
.RS
.TP
int \fIn\fR
Number of items
.TP
int \fIm\fR
Number of cycles
.RE
.TP
\fB::math::combinatorics::secondStirling\fR \fIn\fR \fIm\fR
Calculate a Stirling number of the second kind
(m non-empty subsets from n items)
.RS
.TP
int \fIn\fR
Number of items
.TP
int \fIm\fR
Number of subsets
.RE
.TP
\fB::math::combinatorics::partitionP\fR \fIn\fR
Calculate the number of ways an integer n can be written as the sum of positive integers\&.
.RS
.TP
int \fIn\fR
Number in question
.RE
.TP
\fB::math::combinatorics::list-permutations\fR \fIn\fR
Return the list of permutations of the numbers 0, \&.\&.\&., n-1\&.
.RS
.TP
int \fIn\fR
The number of items to be permuted\&.
.RE
.TP
\fB::math::combinatorics::list-variations\fR \fIn\fR \fIk\fR
Return the list of variations of k numbers selected from the numbers 0, \&.\&.\&., n-1\&.
The order of the items is taken into account\&.
.RS
.TP
int \fIn\fR
The number of items to be selected from\&.
.TP
int \fIk\fR
The number of items to be selected in each variation\&.
.RE
.TP
\fB::math::combinatorics::list-combinations\fR \fIn\fR \fIk\fR
Return the list of combinations of k numbers selected from the numbers 0, \&.\&.\&., n-1\&.
The order of the items is ignored\&.
.RS
.TP
int \fIn\fR
The number of items to be selected from\&.
.TP
int \fIk\fR
The number of items to be selected in each combination\&.
.RE
.TP
\fB::math::combinatorics::list-derangements\fR \fIn\fR
Return the list of derangements of the numbers 0, \&.\&.\&., n-1\&.
.RS
.TP
int \fIn\fR
The number of items to be rearranged\&.
.RE
.TP
\fB::math::combinatorics::list-powerset\fR \fIn\fR
Return the list of all subsets of the numbers 0, \&.\&.\&., n-1\&.
.RS
.TP
int \fIn\fR
The number of items to be rearranged\&.
.RE
.TP
\fB::math::combinatorics::permutationObj\fR new/create NAME \fIn\fR
Create a TclOO object for returning permutations one by one\&. If the last permutation
has been reached an empty list is returned\&.
.RS
.TP
int \fIn\fR
The number of items to be rearranged\&.
.RE
.TP
\fB$perm\fR next
Return the next permutation of n objects\&.
.TP
\fB$perm\fR reset
Reset the object, so that the command \fInext\fR returns the complete list again\&.
.TP
\fB$perm\fR setElements \fIelements\fR
Register a list of items to be permuted, using the \fInextElements\fR command\&.
.RS
.TP
list \fIelements\fR
The list of n items that will be permuted\&.
.RE
.TP
\fB$perm\fR setElements
Return the next permulation of the registered items\&.
.TP
\fB::math::combinatorics::combinationObj\fR new/create NAME \fIn\fR \fIk\fR
Create a TclOO object for returning combinations one by one\&. If the last combination
has been reached an empty list is returned\&.
.RS
.TP
int \fIn\fR
The number of items to be rearranged\&.
.RE
.TP
\fB$combin\fR next
Return the next combination of n objects\&.
.TP
\fB$combin\fR reset
Reset the object, so that the command \fInext\fR returns the complete list again\&.
.TP
\fB$combin\fR setElements \fIelements\fR
Register a list of items to be permuted, using the \fInextElements\fR command\&.
.RS
.TP
list \fIelements\fR
The list of n items that will be permuted\&.
.RE
.TP
\fB$combin\fR setElements
Return the next combination of the registered items\&.
.PP
.SH "BUGS, IDEAS, FEEDBACK"
This document, and the package it describes, will undoubtedly contain
bugs and other problems\&.
Please report such in the category \fImath\fR of the
\fITcllib Trackers\fR [http://core\&.tcl\&.tk/tcllib/reportlist]\&.
Please also report any ideas for enhancements you may have for either
package and/or documentation\&.
.PP
When proposing code changes, please provide \fIunified diffs\fR,
i\&.e the output of \fBdiff -u\fR\&.
.PP
Note further that \fIattachments\fR are strongly preferred over
inlined patches\&. Attachments can be made by going to the \fBEdit\fR
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar\&.
.SH CATEGORY
Mathematics