<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 \cdot 2 \cdot 3 \cdots 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_mj.html#X7B0143FB83F359B7"><span class="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 \neq 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 \geq 0\)</span> and <span class="SimpleMath">\(0 \leq k \leq 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 \geq 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 \geq 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 <spanclass="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_mj.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_mj.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) = \sum_{{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_mj.html#X7A13D8DC8204525F"><span class="RefLink">16.2-16</span></a>)). This implies of course that <span class="SimpleMath">\(B(n) = \sum_{{k = 0}}^n S_2(n,k)\)</span> (see <code class="func">Stirling2</code> (<a href="chap16_mj.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 = -\sum_{{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}} = \sum_{{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 = \sum_{{k = 0}}^n S_2(n,k) k! {{x \choose k}}\)</span> (see <code class="func">Stirling2</code> (<a href="chap16_mj.html#X7C93E14D7BC360F0"><spanclass="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_mj.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 = \sum_{{k = 0}}^n S_2(n,k) k! {{x \choose k}}\)</span>. Note the similarity to <span class="SimpleMath">\(n! {{x \choose n}} = \sum_{{k = 0}}^n S_1(n,k) x^k\)</span> (see <code class="func">Stirling1</code> (<a href="chap16_mj.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">\({{|\textit{mset}| \choose \textit{k}}}\)</span> (see <code class="func">Binomial</code> (<a href="chap16_mj.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^{{|\textit{mset}|}}\)</span>.</p>
<p>To loop over combinations of a larger multiset use <code class="func">IteratorOfCombinations</code> (<a href="chap16_mj.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_mj.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_mj.html#X83ADF8287ED0668E"><span class="RefLink">30.8-1</span></a>) for combinations (see <code class="func">Combinations</code> (<a href="chap16_mj.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_mj.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_mj.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_mj.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_mj.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_mj.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, \ldots, 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">\(|\textit{set}|^{\textit{k}}\)</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_mj.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_mj.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_mj.html#X7E1593B979BDF2CD"><span class="RefLink">21.20-15</span></a>)).</p>
<p>The function <code class="func">Combinations</code> (<a href="chap16_mj.html#X8770F16D794C0ADB"><span class="RefLink">16.2-1</span></a>) computes unordered selections without repetitions, <code class="func">Arrangements</code> (<a href="chap16_mj.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_mj.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">\(|\textit{mset}| !\)</span> (see <code class="func">Factorial</code> (<a href="chap16_mj.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">\(|\textit{mset}| ! / (k_1! k_2! \ldots)\)</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_mj.html#X7837B3357C7566C8"><span class="RefLink">16.2-4</span></a>) is the generalization of <code class="func">PermutationsList</code> (<a href="chap16_mj.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_mj.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">\(|\textit{list}|! (1/2! - 1/3! + 1/4! - \cdots + (-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! - \cdots + (-1)^n / n!))\)</span> is an approximation for the base of the natural logarithm <span class="SimpleMath">\(e = 2.7182818285\ldots\)</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_mj.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_mj.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_mj.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_mj.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 + \cdots + p_k\)</span> of positive integers and is represented by the list <span class="SimpleMath">\(p = [ p_1, p_2, \ldots, p_k ]\)</span>, in nonincreasing order, i.e., <span class="SimpleMath">\(p_1 \geq p_2 \geq \ldots \geq p_k\)</span>. We write <span class="SimpleMath">\(p \vdash n\)</span>. There are approximately <span class="SimpleMath">\(\exp(\pi \sqrt{{2/3 n}}) / (4 \sqrt{{3}} n)\)</span> such partitions, use <code class="func">NrPartitions</code> (<a href="chap16_mj.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_mj.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_mj.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_mj.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_mj.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_mj.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_mj.html#X820DF201871F2723"><span class="RefLink">16.2-22</span></a>) is the ordered counterpart of <code class="func">Partitions</code> (<a href="chap16_mj.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 + \ldots + p_k\)</span> of positive integers and is represented by the list <span class="SimpleMath">\([ p_1, p_2, \ldots, 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_mj.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_mj.html#X84A6D15F8107008B"><span class="RefLink">16.2-18</span></a>) is the unordered counterpart of <code class="func">OrderedPartitions</code> (<a href="chap16_mj.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_mj.html#X84A6D15F8107008B"><span class="RefLink">16.2-18</span></a>)) an unordered sum <span class="SimpleMath">\(n = p_1 + p_2 + \ldots + p_k\)</span> of positive integers and is represented by the list <span class="SimpleMath">\(p = [ p_1, p_2, \ldots, 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_mj.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>
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.
