<html><head><title>[ref] 17 Combinatorics</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP016.htm">Previous</a>] [<a href ="CHAP018.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>17 Combinatorics</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP017.htm#SECT001">Combinatorial Numbers</a> <li> <A HREF="CHAP017.htm#SECT002">Combinations, Arrangements and Tuples</a> <li> <A HREF="CHAP017.htm#SECT003">Fibonacci and Lucas Sequences</a> <li> <A HREF="CHAP017.htm#SECT004">Permanent of a Matrix</a> </ol><p> <p> This chapter describes the functions that deal with combinatorics. We mainly concentrate on two areas. One is about <strong>selections</strong>, that is the ways one can select elements from a set. The other is about <strong>partitions</strong>, that is the ways one can partition a set into the union of pairwise disjoint subsets. <p> <p> <h2><a name="SECT001">17.1 Combinatorial Numbers</a></h2> <p><p> <a name = "SSEC001.1"></a> <li><code>Factorial( </code><var>n</var><code> ) F</code> <p> returns the <strong>factorial</strong> <i>n</i>! of the positive integer <var>n</var>, which is defined as the product 1 ·2 ·3 …<i>n</i>. <p> <i>n</i>! is the number of permutations of a set of <i>n</i> elements. 1/<i>n</i>! is the coefficient of <i>x</i><sup><i>n</i></sup> in the formal series <i>e</i><sup><i>x</i></sup>, which is the generating function for factorial. <p> <pre> gap> List( [0..10], Factorial ); [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ] gap> Factorial( 30 ); 265252859812191058636308480000000 </pre> <p> <code>PermutationsList</code> (see <a href="CHAP017.htm#SSEC002.9">PermutationsList</a>) computes the set of all permutations of a list. <p> <a name = "SSEC001.2"></a> <li><code>Binomial( </code><var>n</var><code>, </code><var>k</var><code> ) F</code> <p> returns the <strong>binomial coefficient</strong> <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table> of integers <var>n</var> and <var>k</var>, which is defined as <i>n</i>! / (<i>k</i>! (<i>n</i>−<i>k</i>)!) (see <a href="CHAP017.htm#SSEC001.1">Factorial</a>). We define <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center">0<br />0<br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"> = 1, </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"> = 0</td></tr></table></td></tr></table> if <i>k</i> < 0 or <i>n</i> < <i>k</i>, and <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"> = (−1)<sup><i>k</i></sup> </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center">−<i>n</i>+<i>k</i>−1<br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table> if <i>n</i> < 0, which is consistent with the equivalent definition <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"> = </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i>−1<br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center">+ </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i>−1<br /><i>k</i>−1<br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center">·</td></tr></table></td></tr></table> <p> <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table> is the number of combinations with <i>k</i> elements, i.e., the number of subsets with <i>k</i> elements, of a set with <i>n</i> elements. <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table> is the coefficient of the term <i>x</i><sup><i>k</i></sup> of the polynomial (<i>x</i> + 1)<sup><i>n</i></sup>, which is the generating function for <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i><br />·<br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center">,</td></tr></table></td></tr></table> hence the name. <p> <a name = "I0"></a> <a name = "I0"></a> <a name = "I1"></a> <pre> gap> List( [0..4], k->Binomial( 4, k ) ); # Knuth calls this the trademark of Binomial [ 1, 4, 6, 4, 1 ] gap> List( [0..6], n->List( [0..6], k->Binomial( n, k ) ) );; gap> PrintArray( last ); # the lower triangle is called Pascal's triangle [ [ 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 ] ] gap> Binomial( 50, 10 ); 10272278170 </pre> <p> <code>NrCombinations</code> (see <a href="CHAP017.htm#SSEC002.1">Combinations</a>) is the generalization of <code>Binomial</code> for multisets. <code>Combinations</code> (see <a href="CHAP017.htm#SSEC002.1">Combinations</a>) computes the set of all combinations of a multiset. <p> <a name = "SSEC001.3"></a> <li><code>Bell( </code><var>n</var><code> ) F</code> <p> returns the <strong>Bell number</strong> <i>B</i>(<i>n</i>). The Bell numbers are defined by <i>B</i>(0)=1 and the recurrence <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>B</i>(<i>n</i>+1) = </td><td nowrap="nowrap" align="center"><small><i>n</i></small><!--sup--><br /><font size="+3">∑<br /></font><small><i>k</i>=0</small> <br /></td><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>B</i>(<i>k</i>)</td></tr></table></td></tr></table>. <p> <i>B</i>(<i>n</i>) is the number of ways to partition a set of <var>n</var> elements into pairwise disjoint nonempty subsets (see <a href="CHAP017.htm#SSEC002.13">PartitionsSet</a>). This implies of course that <i>B</i>(<i>n</i>) = ∑<sub><i>k</i>=0</sub><sup><i>n</i></sup><i>S</i><sub>2</sub>(<i>n</i>,<i>k</i>) (see <a href="CHAP017.htm#SSEC001.6">Stirling2</a>). <i>B</i>(<i>n</i>)/<i>n</i>! is the coefficient of <i>x</i><sup><i>n</i></sup> in the formal series <i>e</i><sup><i>e</i><sup><i>x</i></sup>−1</sup>, which is the generating function for <i>B</i>(<i>n</i>). <p> <a name = "I2"></a> <pre> gap> List( [0..6], n -> Bell( n ) ); [ 1, 1, 2, 5, 15, 52, 203 ] gap> Bell( 14 ); 190899322 </pre> <p> <a name = "SSEC001.4"></a> <li><code>Bernoulli( </code><var>n</var><code> ) F</code> <p> returns the <var>n</var>-th <strong>Bernoulli number</strong> <i>B</i><sub><i>n</i></sub>, which is defined by <i>B</i><sub>0</sub> = 1 and <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>B</i><sub><i>n</i></sub> = −</td><td nowrap="nowrap" align="center"><small><i>n</i>−1</small><!--sup--><br /><font size="+3">∑<br /></font><small><i>k</i>=0</small> <br /></td><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i>+1<br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>B</i><sub><i>k</i></sub>/(<i>n</i>+1)</td></tr></table></td></tr></table>. <p> <i>B</i><sub><i>n</i></sub>/<i>n</i>! is the coefficient of <i>x</i><sup><i>n</i></sup> in the power series of <i>x</i>/<i>e</i><sup><i>x</i></sup>−1. Except for <i>B</i><sub>1</sub>=−1/2 the Bernoulli numbers for odd indices are zero. <p> <a name = "I3"></a> <pre> gap> Bernoulli( 4 ); -1/30 gap> Bernoulli( 10 ); 5/66 gap> Bernoulli( 12 ); # there is no simple pattern in Bernoulli numbers -691/2730 gap> Bernoulli( 50 ); # and they grow fairly fast 495057205241079648212477525/66 </pre> <p> <a name = "SSEC001.5"></a> <li><code>Stirling1( </code><var>n</var><code>, </code><var>k</var><code> ) F</code> <p> returns the <strong>Stirling number of the first kind</strong> <i>S</i><sub>1</sub>(<i>n</i>,<i>k</i>) of the integers <var>n</var> and <var>k</var>. Stirling numbers of the first kind are defined by <i>S</i><sub>1</sub>(0,0) = 1, <i>S</i><sub>1</sub>(<i>n</i>,0) = <i>S</i><sub>1</sub>(0,<i>k</i>) = 0 if <i>n</i>, <i>k</i> ≠ 0 and the recurrence <i>S</i><sub>1</sub>(<i>n</i>,<i>k</i>) = (<i>n</i>−1) <i>S</i><sub>1</sub>(<i>n</i>−1,<i>k</i>) + <i>S</i><sub>1</sub>(<i>n</i>−1,<i>k</i>−1). <p> <i>S</i><sub>1</sub>(<i>n</i>,<i>k</i>) is the number of permutations of <var>n</var> points with <var>k</var> cycles. Stirling numbers of the first kind appear as coefficients in the series <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>n</i>! </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>x</i><br /><i>n</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"> = </td><td nowrap="nowrap" align="center"><small><i>n</i></small><!--sup--><br /><font size="+3">∑<br /></font><small><i>k</i>=0</small> <br /></td><td nowrap="nowrap" align="center"><i>S</i><sub>1</sub>(<i>n</i>,<i>k</i>) <i>x</i><sup><i>k</i></sup></td></tr></table></td></tr></table> which is the generating function for Stirling numbers of the first kind. Note the similarity to <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>x</i><sup><i>n</i></sup> = </td><td nowrap="nowrap" align="center"><small><i>n</i></small><!--sup--><br /><font size="+3">∑<br /></font><small><i>k</i>=0</small> <br /></td><td nowrap="nowrap" align="center"><i>S</i><sub>2</sub>(<i>n</i>,<i>k</i>) <i>k</i>! </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>x</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table> (see <a href="CHAP017.htm#SSEC001.6">Stirling2</a>). Also the definition of <i>S</i><sub>1</sub> implies <i>S</i><sub>1</sub>(<i>n</i>,<i>k</i>) = <i>S</i><sub>2</sub>(−<i>k</i>,−<i>n</i>) if <i>n</i>,<i>k</i> < 0. There are many formulae relating Stirling numbers of the first kind to Stirling numbers of the second kind, Bell numbers, and Binomial coefficients. <p> <a name = "I4"></a> <a name = "I5"></a> <pre> gap> List( [0..4], k -> Stirling1( 4, k ) ); # Knuth calls this the trademark of S_1 [ 0, 6, 11, 6, 1 ] gap> List( [0..6], n->List( [0..6], k->Stirling1( n, k ) ) );; gap> # note the similarity with Pascal's triangle for the Binomial numbers gap> PrintArray( last ); [ [ 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 ] ] gap> Stirling1(50,10); 101623020926367490059043797119309944043405505380503665627365376 </pre> <p> <a name = "SSEC001.6"></a> <li><code>Stirling2( </code><var>n</var><code>, </code><var>k</var><code> ) F</code> <p> returns the <strong>Stirling number of the second kind</strong> <i>S</i><sub>2</sub>(<i>n</i>,<i>k</i>) of the integers <var>n</var> and <var>k</var>. Stirling numbers of the second kind are defined by <i>S</i><sub>2</sub>(0,0) = 1, <i>S</i><sub>2</sub>(<i>n</i>,0) = <i>S</i><sub>2</sub>(0,<i>k</i>) = 0 if <i>n</i>, <i>k</i> ≠ 0 and the recurrence <i>S</i><sub>2</sub>(<i>n</i>,<i>k</i>) = <i>k</i> <i>S</i><sub>2</sub>(<i>n</i>−1,<i>k</i>) + <i>S</i><sub>2</sub>(<i>n</i>−1,<i>k</i>−1). <p> <i>S</i><sub>2</sub>(<i>n</i>,<i>k</i>) is the number of ways to partition a set of <var>n</var> elements into <var>k</var> pairwise disjoint nonempty subsets (see <a href="CHAP017.htm#SSEC002.13">PartitionsSet</a>). Stirling numbers of the second kind appear as coefficients in the expansion of <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>x</i><sup><i>n</i></sup> = </td><td nowrap="nowrap" align="center"><small><i>n</i></small><!--sup--><br /><font size="+3">∑<br /></font><small><i>k</i>=0</small> <br /></td><td nowrap="nowrap" align="center"><i>S</i><sub>2</sub>(<i>n</i>,<i>k</i>) <i>k</i>! </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>x</i><br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table>. Note the similarity to <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>n</i>! </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>x</i><br /><i>n</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"> = </td><td nowrap="nowrap" align="center"><small><i>n</i></small><!--sup--><br /><font size="+3">∑<br /></font><small><i>k</i>=0</small> <br /></td><td nowrap="nowrap" align="center"><i>S</i><sub>1</sub>(<i>n</i>,<i>k</i>) <i>x</i><sup><i>k</i></sup></td></tr></table></td></tr></table> (see <a href="CHAP017.htm#SSEC001.5">Stirling1</a>). Also the definition of <i>S</i><sub>2</sub> implies <i>S</i><sub>2</sub>(<i>n</i>,<i>k</i>) = <i>S</i><sub>1</sub>(−<i>k</i>,−<i>n</i>) if <i>n</i>,<i>k</i> < 0. There are many formulae relating Stirling numbers of the second kind to Stirling numbers of the first kind, Bell numbers, and Binomial coefficients. <p> <a name = "I6"></a> <a name = "I7"></a> <pre> gap> List( [0..4], k->Stirling2( 4, k ) ); # Knuth calls this the trademark of S_2 [ 0, 1, 7, 6, 1 ] gap> List( [0..6], n->List( [0..6], k->Stirling2( n, k ) ) );; gap> # note the similarity with Pascal's triangle for the Binomial numbers gap> PrintArray( last ); [ [ 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 ] ] gap> Stirling2( 50, 10 ); 26154716515862881292012777396577993781727011 </pre> <p> <p> <h2><a name="SECT002">17.2 Combinations, Arrangements and Tuples</a></h2> <p><p> <a name = "SSEC002.1"></a> <li><code>Combinations( </code><var>mset</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the set of all combinations of the multiset <var>mset</var> (a list of objects which may contain the same object several times) with <var>k</var> elements; if <var>k</var> is not given it returns all combinations of <var>mset</var>. <p> A <strong>combination</strong> of <var>mset</var> is an unordered selection without repetitions and is represented by a sorted sublist of <var>mset</var>. If <var>mset</var> is a proper set, there are <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center">|<i>mset</i>|<br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table> (see <a href="CHAP017.htm#SSEC001.2">Binomial</a>) combinations with <var>k</var> elements, and the set of all combinations is just the <strong>powerset</strong> of <var>mset</var>, which contains all <strong>subsets</strong> of <var>mset</var> and has cardinality 2<sup>|<i>mset</i>|</sup>. <p> <a name = "SSEC002.2"></a> <li><code>NrCombinations( </code><var>mset</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the number of <code>Combinations(</code><var>mset</var><code>,</code><var>k</var><code>)</code>. <p> <a name = "I8"></a> <a name = "I8"></a> <a name = "I9"></a> <pre> gap> Combinations( [1,2,2,3] ); [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 2 ], [ 1, 2, 2, 3 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 2 ], [ 2, 2, 3 ], [ 2, 3 ], [ 3 ] ] gap> NrCombinations( [1..52], 5 ); # number of different hands in a game of poker 2598960 </pre> <p> The function <code>Arrangements</code> (see <a href="CHAP017.htm#SSEC002.3">Arrangements</a>) computes ordered selections without repetitions, <code>UnorderedTuples</code> (see <a href="CHAP017.htm#SSEC002.5">UnorderedTuples</a>) computes unordered selections with repetitions and <code>Tuples</code> (see <a href="CHAP017.htm#SSEC002.7">Tuples</a>) computes ordered selections with repetitions. <p> <a name = "SSEC002.3"></a> <li><code>Arrangements( </code><var>mset</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the set of arrangements of the multiset <var>mset</var> that contain <var>k</var> elements. If <var>k</var> is not given it returns all arrangements of <var>mset</var>. <p> An <strong>arrangement</strong> of <var>mset</var> is an ordered selection without repetitions and is represented by a list that contains only elements from <var>mset</var>, but maybe in a different order. If <var>mset</var> is a proper set there are |<i>mset</i>|! / (|<i>mset</i>|−<i>k</i>)! (see <a href="CHAP017.htm#SSEC001.1">Factorial</a>) arrangements with <var>k</var> elements. <p> <a name = "SSEC002.4"></a> <li><code>NrArrangements( </code><var>mset</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the number of <code>Arrangements(</code><var>mset</var><code>,</code><var>k</var><code>)</code>. <p> As an example of arrangements of a multiset, think of the game Scrabble. Suppose you have the six characters of the word <code>settle</code> and you have to make a four letter word. Then the possibilities are given by <p> <pre> gap> Arrangements( ["s","e","t","t","l","e"], 4 ); [ [ "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> <p> Can you find the five proper English words, where <code>lets</code> does not count? Note that the fact that the list returned by <code>Arrangements</code> is a proper set means in this example that the possibilities are listed in the same order as they appear in the dictionary. <p> <pre> gap> NrArrangements( ["s","e","t","t","l","e"] ); 523 </pre> <p> The function <code>Combinations</code> (see <a href="CHAP017.htm#SSEC002.1">Combinations</a>) computes unordered selections without repetitions, <code>UnorderedTuples</code> (see <a href="CHAP017.htm#SSEC002.5">UnorderedTuples</a>) computes unordered selections with repetitions and <code>Tuples</code> (see <a href="CHAP017.htm#SSEC002.7">Tuples</a>) computes ordered selections with repetitions. <p> <a name = "SSEC002.5"></a> <li><code>UnorderedTuples( </code><var>set</var><code>, </code><var>k</var><code> ) F</code> <p> returns the set of all unordered tuples of length <var>k</var> of the set <var>set</var>. <p> An <strong>unordered tuple</strong> of length <var>k</var> of <var>set</var> is a unordered selection with repetitions of <var>set</var> and is represented by a sorted list of length <var>k</var> containing elements from <var>set</var>. There are <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center">|<i>set</i>|+<i>k</i>−1<br /><i>k</i><br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table> (see <a href="CHAP017.htm#SSEC001.2">Binomial</a>) such unordered tuples. <p> Note that the fact that <code>UnorderedTuples</code> returns a set implies that the last index runs fastest. That means the first tuple contains the smallest element from <var>set</var> <var>k</var> times, the second tuple contains the smallest element of <var>set</var> at all positions except at the last positions, where it contains the second smallest element from <var>set</var> and so on. <p> <a name = "SSEC002.6"></a> <li><code>NrUnorderedTuples( </code><var>set</var><code>, </code><var>k</var><code> ) F</code> <p> returns the number of <code>UnorderedTuples(</code><var>set</var><code>,</code><var>k</var><code>)</code>. <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 [1..6] <p> <pre> gap> NrUnorderedTuples( [1..6], 5 ); 252 gap> UnorderedTuples( [1..6], 5 ); [ [ 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> <p> The function <code>Combinations</code> (see <a href="CHAP017.htm#SSEC002.1">Combinations</a>) computes unordered selections without repetitions, <code>Arrangements</code> (see <a href="CHAP017.htm#SSEC002.3">Arrangements</a>) computes ordered selections without repetitions and <code>Tuples</code> (see <a href="CHAP017.htm#SSEC002.7">Tuples</a>) computes ordered selections with repetitions. <p> <a name = "SSEC002.7"></a> <li><code>Tuples( </code><var>set</var><code>, </code><var>k</var><code> ) F</code> <p> returns the set of all ordered tuples of length <var>k</var> of the set <var>set</var>. <p> An <strong>ordered tuple</strong> of length <var>k</var> of <var>set</var> is an ordered selection with repetition and is represented by a list of length <var>k</var> containing elements of <var>set</var>. There are |<i>set</i>|<sup><i>k</i></sup> such ordered tuples. <p> Note that the fact that <code>Tuples</code> returns a set implies that the last index runs fastest. That means the first tuple contains the smallest element from <var>set</var> <var>k</var> times, the second tuple contains the smallest element of <var>set</var> at all positions except at the last positions, where it contains the second smallest element from <var>set</var> and so on. <p> <a name = "SSEC002.8"></a> <li><code>NrTuples( </code><var>set</var><code>, </code><var>k</var><code> ) F</code> <p> returns the number of <code>Tuples(</code><var>set</var><code>,</code><var>k</var><code>)</code>. <p> <pre> gap> Tuples( [1,2,3], 2 ); [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ] gap> NrTuples( [1..10], 5 ); 100000 </pre> <p> <code>Tuples(</code><var>set</var><code>,</code><var>k</var><code>)</code> can also be viewed as the <var>k</var>-fold cartesian product of <var>set</var> (see <a href="CHAP021.htm#SSEC020.15">Cartesian</a>). <p> The function <code>Combinations</code> (see <a href="CHAP017.htm#SSEC002.1">Combinations</a>) computes unordered selections without repetitions, <code>Arrangements</code> (see <a href="CHAP017.htm#SSEC002.3">Arrangements</a>) computes ordered selections without repetitions, and finally the function <code>UnorderedTuples</code> (see <a href="CHAP017.htm#SSEC002.5">UnorderedTuples</a>) computes unordered selections with repetitions. <p> <a name = "SSEC002.9"></a> <li><code>PermutationsList( </code><var>mset</var><code> ) F</code> <p> <code>PermutationsList</code> returns the set of permutations of the multiset <var>mset</var>. <p> A <strong>permutation</strong> is represented by a list that contains exactly the same elements as <var>mset</var>, but possibly in different order. If <var>mset</var> is a proper set there are |<i>mset</i>| ! (see <a href="CHAP017.htm#SSEC001.1">Factorial</a>) such permutations. Otherwise if the first elements appears <i>k</i><sub>1</sub> times, the second element appears <i>k</i><sub>2</sub> times and so on, the number of permutations is |<i>mset</i>|! / (<i>k</i><sub>1</sub>! <i>k</i><sub>2</sub>! …), which is sometimes called multinomial coefficient. <p> <a name = "SSEC002.10"></a> <li><code>NrPermutationsList( </code><var>mset</var><code> ) F</code> <p> returns the number of <code>PermutationsList(</code><var>mset</var><code>)</code>. <p> <pre> gap> PermutationsList( [1,2,3] ); [ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ] gap> PermutationsList( [1,1,2,2] ); [ [ 1, 1, 2, 2 ], [ 1, 2, 1, 2 ], [ 1, 2, 2, 1 ], [ 2, 1, 1, 2 ], [ 2, 1, 2, 1 ], [ 2, 2, 1, 1 ] ] gap> NrPermutationsList( [1,2,2,3,3,3,4,4,4,4] ); 12600 </pre> <p> The function <code>Arrangements</code> (see <a href="CHAP017.htm#SSEC002.3">Arrangements</a>) is the generalization of <code>PermutationsList</code> that allows you to specify the size of the permutations. <code>Derangements</code> (see <a href="CHAP017.htm#SSEC002.11">Derangements</a>) computes permutations that have no fixpoints. <p> <a name = "SSEC002.11"></a> <li><code>Derangements( </code><var>list</var><code> ) F</code> <p> returns the set of all derangements of the list <var>list</var>. <p> A <strong>derangement</strong> is a fixpointfree permutation of <var>list</var> and is represented by a list that contains exactly the same elements as <var>list</var>, but in such an order that the derangement has at no position the same element as <var>list</var>. If the list <var>list</var> contains no element twice there are exactly |<i>list</i>|! (1/2! − 1/3! + 1/4! − …+ (−1)<sup><i>n</i></sup>/<i>n</i>!) derangements. <p> Note that the ratio <code>NrPermutationsList([1..n])/NrDerangements([1..n])</code>, which is <i>n</i>! / (<i>n</i>! (1/2! − 1/3! + 1/4! − …+ (−1)<sup><i>n</i></sup>/<i>n</i>!)) is an approximation for the base of the natural logarithm <i>e</i> = 2.7182818285…, which is correct to about <i>n</i> digits. <p> <a name = "SSEC002.12"></a> <li><code>NrDerangements( </code><var>list</var><code> ) F</code> <p> returns the number of <code>Derangements(</code><var>list</var><code>)</code>. <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> <pre> gap> Derangements( [1,2,3,4] ); [ [ 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 ] ] gap> NrDerangements( [1..10] ); 1334961 gap> Int( 10^7*NrPermutationsList([1..10])/last ); 27182816 gap> Derangements( [1,1,2,2,3,3] ); [ [ 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 ] ] gap> NrDerangements( [1,2,2,3,3,3,4,4,4,4] ); 338 </pre> <p> The function <code>PermutationsList</code> (see <a href="CHAP017.htm#SSEC002.9">PermutationsList</a>) computes all permutations of a list. <p> <a name = "SSEC002.13"></a> <li><code>PartitionsSet( </code><var>set</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the set of all unordered partitions of the set <var>set</var> into <var>k</var> pairwise disjoint nonempty sets. If <var>k</var> is not given it returns all unordered partitions of <var>set</var> for all <var>k</var>. <p> An <strong>unordered partition</strong> of <var>set</var> is a set of pairwise disjoint nonempty sets with union <var>set</var> and is represented by a sorted list of such sets. There are <i>B</i>( |<i>set</i>| ) (see <a href="CHAP017.htm#SSEC001.3">Bell</a>) partitions of the set <var>set</var> and <i>S</i><sub>2</sub>( |<i>set</i>|, <i>k</i> ) (see <a href="CHAP017.htm#SSEC001.6">Stirling2</a>) partitions with <var>k</var> elements. <p> <a name = "SSEC002.14"></a> <li><code>NrPartitionsSet( </code><var>set</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the number of <code>PartitionsSet(</code><var>set</var><code>,</code><var>k</var><code>)</code>. <p> <pre> gap> PartitionsSet( [1,2,3] ); [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 2, 3 ] ], [ [ 1, 2 ], [ 3 ] ], [ [ 1, 2, 3 ] ], [ [ 1, 3 ], [ 2 ] ] ] gap> PartitionsSet( [1,2,3,4], 2 ); [ [ [ 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 ] ] ] gap> NrPartitionsSet( [1..6] ); 203 gap> NrPartitionsSet( [1..10], 3 ); 9330 </pre> <p> Note that <code>PartitionsSet</code> does currently not support multisets and that there is currently no ordered counterpart. <p> <a name = "SSEC002.15"></a> <li><code>Partitions( </code><var>n</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the set of all (unordered) partitions of the positive integer <var>n</var> into sums with <var>k</var> summands. If <var>k</var> is not given it returns all unordered partitions of <var>set</var> for all <var>k</var>. <p> An <strong>unordered partition</strong> is an unordered sum <i>n</i> = <i>p</i><sub>1</sub>+<i>p</i><sub>2</sub> +…+ <i>p</i><sub><i>k</i></sub> of positive integers and is represented by the list <i>p</i> = [<i>p</i><sub>1</sub>,<i>p</i><sub>2</sub>,…,<i>p</i><sub><i>k</i></sub>], in nonincreasing order, i.e., <i>p</i><sub>1</sub> > =<i>p</i><sub>2</sub> > = … > =<i>p</i><sub><i>k</i></sub>. We write <i>p</i> |- <i>n</i>. There are approximately <i>e</i><sup>π√{2/3 <i>n</i>}</sup> / 4 √3 <i>n</i> such partitions. <p> It is possible to associate with every partition of the integer <var>n</var> a conjugacy class of permutations in the symmetric group on <var>n</var> points and vice versa. Therefore <i>p</i>(<i>n</i>) : = <tt>NrPartitions</tt>(<i>n</i>) is the number of conjugacy classes of the symmetric group on <var>n</var> points. <p> Ramanujan found the identities <i>p</i>(5<i>i</i>+4) = 0 mod 5, <i>p</i>(7<i>i</i>+5) = 0 mod 7 and <i>p</i>(11<i>i</i>+6) = 0 mod 11 and many other fascinating things about the number of partitions. <p> Do not call <code>Partitions</code> with an <var>n</var> much larger than 40, in which case there are 37338 partitions, since the list will simply become too large. <p> <a name = "SSEC002.16"></a> <li><code>NrPartitions( </code><var>n</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the number of <code>Partitions(</code><var>set</var><code>,</code><var>k</var><code>)</code>. <p> <pre> gap> Partitions( 7 ); [ [ 1, 1, 1, 1, 1, 1, 1 ], [ 2, 1, 1, 1, 1, 1 ], [ 2, 2, 1, 1, 1 ], [ 2, 2, 2, 1 ], [ 3, 1, 1, 1, 1 ], [ 3, 2, 1, 1 ], [ 3, 2, 2 ], [ 3, 3, 1 ], [ 4, 1, 1, 1 ], [ 4, 2, 1 ], [ 4, 3 ], [ 5, 1, 1 ], [ 5, 2 ], [ 6, 1 ], [ 7 ] ] gap> Partitions( 8, 3 ); [ [ 3, 3, 2 ], [ 4, 2, 2 ], [ 4, 3, 1 ], [ 5, 2, 1 ], [ 6, 1, 1 ] ] gap> NrPartitions( 7 ); 15 gap> NrPartitions( 100 ); 190569292 </pre> <p> The function <code>OrderedPartitions</code> (see <a href="CHAP017.htm#SSEC002.17">OrderedPartitions</a>) is the ordered counterpart of <code>Partitions</code>. <p> <a name = "SSEC002.17"></a> <li><code>OrderedPartitions( </code><var>n</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the set of all ordered partitions of the positive integer <var>n</var> into sums with <var>k</var> summands. If <var>k</var> is not given it returns all ordered partitions of <var>set</var> for all <var>k</var>. <p> An <strong>ordered partition</strong> is an ordered sum <i>n</i> = <i>p</i><sub>1</sub> + <i>p</i><sub>2</sub> +…+ <i>p</i><sub><i>k</i></sub> of positive integers and is represented by the list [ <i>p</i><sub>1</sub>, <i>p</i><sub>2</sub>,…, <i>p</i><sub><i>k</i></sub> ]. There are totally 2<sup><i>n</i>−1</sup> ordered partitions and <br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>n</i>−1<br /><i>k</i>−1<br /></td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"></td></tr></table></td></tr></table> (see <a href="CHAP017.htm#SSEC001.2">Binomial</a>) ordered partitions with <var>k</var> summands. <p> Do not call <code>OrderedPartitions</code> with an <var>n</var> much larger than 15, the list will simply become too large. <p> <a name = "SSEC002.18"></a> <li><code>NrOrderedPartitions( </code><var>n</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the number of <code>OrderedPartitions(</code><var>set</var><code>,</code><var>k</var><code>)</code>. <p> <a name = "I10"></a> <a name = "I11"></a> <pre> gap> OrderedPartitions( 5 ); [ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 2 ], [ 1, 1, 2, 1 ], [ 1, 1, 3 ], [ 1, 2, 1, 1 ], [ 1, 2, 2 ], [ 1, 3, 1 ], [ 1, 4 ], [ 2, 1, 1, 1 ], [ 2, 1, 2 ], [ 2, 2, 1 ], [ 2, 3 ], [ 3, 1, 1 ], [ 3, 2 ], [ 4, 1 ], [ 5 ] ] gap> OrderedPartitions( 6, 3 ); [ [ 1, 1, 4 ], [ 1, 2, 3 ], [ 1, 3, 2 ], [ 1, 4, 1 ], [ 2, 1, 3 ], [ 2, 2, 2 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ], [ 4, 1, 1 ] ] gap> NrOrderedPartitions(20); 524288 </pre> <p> The function <code>Partitions</code> (see <a href="CHAP017.htm#SSEC002.15">Partitions</a>) is the unordered counterpart of <code>OrderedPartitions</code>. <p> <a name = "SSEC002.19"></a> <li><code>PartitionsGreatestLE( </code><var>n</var><code>, </code><var>m</var><code> ) F</code> <p> returns the set of all (unordered) partitions of the integer <var>n</var> having parts less or equal to the integer <var>m</var>. <p> <a name = "SSEC002.20"></a> <li><code>PartitionsGreatestEQ( </code><var>n</var><code>, </code><var>m</var><code> ) F</code> <p> returns the set of all (unordered) partitions of the integer <var>n</var> having greatest part equal to the integer <var>m</var>. <p> <a name = "SSEC002.21"></a> <li><code>RestrictedPartitions( </code><var>n</var><code>, </code><var>set</var><code> [, </code><var>k</var><code>] ) F</code> <p> In the first form <code>RestrictedPartitions</code> returns the set of all restricted partitions of the positive integer <var>n</var> into sums with <var>k</var> summands with the summands of the partition coming from the set <var>set</var>. If <var>k</var> is not given all restricted partitions for all <var>k</var> are returned. <p> A <strong>restricted partition</strong> is like an ordinary partition (see <a href="CHAP017.htm#SSEC002.15">Partitions</a>) an unordered sum <i>n</i> = <i>p</i><sub>1</sub>+<i>p</i><sub>2</sub>+…+<i>p</i><sub><i>k</i></sub> of positive integers and is represented by the list <i>p</i> = [<i>p</i><sub>1</sub>,<i>p</i><sub>2</sub>,…,<i>p</i><sub><i>k</i></sub>], in nonincreasing order. The difference is that here the <i>p</i><sub><i>i</i></sub> must be elements from the set <var>set</var>, while for ordinary partitions they may be elements from <code>[1..n]</code>. <p> <a name = "SSEC002.22"></a> <li><code>NrRestrictedPartitions( </code><var>n</var><code>, </code><var>set</var><code> [, </code><var>k</var><code>] ) F</code> <p> returns the number of <code>RestrictedPartitions(</code><var>n</var><code>,</code><var>set</var><code>,</code><var>k</var><code>)</code>. <p> <a name = "I12"></a> <pre> gap> RestrictedPartitions( 8, [1,3,5,7] ); [ [ 1, 1, 1, 1, 1, 1, 1, 1 ], [ 3, 1, 1, 1, 1, 1 ], [ 3, 3, 1, 1 ], [ 5, 1, 1, 1 ], [ 5, 3 ], [ 7, 1 ] ] gap> NrRestrictedPartitions(50,[1,2,5,10,20,50]); 451 </pre> <p> The last example tells us that there are 451 ways to return 50 pence change using 1,2,5,10,20 and 50 pence coins. <p> <a name = "SSEC002.23"></a> <li><code>SignPartition( </code><var>pi</var><code> ) F</code> <p> returns the sign of a permutation with cycle structure <var>pi</var>. <p> This function actually describes a homomorphism from the symmetric group <i>S</i><sub><i>n</i></sub> into the cyclic group of order 2, whose kernel is exactly the alternating group <i>A</i><sub><i>n</i></sub> (see <a href="CHAP040.htm#SSEC003.1">SignPerm</a>). Partitions of sign 1 are called <strong>even</strong> partitions while partitions of sign −1 are called <strong>odd</strong>. <p> <pre> gap> SignPartition([6,5,4,3,2,1]); -1 </pre> <p> <a name = "SSEC002.24"></a> <li><code>AssociatedPartition( </code><var>pi</var><code> ) F</code> <p> <code>AssociatedPartition</code> returns the associated partition of the partition <var>pi</var> which is obtained by transposing the corresponding Young diagram. <p> <pre> gap> AssociatedPartition([4,2,1]); [ 3, 2, 1, 1 ] gap> AssociatedPartition([6]); [ 1, 1, 1, 1, 1, 1 ] </pre> <p> <a name = "SSEC002.25"></a> <li><code>PowerPartition( </code><var>pi</var><code>, </code><var>k</var><code> ) F</code> <p> <code>PowerPartition</code> returns the partition corresponding to the <var>k</var>-th power of a permutation with cycle structure <var>pi</var>. <p> Each part <i>l</i> of <var>pi</var> is replaced by <i>d</i> = gcd(<i>l</i>, <i>k</i>) parts <i>l</i>/<i>d</i>. So if <var>pi</var> is a partition of <i>n</i> then <i>pi</i> <sup><i>k</i> </sup> also is a partition of <i>n</i>. <code>PowerPartition</code> describes the powermap of symmetric groups. <p> <a name = "I13"></a> <pre> gap> PowerPartition([6,5,4,3,2,1], 3); [ 5, 4, 2, 2, 2, 2, 1, 1, 1, 1 ] </pre> <p> <a name = "SSEC002.26"></a> <li><code>PartitionTuples( </code><var>n</var><code>, </code><var>r</var><code> ) F</code> <p> <code>PartitionTuples</code> returns the list of all <var>r</var>-tuples of partitions which together form a partition of <var>n</var>. <p> <var>r</var>--tuples of partitions describe the classes and the characters of wreath products of groups with <var>r</var> conjugacy classes with the symmetric group <i>S</i><sub><i>n</i></sub>. <p> <a name = "SSEC002.27"></a> <li><code>NrPartitionTuples( </code><var>n</var><code>, </code><var>r</var><code> ) F</code> <p> returns the number of <code>PartitionTuples( </code><var>n</var><code>, </code><var>r</var><code> )</code>. <p> <pre> gap> PartitionTuples(3, 2); [ [ [ 1, 1, 1 ], [ ] ], [ [ 1, 1 ], [ 1 ] ], [ [ 1 ], [ 1, 1 ] ], [ [ ], [ 1, 1, 1 ] ], [ [ 2, 1 ], [ ] ], [ [ 1 ], [ 2 ] ], [ [ 2 ], [ 1 ] ], [ [ ], [ 2, 1 ] ], [ [ 3 ], [ ] ], [ [ ], [ 3 ] ] ] </pre> <p> <p> <h2><a name="SECT003">17.3 Fibonacci and Lucas Sequences</a></h2> <p><p> <a name = "SSEC003.1"></a> <li><code>Fibonacci( </code><var>n</var><code> ) F</code> <p> returns the <var>n</var>th number of the <strong>Fibonacci sequence</strong>. The Fibonacci sequence <i>F</i><sub><i>n</i></sub> is defined by the initial conditions <i>F</i><sub>1</sub>=<i>F</i><sub>2</sub>=1 and the recurrence relation <i>F</i><sub><i>n</i>+2</sub> = <i>F</i><sub><i>n</i>+1</sub> + <i>F</i><sub><i>n</i></sub>. For negative <i>n</i> we define <i>F</i><sub><i>n</i></sub> = (−1)<sup><i>n</i>+1</sup> <i>F</i><sub>−<i>n</i></sub>, which is consistent with the recurrence relation. <p> Using generating functions one can prove that <i>F</i><sub><i>n</i></sub> = φ<sup><i>n</i></sup> − 1/φ<sup><i>n</i></sup>, where φ is (√5 + 1)/2, i.e., one root of <i>x</i><sup>2</sup> − <i>x</i> − 1 = 0. Fibonacci numbers have the property <i>Gcd</i>( <i>F</i><sub><i>m</i></sub>, <i>F</i><sub><i>n</i></sub> ) = <i>F</i><sub><i>Gcd</i>(<i>m</i>,<i>n</i>)</sub>. But a pair of Fibonacci numbers requires more division steps in Euclid's algorithm (see <a href="CHAP054.htm#SSEC007.1">Gcd</a>) than any other pair of integers of the same size. <code>Fibonacci(</code><var>k</var><code>)</code> is the special case <code>Lucas(1,-1,</code><var>k</var><code>)[1]</code> (see <a href="CHAP017.htm#SSEC003.2">Lucas</a>). <p> <a name = "I14"></a> <pre> gap> Fibonacci( 10 ); 55 gap> Fibonacci( 35 ); 9227465 gap> Fibonacci( -10 ); -55 </pre> <p> <a name = "SSEC003.2"></a> <li><code>Lucas( </code><var>P</var><code>, </code><var>Q</var><code>, </code><var>k</var><code> ) F</code> <p> returns the <var>k</var>-th values of the <strong>Lucas sequence</strong> with parameters <var>P</var> and <var>Q</var>, which must be integers, as a list of three integers. <p> Let α, β be the two roots of <i>x</i><sup>2</sup> − <i>P</i> <i>x</i> + <i>Q</i> then we define <i>Lucas</i>( <i>P</i>, <i>Q</i>, <i>k</i> )[1] = <i>U</i><sub><i>k</i></sub> = (α<sup><i>k</i></sup> − β<sup><i>k</i></sup>) / (α− β) and <i>Lucas</i>( <i>P</i>, <i>Q</i>, <i>k</i> )[2] = <i>V</i><sub><i>k</i></sub> = (α<sup><i>k</i></sup> + β<sup><i>k</i></sup>) and as a convenience <i>Lucas</i>( <i>P</i>, <i>Q</i>, <i>k</i> )[3] = <i>Q</i><sup><i>k</i></sup>. <p> The following recurrence relations are easily derived from the definition <i>U</i><sub>0</sub> = 0, <i>U</i><sub>1</sub> = 1, <i>U</i><sub><i>k</i></sub> = <i>P</i> <i>U</i><sub><i>k</i>−1</sub> − <i>Q</i> <i>U</i><sub><i>k</i>−2</sub> and <i>V</i><sub>0</sub> = 2, <i>V</i><sub>1</sub> = <i>P</i>, <i>V</i><sub><i>k</i></sub> = <i>P</i> <i>V</i><sub><i>k</i>−1</sub> − <i>Q</i> <i>V</i><sub><i>k</i>−2</sub>. Those relations are actually used to define <code>Lucas</code> if α = β. <p> Also the more complex relations used in <code>Lucas</code> can be easily derived <i>U</i><sub>2<i>k</i></sub> = <i>U</i><sub><i>k</i></sub> <i>V</i><sub><i>k</i></sub>, <i>U</i><sub>2<i>k</i>+1</sub> = (<i>P</i> <i>U</i><sub>2<i>k</i></sub> + <i>V</i><sub>2<i>k</i></sub>) / 2 and <i>V</i><sub>2<i>k</i></sub> = <i>V</i><sub><i>k</i></sub><sup>2</sup> − 2 <i>Q</i><sup><i>k</i></sup>, <i>V</i><sub>2<i>k</i>+1</sub> = ((<i>P</i><sup>2</sup>−4<i>Q</i>) <i>U</i><sub>2<i>k</i></sub> + <i>P</i> <i>V</i><sub>2<i>k</i></sub>) / 2. <p> <code>Fibonacci(</code><var>k</var><code>)</code> (see <a href="CHAP017.htm#SSEC003.1">Fibonacci</a>) is simply <code>Lucas(1,-1,</code><var>k</var><code>)[1]</code>. In an abuse of notation, the sequence <code>Lucas(1,-1,</code><var>k</var><code>)[2]</code> is sometimes called the Lucas sequence. <p> <a name = "I15"></a> <pre> gap> List( [0..10], i -> Lucas(1,-2,i)[1] ); # 2^k - (-1)^k)/3 [ 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341 ] gap> List( [0..10], i -> Lucas(1,-2,i)[2] ); # 2^k + (-1)^k [ 2, 1, 5, 7, 17, 31, 65, 127, 257, 511, 1025 ] gap> List( [0..10], i -> Lucas(1,-1,i)[1] ); # Fibonacci sequence [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ] gap> List( [0..10], i -> Lucas(2,1,i)[1] ); # the roots are equal [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] </pre> <p> <p> <h2><a name="SECT004">17.4 Permanent of a Matrix</a></h2> <p><p> <a name = "SSEC004.1"></a> <li><code>Permanent( </code><var>mat</var><code> ) F</code> <p> returns the <strong>permanent</strong> of the matrix <var>mat</var>. The permanent is defined by ∑<sub><i>p</i> ∈ <i>Symm</i>(<i>n</i>)</sub>∏<sub><i>i</i>=1</sub><sup><i>n</i></sup><i>mat</i>[<i>i</i>][<i>i</i><sup><i>p</i></sup>]. <p> Note the similarity of the definition of the permanent to the definition of the determinant (see <a href="CHAP024.htm#SSEC003.4">DeterminantMat</a>). In fact the only difference is the missing sign of the permutation. However the permanent is quite unlike the determinant, for example it is not multilinear or alternating. It has however important combinatorial properties. <p> <pre> gap> Permanent( [[0,1,1,1], > [1,0,1,1], > [1,1,0,1], > [1,1,1,0]] ); # inefficient way to compute `NrDerangements([1..4])' 9 gap> Permanent( [[1,1,0,1,0,0,0], > [0,1,1,0,1,0,0], > [0,0,1,1,0,1,0], > [0,0,0,1,1,0,1], > [1,0,0,0,1,1,0], > [0,1,0,0,0,1,1], > [1,0,1,0,0,0,1]] ); # 24 permutations fit the projective plane of order 2 24 </pre> <p> <p> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP016.htm">Previous</a>] [<a href ="CHAP018.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008 </font></body></html>