| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/doc/ref/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 18.9.2025 mit Größe 77 kB |
|
Quelle chap16.html Sprache: HTML |
||
<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head> <title>GAP (ref) - Chapter 16: Combinatorics</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8" /> <meta name="generator" content="GAPDoc2HTML" /> <link rel="stylesheet" type="text/css" href="manual.css" /> <script src="manual.js" type="text/javascript"></script> <script type="text/javascript">overwriteStyle();</script> </head> <body class="chap16" onload="jscontent()"> <div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a <div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#con <p id="mathjaxlink" class="pcenter"><a href="chap16_mj.html">[MathJax on]</a></p> <p><a id="X7BDA99EE7CEADA7C" name="X7BDA99EE7CEADA7C"></a></p> <div class="ChapSects"><a href="chap16.html#X7BDA99EE7CEADA7C">16 <span class="Heading">Co <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap16.html#X </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X87665F748594BF29"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7A9AF5F58682819D"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7DC5667580522BDA"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X792FF6EA786A5C2B"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X85037456785BB33C"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7C93E14D7BC360F0"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap16.html#X </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X8770F16D794C0ADB"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X78DD5C0D81057540"> </span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X82A6E98C85714FD0"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7837B3357C7566C8"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7DE1ABD47D19F140"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X81601C6786120DDC"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7959281584C42C52"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X86A3CA0F7CC8C320"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7BA135297E8DA819"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X86416A31807B0086"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X85E18A9A87FD4CA2"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7B0143FB83F359B7"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X8629A2908050EB3A"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X79C159507B2BF1C9"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7C1741B181A9AB9C"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7A13D8DC8204525F"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7BCD7FC2876386F1"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X84A6D15F8107008B"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X8793AEBD7E529E1D"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7EBD746A8607D0B8"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X86933C4F795C4EBD"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X820DF201871F2723"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X80BB9F4982CA1E8B"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X8009520C82942461"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7CB8D4FF8592A9BB"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7A70D4F3809494E7"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X800B43838742FBF4"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7F4EDCCA780B469D"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7DB9BEB6856EC03D"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7A95D8A6820363A8"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X877D997B7F66A119"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7F44AD098561DE32"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X8796C1D783ED9CB4"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap16.html#X </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X85AE1D70803A886C"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7830A03181D67192"> </div></div> <div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap16.html#X </span> <div class="ContSSBlock"> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap16.html#X7F0942DD83BBAB7A"> </div></div> </div> <h3>16 <span class="Heading">Combinatorics</span></h3> <p>This chapter describes functions that deal with combinatorics. We mainly concentrate on two <p><a id="X800E48927D5C83F5" name="X800E48927D5C83F5"></a></p> <h4>16.1 <span class="Heading">Combinatorial Numbers</span></h4> <p><a id="X87665F748594BF29" name="X87665F748594BF29"></a></p> <h5>16.1-1 Factorial</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Fa <p>returns the <em>factorial</em> <span class="SimpleMath">n!</span> of the positive integer <var cla <p><span class="SimpleMath">n!</span> is the number of permutations of a set of <span class="Simple <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">List( [0..10], Factorial );</span> [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ] <span class="GAPprompt">gap></span> <span class="GAPinput">Factorial( 30 );</span> 265252859812191058636308480000000 </pre></div> <p><code class="func">PermutationsList</code> (<a href="chap16.html#X7B0143FB83F359B7"><span <p><a id="X7A9AF5F58682819D" name="X7A9AF5F58682819D"></a></p> <h5>16.1-2 Binomial</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Bi <p>returns the <em>binomial coefficient</em> <span class="SimpleMath">{n choose k}</span> of intege <p>There are many ways of describing this function. For example, if <span class="SimpleMath">n ≥ 0</ <p>If <span class="SimpleMath">n ≥ 0</span> then <span class="SimpleMath">{n choose k}</span> is the nu <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput"># Knuth calls this the trademark of Bi <span class="GAPprompt">gap></span> <span class="GAPinput">List( [0..4], k->Binomial( 4, k ) );</s [ 1, 4, 6, 4, 1 ] <span class="GAPprompt">gap></span> <span class="GAPinput">List( [0..6], n->List( [0..6], k->Bin <span class="GAPprompt">gap></span> <span class="GAPinput"># the lower triangle is called Pascal <span class="GAPprompt">gap></span> <span class="GAPinput">PrintArray( last );</span> [ [ 1, 0, 0, 0, 0, 0, 0 ], [ 1, 1, 0, 0, 0, 0, 0 ], [ 1, 2, 1, 0, 0, 0, 0 ], [ 1, 3, 3, 1, 0, 0, 0 ], [ 1, 4, 6, 4, 1, 0, 0 ], [ 1, 5, 10, 10, 5, 1, 0 ], [ 1, 6, 15, 20, 15, 6, 1 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">Binomial( 50, 10 );</span> 10272278170 </pre></div> <p><code class="func">NrCombinations</code> (<a href="chap16.html#X82A6E98C85714FD0"><span cl <p><a id="X7DC5667580522BDA" name="X7DC5667580522BDA"></a></p> <h5>16.1-3 Bell</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Be <p>returns the <em>Bell number</em> <span class="SimpleMath">B(n)</span>. The Bell numbers are defin <p><span class="SimpleMath">B(n)</span> is the number of ways to partition a set of <var class="Arg"> <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">List( [0..6], n -> Bell( n ) );</span> [ 1, 1, 2, 5, 15, 52, 203 ] <span class="GAPprompt">gap></span> <span class="GAPinput">Bell( 14 );</span> 190899322 </pre></div> <p><a id="X792FF6EA786A5C2B" name="X792FF6EA786A5C2B"></a></p> <h5>16.1-4 Bernoulli</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Be <p>returns the <var class="Arg">n</var>-th <em>Bernoulli number</em> <span class="SimpleMath">B_n</s <p><span class="SimpleMath">B_n / n!</span> is the coefficient of <span class="SimpleMath">x^n</sp <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 p -691/2730 <span class="GAPprompt">gap></span> <span class="GAPinput">Bernoulli( 50 ); # and they grow fairl 495057205241079648212477525/66 </pre></div> <p><a id="X85037456785BB33C" name="X85037456785BB33C"></a></p> <h5>16.1-5 Stirling1</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ St <p>returns the <em>Stirling number of the first kind</em> <span class="SimpleMath">S_1(n,k)</span> o <p><span class="SimpleMath">S_1(n,k)</span> is the number of permutations of <var class="Arg">n</v <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput"># Knuth calls this the trademark of S_ <span class="GAPprompt">gap></span> <span class="GAPinput">List( [0..4], k -> Stirling1( 4, k ) );</ [ 0, 6, 11, 6, 1 ] <span class="GAPprompt">gap></span> <span class="GAPinput">List( [0..6], n->List( [0..6], k->Sti <span class="GAPprompt">gap></span> <span class="GAPinput"># note the similarity with Pascal's <span class="GAPprompt">gap></span> <span class="GAPinput">PrintArray( last );</span> [ [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0 ], [ 0, 1, 1, 0, 0, 0, 0 ], [ 0, 2, 3, 1, 0, 0, 0 ], [ 0, 6, 11, 6, 1, 0, 0 ], [ 0, 24, 50, 35, 10, 1, 0 ], [ 0, 120, 274, 225, 85, 15, 1 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">Stirling1(50,10);</span> 101623020926367490059043797119309944043405505380503665627365376 </pre></div> <p><a id="X7C93E14D7BC360F0" name="X7C93E14D7BC360F0"></a></p> <h5>16.1-6 Stirling2</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ St <p>returns the <em>Stirling number of the second kind</em> <span class="SimpleMath">S_2(n,k)</span> <p><span class="SimpleMath">S_2(n,k)</span> is the number of ways to partition a set of <var class=" <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput"># Knuth calls this the trademark of S_ <span class="GAPprompt">gap></span> <span class="GAPinput">List( [0..4], k->Stirling2( 4, k ) );</ [ 0, 1, 7, 6, 1 ] <span class="GAPprompt">gap></span> <span class="GAPinput">List( [0..6], n->List( [0..6], k->Sti <span class="GAPprompt">gap></span> <span class="GAPinput"># note the similarity with Pascal's <span class="GAPprompt">gap></span> <span class="GAPinput">PrintArray( last );</span> [ [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0 ], [ 0, 1, 1, 0, 0, 0, 0 ], [ 0, 1, 3, 1, 0, 0, 0 ], [ 0, 1, 7, 6, 1, 0, 0 ], [ 0, 1, 15, 25, 10, 1, 0 ], [ 0, 1, 31, 90, 65, 15, 1 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">Stirling2( 50, 10 );</span> 26154716515862881292012777396577993781727011 </pre></div> <p><a id="X81B4696585C38147" name="X81B4696585C38147"></a></p> <h4>16.2 <span class="Heading">Combinations, Arrangements and Tuples</span></h4> <p><a id="X8770F16D794C0ADB" name="X8770F16D794C0ADB"></a></p> <h5>16.2-1 Combinations</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Co <p>returns the set of all combinations of the multiset <var class="Arg">mset</var> (a list of object <p>A <em>combination</em> of <var class="Arg">mset</var> is an unordered selection without repetitio <p>To loop over combinations of a larger multiset use <code class="func">IteratorOfCombination <p><a id="X78DD5C0D81057540" name="X78DD5C0D81057540"></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">‣ It <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ En <p><code class="func">IteratorOfCombinations</code> returns an <code class="func">Iterator</co <p><code class="func">EnumeratorOfCombinations</code> returns an <code class="func">Enumerato <p>The ordering of combinations from these functions can be different and also different from th <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">m:=[1..15];; Add(m, 15);</span> <span class="GAPprompt">gap></span> <span class="GAPinput">NrCombinations(m);</span> 49152 <span class="GAPprompt">gap></span> <span class="GAPinput">i := 0;; for c in Combinations(m) do i : <span class="GAPprompt">gap></span> <span class="GAPinput">i;</span> 49152 <span class="GAPprompt">gap></span> <span class="GAPinput">cm := EnumeratorOfCombinations(m) <span class="GAPprompt">gap></span> <span class="GAPinput">cm[1000];</span> [ 1, 2, 3, 6, 7, 8, 9, 10 ] <span class="GAPprompt">gap></span> <span class="GAPinput">Position(cm, [1,13,15,15]);</span> 36866 </pre></div> <p><a id="X82A6E98C85714FD0" name="X82A6E98C85714FD0"></a></p> <h5>16.2-3 NrCombinations</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nr <p>returns the number of <code class="code">Combinations(<var class="Arg">mset</var>,<var class= <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">Combinations( [1,2,2,3] );</span> [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 2 ], [ 1, 2, 2, 3 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 2 ], [ 2, 2, 3 ], [ 2, 3 ], [ 3 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput"># number of different hands in a game o <span class="GAPprompt">gap></span> <span class="GAPinput">NrCombinations( [1..52], 5 );</span> 2598960 </pre></div> <p>The function <code class="func">Arrangements</code> (<a href="chap16.html#X7837B3357C7566 <p><a id="X7837B3357C7566C8" name="X7837B3357C7566C8"></a></p> <h5>16.2-4 Arrangements</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Ar <p>returns the set of arrangements of the multiset <var class="Arg">mset</var> that contain <var cla <p>An <em>arrangement</em> of <var class="Arg">mset</var> is an ordered selection without repetition <p><a id="X7DE1ABD47D19F140" name="X7DE1ABD47D19F140"></a></p> <h5>16.2-5 NrArrangements</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nr <p>returns the number of <code class="code">Arrangements(<var class="Arg">mset</var>,<var class= <p>As an example of arrangements of a multiset, think of the game Scrabble. Suppose you have the si <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">Arrangements( ["s","e","t","t"," [ [ "e", "e", "l", "s" ], [ "e", "e", "l", "t" ], [ "e", "e", "s", "l" ], [ "e", "e", "s", "t" ], [ "e", "e", "t", "l" ], [ "e", "e", "t", "s" ], ... 93 more possibilities ... [ "t", "t", "l", "s" ], [ "t", "t", "s", "e" ], [ "t", "t", "s", "l" ] ] </pre></div> <p>Can you find the five proper English words, where <code class="code">"lets"</code> does not coun <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">NrArrangements( ["s","e","t","t" 523 </pre></div> <p>The function <code class="func">Combinations</code> (<a href="chap16.html#X8770F16D794C0A <p><a id="X81601C6786120DDC" name="X81601C6786120DDC"></a></p> <h5>16.2-6 UnorderedTuples</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Un <p>returns the set of all unordered tuples of length <var class="Arg">k</var> of the set <var class="A <p>An <em>unordered tuple</em> of length <var class="Arg">k</var> of <var class="Arg">set</var> is an unor <p>Note that the fact that <code class="func">UnorderedTuples</code> returns a set implies that th <p><a id="X7959281584C42C52" name="X7959281584C42C52"></a></p> <h5>16.2-7 NrUnorderedTuples</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nr <p>returns the number of <code class="code">UnorderedTuples(<var class="Arg">set</var>,<var clas <p>As an example for unordered tuples think of a poker-like game played with 5 dice. Then each poss <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">NrUnorderedTuples( [1..6], 5 );</sp 252 <span class="GAPprompt">gap></span> <span class="GAPinput">UnorderedTuples( [1..6], 5 );</span> [ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 1, 2 ], [ 1, 1, 1, 1, 3 ], [ 1, 1, 1, 1, 4 ], [ 1, 1, 1, 1, 5 ], [ 1, 1, 1, 1, 6 ], [ 1, 1, 1, 2, 2 ], [ 1, 1, 1, 2, 3 ], ... 100 more tuples ... [ 1, 3, 5, 5, 6 ], [ 1, 3, 5, 6, 6 ], [ 1, 3, 6, 6, 6 ], [ 1, 4, 4, 4, 4 ], ... 100 more tuples ... [ 3, 3, 5, 5, 5 ], [ 3, 3, 5, 5, 6 ], [ 3, 3, 5, 6, 6 ], [ 3, 3, 6, 6, 6 ], ... 32 more tuples ... [ 5, 5, 5, 6, 6 ], [ 5, 5, 6, 6, 6 ], [ 5, 6, 6, 6, 6 ], [ 6, 6, 6, 6, 6 ] ] </pre></div> <p>The function <code class="func">Combinations</code> (<a href="chap16.html#X8770F16D794C0A <p><a id="X86A3CA0F7CC8C320" name="X86A3CA0F7CC8C320"></a></p> <h5>16.2-8 Tuples</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Tu <p>returns the set of all ordered tuples of length <var class="Arg">k</var> of the set <var class="Arg <p>An <em>ordered tuple</em> of length <var class="Arg">k</var> of <var class="Arg">set</var> is an ordere <p>Note that the fact that <code class="func">Tuples</code> returns a set implies that the last inde <p><a id="X7BA135297E8DA819" name="X7BA135297E8DA819"></a></p> <h5>16.2-9 EnumeratorOfTuples</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ En <p>This function is referred to as an example of enumerators that are defined by functions but are <p><a id="X86416A31807B0086" name="X86416A31807B0086"></a></p> <h5>16.2-10 IteratorOfTuples</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ It <p>For a set <var class="Arg">set</var> and a positive integer <var class="Arg">k</var>, <code class="f <p><a id="X85E18A9A87FD4CA2" name="X85E18A9A87FD4CA2"></a></p> <h5>16.2-11 NrTuples</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nr <p>returns the number of <code class="code">Tuples(<var class="Arg">set</var>,<var class="Arg">k</ <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">Tuples( [1,2,3], 2 );</span> [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">NrTuples( [1..10], 5 );</span> 100000 </pre></div> <p><code class="code">Tuples(<var class="Arg">set</var>,<var class="Arg">k</var>)</code> can also be <p>The function <code class="func">Combinations</code> (<a href="chap16.html#X8770F16D794C0A <p><a id="X7B0143FB83F359B7" name="X7B0143FB83F359B7"></a></p> <h5>16.2-12 PermutationsList</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Pe <p><code class="func">PermutationsList</code> returns the set of permutations of the multiset <va <p>A <em>permutation</em> is represented by a list that contains exactly the same elements as <var cla <p><a id="X8629A2908050EB3A" name="X8629A2908050EB3A"></a></p> <h5>16.2-13 NrPermutationsList</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nr <p>returns the number of <code class="code">PermutationsList(<var class="Arg">mset</var>)</code> <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">PermutationsList( [1,2,3] );</span> [ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">PermutationsList( [1,1,2,2] );</sp [ [ 1, 1, 2, 2 ], [ 1, 2, 1, 2 ], [ 1, 2, 2, 1 ], [ 2, 1, 1, 2 ], [ 2, 1, 2, 1 ], [ 2, 2, 1, 1 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">NrPermutationsList( [1,2,2,3,3,3 12600 </pre></div> <p>The function <code class="func">Arrangements</code> (<a href="chap16.html#X7837B3357C7566 <p><a id="X79C159507B2BF1C9" name="X79C159507B2BF1C9"></a></p> <h5>16.2-14 Derangements</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ De <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 represe <p>Note that the ratio <code class="code">NrPermutationsList( [ 1 .. n ] ) / NrDerangements( [ 1 .. n <p><a id="X7C1741B181A9AB9C" name="X7C1741B181A9AB9C"></a></p> <h5>16.2-15 NrDerangements</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nr <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 diff <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">Derangements( [1,2,3,4] );</span> [ [ 2, 1, 4, 3 ], [ 2, 3, 4, 1 ], [ 2, 4, 1, 3 ], [ 3, 1, 4, 2 ], [ 3, 4, 1, 2 ], [ 3, 4, 2, 1 ], [ 4, 1, 2, 3 ], [ 4, 3, 1, 2 ], [ 4, 3, 2, 1 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">NrDerangements( [1..10] );</span> 1334961 <span class="GAPprompt">gap></span> <span class="GAPinput">Int( 10^7*NrPermutationsList([1. 27182816 <span class="GAPprompt">gap></span> <span class="GAPinput">Derangements( [1,1,2,2,3,3] );</sp [ [ 2, 2, 3, 3, 1, 1 ], [ 2, 3, 1, 3, 1, 2 ], [ 2, 3, 1, 3, 2, 1 ], [ 2, 3, 3, 1, 1, 2 ], [ 2, 3, 3, 1, 2, 1 ], [ 3, 2, 1, 3, 1, 2 ], [ 3, 2, 1, 3, 2, 1 ], [ 3, 2, 3, 1, 1, 2 ], [ 3, 2, 3, 1, 2, 1 ], [ 3, 3, 1, 1, 2, 2 ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">NrDerangements( [1,2,2,3,3,3,4,4 338 </pre></div> <p>The function <code class="func">PermutationsList</code> (<a href="chap16.html#X7B0143FB83 <p><a id="X7A13D8DC8204525F" name="X7A13D8DC8204525F"></a></p> <h5>16.2-16 PartitionsSet</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Pa <p>returns the set of all unordered partitions of the set <var class="Arg">set</var> into <var class= <p>An <em>unordered partition</em> of <var class="Arg">set</var> is a set of pairwise disjoint nonempt <p><a id="X7BCD7FC2876386F1" name="X7BCD7FC2876386F1"></a></p> <h5>16.2-17 NrPartitionsSet</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nr <p>returns the number of <code class="code">PartitionsSet(<var class="Arg">set</var>,<var class= <div class="example"><pre> <span class="GAPprompt">gap></span> <span class="GAPinput">PartitionsSet( [1,2,3] );</span> [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 2, 3 ] ], [ [ 1, 2 ], [ 3 ] ], [ [ 1, 2, 3 ] ], [ [ 1, 3 ], [ 2 ] ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">PartitionsSet( [1,2,3,4], 2 );</spa [ [ [ 1 ], [ 2, 3, 4 ] ], [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 2, 3 ], [ 4 ] ], [ [ 1, 2, 4 ], [ 3 ] ], [ [ 1, 3 ], [ 2, 4 ] ], [ [ 1, 3, 4 ], [ 2 ] ], [ [ 1, 4 ], [ 2, 3 ] ] ] <span class="GAPprompt">gap></span> <span class="GAPinput">NrPartitionsSet( [1..6] );</span> 203 <span class="GAPprompt">gap></span> <span class="GAPinput">NrPartitionsSet( [1..10], 3 );</spa 9330 </pre></div> <p>Note that <code class="func">PartitionsSet</code> (<a href="chap16.html#X7A13D8DC8204525F <p><a id="X84A6D15F8107008B" name="X84A6D15F8107008B"></a></p> <h5>16.2-18 Partitions</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Pa <p>returns the set of all (unordered) partitions of the positive integer <var class="Arg">n</var> i <p>An <em>unordered partition</em> is an unordered sum <span class="SimpleMath">n = p_1 + p_2 + ⋯ + p_k</s <p>If you want to loop over all partitions of some larger <var class="Arg">n</var> use the more memory |
