<p>This chapter describes functions that deal with combinatorics. We mainly concentrate on two areas. One is about <em>selections</em>, that is the ways one can select elements from a set. The other is about <em>partitions</em>, that is the ways one can partition a set into the union of pairwise disjoint subsets.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Factorial</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the <em>factorial</em> <span class="SimpleMath">n!</span> of the positive integer <var class="Arg">n</var>, which is defined as the product <span class="SimpleMath">1 ⋅ 2 ⋅ 3 ⋯ n</span>.</p>
<p><span class="SimpleMath">n!</span> is the number of permutations of a set of <span class="SimpleMath">n</span> elements. <span class="SimpleMath">1 / n!</span> is the coefficient of <span class="SimpleMath">x^n</span> in the formal series <span class="SimpleMath">exp(x)</span>, which is the generating function for factorial.</p>
<p><code class="func">PermutationsList</code> (<a href="chap16.html#X7B0143FB83F359B7"><spanclass="RefLink">16.2-12</span></a>) computes the set of all permutations of a list.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Binomial</code>( <var class="Arg">n</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the <em>binomial coefficient</em> <span class="SimpleMath">{n choose k}</span> of integers <var class="Arg">n</var> and <var class="Arg">k</var>. This is defined by the conditions <span class="SimpleMath">{n choose k} = 0</span> for <span class="SimpleMath">k < 0</span>, <span class="SimpleMath">{0 choose k} = 0</span> for <span class="SimpleMath">k ≠ 0</span>, <span class="SimpleMath">{0 choose 0} = 1</span> and the relation <span class="SimpleMath">{n choose k} = {n-1 choose k} + {n-1 choose k-1}</span> for all <span class="SimpleMath">n</span> and <span class="SimpleMath">k</span>.</p>
<p>There are many ways of describing this function. For example, if <span class="SimpleMath">n ≥ 0</span> and <span class="SimpleMath">0 ≤ k ≤ n</span>, then <span class="SimpleMath">{n choose k} = n! / (k! (n-k)!)</span> and for <span class="SimpleMath">n < 0</span> and <span class="SimpleMath">k ≥ 0</span> we have <span class="SimpleMath">{n choose k} = (-1)^k {-n+k-1 choose k}</span>.</p>
<p>If <span class="SimpleMath">n ≥ 0</span> then <span class="SimpleMath">{n choose k}</span> is the number of subsets with <span class="SimpleMath">k</span> elements of a set with <span class="SimpleMath">n</span> elements. Also, <span class="SimpleMath">{n choose k}</span> is the coefficient of <span class="SimpleMath">x^k</span> in the polynomial <span class="SimpleMath">(x + 1)^n</span>, which is the generating function for <span class="SimpleMath">{n choose .}</span>, hence the name.</p>
<p><code class="func">NrCombinations</code> (<a href="chap16.html#X82A6E98C85714FD0"><span class="RefLink">16.2-3</span></a>) is the generalization of <code class="func">Binomial</code> for multisets. <code class="func">Combinations</code> (<a href="chap16.html#X8770F16D794C0ADB"><span class="RefLink">16.2-1</span></a>) computes the set of all combinations of a multiset.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Bell</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the <em>Bell number</em> <span class="SimpleMath">B(n)</span>. The Bell numbers are defined by <span class="SimpleMath">B(0) = 1</span> and the recurrence <span class="SimpleMath">B(n+1) = ∑_{k = 0}^n {n choose k} B(k)</span>.</p>
<p><span class="SimpleMath">B(n)</span> is the number of ways to partition a set of <var class="Arg">n</var> elements into pairwise disjoint nonempty subsets (see <code class="func">PartitionsSet</code> (<a href="chap16.html#X7A13D8DC8204525F"><span class="RefLink">16.2-16</span></a>)). This implies of course that <span class="SimpleMath">B(n) = ∑_{k = 0}^n S_2(n,k)</span> (see <code class="func">Stirling2</code> (<a href="chap16.html#X7C93E14D7BC360F0"><span class="RefLink">16.1-6</span></a>)). <span class="SimpleMath">B(n)/n!</span> is the coefficient of <span class="SimpleMath">x^n</span> in the formal series <span class="SimpleMath">exp( exp(x)-1 )</span>, which is the generating function for <span class="SimpleMath">B(n)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Bernoulli</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the <var class="Arg">n</var>-th <em>Bernoulli number</em> <span class="SimpleMath">B_n</span>, which is defined by <span class="SimpleMath">B_0 = 1</span> and <span class="SimpleMath">B_n = -∑_{k = 0}^{n-1} {n+1 choose k} B_k/(n+1)</span>.</p>
<p><span class="SimpleMath">B_n / n!</span> is the coefficient of <span class="SimpleMath">x^n</span> in the power series of <span class="SimpleMath">x / (exp(x)-1)</span>. Except for <span class="SimpleMath">B_1 = -1/2</span> the Bernoulli numbers for odd indices are zero.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Bernoulli( 4 );</span>
-1/30
<span class="GAPprompt">gap></span> <span class="GAPinput">Bernoulli( 10 );</span>
5/66
<span class="GAPprompt">gap></span> <span class="GAPinput">Bernoulli( 12 ); # there is no simple pattern in Bernoulli numbers</span>
-691/2730
<span class="GAPprompt">gap></span> <span class="GAPinput">Bernoulli( 50 ); # and they grow fairly fast</span>
495057205241079648212477525/66
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Stirling1</code>( <var class="Arg">n</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the <em>Stirling number of the first kind</em> <span class="SimpleMath">S_1(n,k)</span> of the integers <var class="Arg">n</var> and <var class="Arg">k</var>. Stirling numbers of the first kind are defined by <span class="SimpleMath">S_1(0,0) = 1</span>, <span class="SimpleMath">S_1(n,0) = S_1(0,k) = 0</span> if <span class="SimpleMath">n, k ne 0</span> and the recurrence <span class="SimpleMath">S_1(n,k) = (n-1) S_1(n-1,k) + S_1(n-1,k-1)</span>.</p>
<p><span class="SimpleMath">S_1(n,k)</span> is the number of permutations of <var class="Arg">n</var> points with <var class="Arg">k</var> cycles. Stirling numbers of the first kind appear as coefficients in the series <span class="SimpleMath">n! {x choose n} = ∑_{k = 0}^n S_1(n,k) x^k</span> which is the generating function for Stirling numbers of the first kind. Note the similarity to <span class="SimpleMath">x^n = ∑_{k = 0}^n S_2(n,k) k! {x choose k}</span> (see <code class="func">Stirling2</code> (<a href="chap16.html#X7C93E14D7BC360F0"><span class="RefLink">16.1-6</span></a>)). Also the definition of <span class="SimpleMath">S_1</span> implies <span class="SimpleMath">S_1(n,k) = S_2(-k,-n)</span> if <span class="SimpleMath">n, k < 0</span>. There are many formulae relating Stirling numbers of the first kind to Stirling numbers of the second kind, Bell numbers, and Binomial coefficients.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Stirling2</code>( <var class="Arg">n</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the <em>Stirling number of the second kind</em> <span class="SimpleMath">S_2(n,k)</span> of the integers <var class="Arg">n</var> and <var class="Arg">k</var>. Stirling numbers of the second kind are defined by <span class="SimpleMath">S_2(0,0) = 1</span>, <span class="SimpleMath">S_2(n,0) = S_2(0,k) = 0</span> if <span class="SimpleMath">n, k ne 0</span> and the recurrence <span class="SimpleMath">S_2(n,k) = k S_2(n-1,k) + S_2(n-1,k-1)</span>.</p>
<p><span class="SimpleMath">S_2(n,k)</span> is the number of ways to partition a set of <var class="Arg">n</var> elements into <var class="Arg">k</var> pairwise disjoint nonempty subsets (see <code class="func">PartitionsSet</code> (<a href="chap16.html#X7A13D8DC8204525F"><span class="RefLink">16.2-16</span></a>)). Stirling numbers of the second kind appear as coefficients in the expansion of <span class="SimpleMath">x^n = ∑_{k = 0}^n S_2(n,k) k! {x choose k}</span>. Note the similarity to <span class="SimpleMath">n! {x choose n} = ∑_{k = 0}^n S_1(n,k) x^k</span> (see <code class="func">Stirling1</code> (<a href="chap16.html#X85037456785BB33C"><span class="RefLink">16.1-5</span></a>)). Also the definition of <span class="SimpleMath">S_2</span> implies <span class="SimpleMath">S_2(n,k) = S_1(-k,-n)</span> if <span class="SimpleMath">n, k < 0</span>. There are many formulae relating Stirling numbers of the second kind to Stirling numbers of the first kind, Bell numbers, and Binomial coefficients.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Combinations</code>( <var class="Arg">mset</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all combinations of the multiset <var class="Arg">mset</var> (a list of objects which may contain the same object several times) with <var class="Arg">k</var> elements; if <var class="Arg">k</var> is not given it returns all combinations of <var class="Arg">mset</var>.</p>
<p>A <em>combination</em> of <var class="Arg">mset</var> is an unordered selection without repetitions and is represented by a sorted sublist of <var class="Arg">mset</var>. If <var class="Arg">mset</var> is a proper set, there are <span class="SimpleMath">{|<var class="Arg">mset</var>| choose <var class="Arg">k</var>}</span> (see <code class="func">Binomial</code> (<a href="chap16.html#X7A9AF5F58682819D"><span class="RefLink">16.1-2</span></a>)) combinations with <var class="Arg">k</var> elements, and the set of all combinations is just the <em>power set</em> of <var class="Arg">mset</var>, which contains all <em>subsets</em> of <var class="Arg">mset</var> and has cardinality <span class="SimpleMath">2^{|<var class="Arg">mset</var>|}</span>.</p>
<p>To loop over combinations of a larger multiset use <code class="func">IteratorOfCombinations</code> (<a href="chap16.html#X78DD5C0D81057540"><span class="RefLink">16.2-2</span></a>) which produces combinations one by one and may save a lot of memory. Another memory efficient representation of the list of all combinations is provided by <code class="func">EnumeratorOfCombinations</code> (<a href="chap16.html#X78DD5C0D81057540"><span class="RefLink">16.2-2</span></a>).</p>
<h5>16.2-2 <span class="Heading">Iterator and enumerator of combinations</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IteratorOfCombinations</code>( <var class="Arg">mset</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnumeratorOfCombinations</code>( <var class="Arg">mset</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IteratorOfCombinations</code> returns an <code class="func">Iterator</code> (<a href="chap30.html#X83ADF8287ED0668E"><span class="RefLink">30.8-1</span></a>) for combinations (see <code class="func">Combinations</code> (<a href="chap16.html#X8770F16D794C0ADB"><span class="RefLink">16.2-1</span></a>)) of the given multiset <var class="Arg">mset</var>. If a non-negative integer <var class="Arg">k</var> is given as second argument then only the combinations with <var class="Arg">k</var> entries are produced, otherwise all combinations.</p>
<p><code class="func">EnumeratorOfCombinations</code> returns an <code class="func">Enumerator</code> (<a href="chap30.html#X7EF8910F82B45EC7"><span class="RefLink">30.3-2</span></a>) of the given multiset <var class="Arg">mset</var>. Currently only a variant without second argument <var class="Arg">k</var> is implemented.</p>
<p>The ordering of combinations from these functions can be different and also different from the list returned by <code class="func">Combinations</code> (<a href="chap16.html#X8770F16D794C0ADB"><span class="RefLink">16.2-1</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Arrangements</code>( <var class="Arg">mset</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of arrangements of the multiset <var class="Arg">mset</var> that contain <var class="Arg">k</var> elements. If <var class="Arg">k</var> is not given it returns all arrangements of <var class="Arg">mset</var>.</p>
<p>An <em>arrangement</em> of <var class="Arg">mset</var> is an ordered selection without repetitions and is represented by a list that contains only elements from <var class="Arg">mset</var>, but maybe in a different order. If <var class="Arg">mset</var> is a proper set there are <span class="SimpleMath">|mset|! / (|mset|-k)!</span> (see <code class="func">Factorial</code> (<a href="chap16.html#X87665F748594BF29"><span class="RefLink">16.1-1</span></a>)) arrangements with <var class="Arg">k</var> elements.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrArrangements</code>( <var class="Arg">mset</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the number of <code class="code">Arrangements(<var class="Arg">mset</var>,<var class="Arg">k</var>)</code>.</p>
<p>As an example of arrangements of a multiset, think of the game Scrabble. Suppose you have the six characters of the word <code class="code">"settle"</code> and you have to make a four letter word. Then the possibilities are given by</p>
<p>Can you find the five proper English words, where <code class="code">"lets"</code> does not count? Note that the fact that the list returned by <code class="func">Arrangements</code> (<a href="chap16.html#X7837B3357C7566C8"><span class="RefLink">16.2-4</span></a>) is a proper set means in this example that the possibilities are listed in the same order as they appear in the dictionary.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UnorderedTuples</code>( <var class="Arg">set</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all unordered tuples of length <var class="Arg">k</var> of the set <var class="Arg">set</var>.</p>
<p>An <em>unordered tuple</em> of length <var class="Arg">k</var> of <var class="Arg">set</var> is an unordered selection with repetitions of <var class="Arg">set</var> and is represented by a sorted list of length <var class="Arg">k</var> containing elements from <var class="Arg">set</var>. There are <span class="SimpleMath">{|set| + k - 1 choose k}</span> (see <code class="func">Binomial</code> (<a href="chap16.html#X7A9AF5F58682819D"><span class="RefLink">16.1-2</span></a>)) such unordered tuples.</p>
<p>Note that the fact that <code class="func">UnorderedTuples</code> returns a set implies that the last index runs fastest. That means the first tuple contains the smallest element from <var class="Arg">set</var> <var class="Arg">k</var> times, the second tuple contains the smallest element of <var class="Arg">set</var> at all positions except at the last positions, where it contains the second smallest element from <var class="Arg">set</var> and so on.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrUnorderedTuples</code>( <var class="Arg">set</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the number of <code class="code">UnorderedTuples(<var class="Arg">set</var>,<var class="Arg">k</var>)</code>.</p>
<p>As an example for unordered tuples think of a poker-like game played with 5 dice. Then each possible hand corresponds to an unordered five-tuple from the set <span class="SimpleMath">{ 1, 2, ..., 6 }</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Tuples</code>( <var class="Arg">set</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all ordered tuples of length <var class="Arg">k</var> of the set <var class="Arg">set</var>.</p>
<p>An <em>ordered tuple</em> of length <var class="Arg">k</var> of <var class="Arg">set</var> is an ordered selection with repetition and is represented by a list of length <var class="Arg">k</var> containing elements of <var class="Arg">set</var>. There are <span class="SimpleMath">|<var class="Arg">set</var>|^<var class="Arg">k</var></span> such ordered tuples.</p>
<p>Note that the fact that <code class="func">Tuples</code> returns a set implies that the last index runs fastest. That means the first tuple contains the smallest element from <var class="Arg">set</var> <var class="Arg">k</var> times, the second tuple contains the smallest element of <var class="Arg">set</var> at all positions except at the last positions, where it contains the second smallest element from <var class="Arg">set</var> and so on.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnumeratorOfTuples</code>( <var class="Arg">set</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function is referred to as an example of enumerators that are defined by functions but are not constructed from a domain. The result is equal to that of <code class="code">Tuples( <var class="Arg">set</var>, <var class="Arg">k</var> )</code>. However, the entries are not stored physically in the list but are created/identified on demand.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IteratorOfTuples</code>( <var class="Arg">set</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For a set <var class="Arg">set</var> and a positive integer <var class="Arg">k</var>, <code class="func">IteratorOfTuples</code> returns an iterator (see <a href="chap30.html#X85A3F00985453F95"><span class="RefLink">30.8</span></a>) of the set of all ordered tuples (see <code class="func">Tuples</code> (<a href="chap16.html#X86A3CA0F7CC8C320"><span class="RefLink">16.2-8</span></a>)) of length <var class="Arg">k</var> of the set <var class="Arg">set</var>. The tuples are returned in lexicographic order.</p>
<p><code class="code">Tuples(<var class="Arg">set</var>,<var class="Arg">k</var>)</code> can also be viewed as the <var class="Arg">k</var>-fold cartesian product of <var class="Arg">set</var> (see <code class="func">Cartesian</code> (<a href="chap21.html#X7E1593B979BDF2CD"><span class="RefLink">21.20-15</span></a>)).</p>
<p>The function <code class="func">Combinations</code> (<a href="chap16.html#X8770F16D794C0ADB"><span class="RefLink">16.2-1</span></a>) computes unordered selections without repetitions, <code class="func">Arrangements</code> (<a href="chap16.html#X7837B3357C7566C8"><span class="RefLink">16.2-4</span></a>) computes ordered selections without repetitions, and finally the function <code class="func">UnorderedTuples</code> (<a href="chap16.html#X81601C6786120DDC"><span class="RefLink">16.2-6</span></a>) computes unordered selections with repetitions.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermutationsList</code>( <var class="Arg">mset</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">PermutationsList</code> returns the set of permutations of the multiset <var class="Arg">mset</var>.</p>
<p>A <em>permutation</em> is represented by a list that contains exactly the same elements as <var class="Arg">mset</var>, but possibly in different order. If <var class="Arg">mset</var> is a proper set there are <span class="SimpleMath">|<var class="Arg">mset</var>| !</span> (see <code class="func">Factorial</code> (<a href="chap16.html#X87665F748594BF29"><span class="RefLink">16.1-1</span></a>)) such permutations. Otherwise if the first elements appears <span class="SimpleMath">k_1</span> times, the second element appears <span class="SimpleMath">k_2</span> times and so on, the number of permutations is <span class="SimpleMath">|<var class="Arg">mset</var>| ! / (k_1! k_2! ...)</span>, which is sometimes called multinomial coefficient.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrPermutationsList</code>( <var class="Arg">mset</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the number of <code class="code">PermutationsList(<var class="Arg">mset</var>)</code>.</p>
<p>The function <code class="func">Arrangements</code> (<a href="chap16.html#X7837B3357C7566C8"><span class="RefLink">16.2-4</span></a>) is the generalization of <code class="func">PermutationsList</code> (<a href="chap16.html#X7B0143FB83F359B7"><span class="RefLink">16.2-12</span></a>) that allows you to specify the size of the permutations. <code class="func">Derangements</code> (<a href="chap16.html#X79C159507B2BF1C9"><span class="RefLink">16.2-14</span></a>) computes permutations that have no fixed points.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Derangements</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all derangements of the list <var class="Arg">list</var>.</p>
<p>A <em>derangement</em> is a fixpointfree permutation of <var class="Arg">list</var> and is represented by a list that contains exactly the same elements as <var class="Arg">list</var>, but in such an order that the derangement has at no position the same element as <var class="Arg">list</var>. If the list <var class="Arg">list</var> contains no element twice there are exactly <span class="SimpleMath">|<var class="Arg">list</var>|! (1/2! - 1/3! + 1/4! - ⋯ + (-1)^n / n!)</span> derangements.</p>
<p>Note that the ratio <code class="code">NrPermutationsList( [ 1 .. n ] ) / NrDerangements( [ 1 .. n ] )</code>, which is <span class="SimpleMath">n! / (n! (1/2! - 1/3! + 1/4! - ⋯ + (-1)^n / n!))</span> is an approximation for the base of the natural logarithm <span class="SimpleMath">e = 2.7182818285...</span>, which is correct to about <span class="SimpleMath">n</span> digits.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrDerangements</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the number of <code class="code">Derangements(<var class="Arg">list</var>)</code>.</p>
<p>As an example of derangements suppose that you have to send four different letters to four different people. Then a derangement corresponds to a way to send those letters such that no letter reaches the intended person.</p>
<p>The function <code class="func">PermutationsList</code> (<a href="chap16.html#X7B0143FB83F359B7"><span class="RefLink">16.2-12</span></a>) computes all permutations of a list.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PartitionsSet</code>( <var class="Arg">set</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all unordered partitions of the set <var class="Arg">set</var> into <var class="Arg">k</var> pairwise disjoint nonempty sets. If <var class="Arg">k</var> is not given it returns all unordered partitions of <var class="Arg">set</var> for all <var class="Arg">k</var>.</p>
<p>An <em>unordered partition</em> of <var class="Arg">set</var> is a set of pairwise disjoint nonempty sets with union <var class="Arg">set</var> and is represented by a sorted list of such sets. There are <span class="SimpleMath">B( |set| )</span> (see <code class="func">Bell</code> (<a href="chap16.html#X7DC5667580522BDA"><span class="RefLink">16.1-3</span></a>)) partitions of the set <var class="Arg">set</var> and <span class="SimpleMath">S_2( |set|, k )</span> (see <code class="func">Stirling2</code> (<a href="chap16.html#X7C93E14D7BC360F0"><span class="RefLink">16.1-6</span></a>)) partitions with <var class="Arg">k</var> elements.</p>
<p>Note that <code class="func">PartitionsSet</code> (<a href="chap16.html#X7A13D8DC8204525F"><span class="RefLink">16.2-16</span></a>) does currently not support multisets and that there is currently no ordered counterpart.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Partitions</code>( <var class="Arg">n</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all (unordered) partitions of the positive integer <var class="Arg">n</var> into sums with <var class="Arg">k</var> summands. If <var class="Arg">k</var> is not given it returns all unordered partitions of <var class="Arg">n</var> for all <var class="Arg">k</var>.</p>
<p>An <em>unordered partition</em> is an unordered sum <span class="SimpleMath">n = p_1 + p_2 + ⋯ + p_k</span> of positive integers and is represented by the list <span class="SimpleMath">p = [ p_1, p_2, ..., p_k ]</span>, in nonincreasing order, i.e., <span class="SimpleMath">p_1 ≥ p_2 ≥ ... ≥ p_k</span>. We write <span class="SimpleMath">p ⊢ n</span>. There are approximately <span class="SimpleMath">exp(π sqrt{2/3 n}) / (4 sqrt{3} n)</span> such partitions, use <code class="func">NrPartitions</code> (<a href="chap16.html#X86933C4F795C4EBD"><span class="RefLink">16.2-21</span></a>) to compute the precise number.</p>
<p>If you want to loop over all partitions of some larger <var class="Arg">n</var> use the more memory efficient <code class="func">IteratorOfPartitions</code> (<a href="chap16.html#X8793AEBD7E529E1D"><span class="RefLink">16.2-19</span></a>).</p>
<p>It is possible to associate with every partition of the integer <var class="Arg">n</var> a conjugacy class of permutations in the symmetric group on <var class="Arg">n</var> points and vice versa. Therefore <span class="SimpleMath">p(n) :=</span><code class="code">NrPartitions</code><span class="SimpleMath">(n)</span> is the number of conjugacy classes of the symmetric group on <var class="Arg">n</var> points.</p>
<p>Ramanujan found the identities <span class="SimpleMath">p(5i+4) = 0</span> mod 5, <span class="SimpleMath">p(7i+5) = 0</span> mod 7 and <span class="SimpleMath">p(11i+6) = 0</span> mod 11 and many other fascinating things about the number of partitions.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IteratorOfPartitions</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For a positive integer <var class="Arg">n</var>, <code class="func">IteratorOfPartitions</code> returns an iterator (see <a href="chap30.html#X85A3F00985453F95"><span class="RefLink">30.8</span></a>) of the set of partitions of <var class="Arg">n</var> (see <code class="func">Partitions</code> (<a href="chap16.html#X84A6D15F8107008B"><span class="RefLink">16.2-18</span></a>)). The partitions of <var class="Arg">n</var> are returned in lexicographic order.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IteratorOfPartitionsSet</code>( <var class="Arg">set</var>[, <var class="Arg">k</var>[, <var class="Arg">flag</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IteratorOfPartitionsSet</code> returns an iterator (see <a href="chap30.html#X85A3F00985453F95"><span class="RefLink">30.8</span></a>) for all unordered partitions of the set <var class="Arg">set</var> into pairwise disjoint nonempty sets (see <code class="func">PartitionsSet</code> (<a href="chap16.html#X7A13D8DC8204525F"><span class="RefLink">16.2-16</span></a>)). If <var class="Arg">k</var> given and <var class="Arg">flag</var> is omitted or equal to <code class="keyw">false</code>, then only partitions of size <var class="Arg">k</var> are computed. If <var class="Arg">k</var> is given and <var class="Arg">flag</var> is equal to <code class="keyw">true</code>, then only partitions of size at most <var class="Arg">k</var> are computed.</p>
<p>The function <code class="func">OrderedPartitions</code> (<a href="chap16.html#X820DF201871F2723"><span class="RefLink">16.2-22</span></a>) is the ordered counterpart of <code class="func">Partitions</code> (<a href="chap16.html#X84A6D15F8107008B"><span class="RefLink">16.2-18</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrderedPartitions</code>( <var class="Arg">n</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all ordered partitions of the positive integer <var class="Arg">n</var> into sums with <var class="Arg">k</var> summands. If <var class="Arg">k</var> is not given it returns all ordered partitions of <var class="Arg">set</var> for all <var class="Arg">k</var>.</p>
<p>An <em>ordered partition</em> is an ordered sum <span class="SimpleMath">n = p_1 + p_2 + ... + p_k</span> of positive integers and is represented by the list <span class="SimpleMath">[ p_1, p_2, ..., p_k ]</span>. There are totally <span class="SimpleMath">2^{n-1}</span> ordered partitions and <span class="SimpleMath">{n-1 choose k-1}</span> (see <code class="func">Binomial</code> (<a href="chap16.html#X7A9AF5F58682819D"><span class="RefLink">16.1-2</span></a>)) ordered partitions with <var class="Arg">k</var> summands.</p>
<p>Do not call <code class="func">OrderedPartitions</code> with an <var class="Arg">n</var> much larger than <span class="SimpleMath">15</span>, the list will simply become too large.</p>
<p>The function <code class="func">Partitions</code> (<a href="chap16.html#X84A6D15F8107008B"><span class="RefLink">16.2-18</span></a>) is the unordered counterpart of <code class="func">OrderedPartitions</code> (<a href="chap16.html#X820DF201871F2723"><span class="RefLink">16.2-22</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PartitionsGreatestLE</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all (unordered) partitions of the integer <var class="Arg">n</var> having parts less or equal to the integer <var class="Arg">m</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PartitionsGreatestEQ</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the set of all (unordered) partitions of the integer <var class="Arg">n</var> having greatest part equal to the integer <var class="Arg">m</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RestrictedPartitions</code>( <var class="Arg">n</var>, <var class="Arg">set</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form <code class="func">RestrictedPartitions</code> returns the set of all restricted partitions of the positive integer <var class="Arg">n</var> into sums with <var class="Arg">k</var> summands with the summands of the partition coming from the set <var class="Arg">set</var>. If <var class="Arg">k</var> is not given all restricted partitions for all <var class="Arg">k</var> are returned.</p>
<p>A <em>restricted partition</em> is like an ordinary partition (see <code class="func">Partitions</code> (<a href="chap16.html#X84A6D15F8107008B"><span class="RefLink">16.2-18</span></a>)) an unordered sum <span class="SimpleMath">n = p_1 + p_2 + ... + p_k</span> of positive integers and is represented by the list <span class="SimpleMath">p = [ p_1, p_2, ..., p_k ]</span>, in nonincreasing order. The difference is that here the <span class="SimpleMath">p_i</span> must be elements from the set <var class="Arg">set</var>, while for ordinary partitions they may be elements from <code class="code">[ 1 .. n ]</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SignPartition</code>( <var class="Arg">pi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the sign of a permutation with cycle structure <var class="Arg">pi</var>.</p>
<p>This function actually describes a homomorphism from the symmetric group <span class="SimpleMath">S_n</span> into the cyclic group of order 2, whose kernel is exactly the alternating group <span class="SimpleMath">A_n</span> (see <code class="func">SignPerm</code> (<a href="chap42.html#X7BE5011B7C0DB704"><span class="RefLink">42.4-1</span></a>)). Partitions of sign 1 are called <em>even</em> partitions while partitions of sign <span class="SimpleMath">-1</span> are called <em>odd</em>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AssociatedPartition</code>( <var class="Arg">pi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">AssociatedPartition</code> returns the associated partition of the partition <var class="Arg">pi</var> which is obtained by transposing the corresponding Young diagram.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PowerPartition</code>( <var class="Arg">pi</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">PowerPartition</code> returns the partition corresponding to the <var class="Arg">k</var>-th power of a permutation with cycle structure <var class="Arg">pi</var>.</p>
<p>Each part <span class="SimpleMath">l</span> of <var class="Arg">pi</var> is replaced by <span class="SimpleMath">d = gcd(l, k)</span> parts <span class="SimpleMath">l/d</span>. So if <var class="Arg">pi</var> is a partition of <span class="SimpleMath">n</span> then <span class="SimpleMath"><var class="Arg">pi</var>^<var class="Arg">k</var></span> also is a partition of <span class="SimpleMath">n</span>. <code class="func">PowerPartition</code> describes the power map of symmetric groups.</p>
¤ Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.0.80Bemerkung:
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
