home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / combinat.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  34.5 KB  |  853 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  combinat.tex                GAP documentation            Martin Schoenert
  4. %%
  5. %A  @(#)$Id: combinat.tex,v 3.12 1993/02/19 11:30:42 gap Exp $
  6. %%
  7. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %%  This file describes the functions that mainly  deal  with  combinatorics.
  10. %%
  11. %H  $Log: combinat.tex,v $
  12. %H  Revision 3.12  1993/02/19  11:30:42  gap
  13. %H  removed overfull hboxes
  14. %H
  15. %H  Revision 3.11  1993/02/19  10:48:42  gap
  16. %H  adjustments in line length and spelling
  17. %H
  18. %H  Revision 3.10  1993/02/12  12:01:43  felsch
  19. %H  examples adjusted to line length 72
  20. %H
  21. %H  Revision 3.9  1993/02/09  13:56:41  felsch
  22. %H  examples fixed
  23. %H
  24. %H  Revision 3.8  1992/04/27  11:55:51  martin
  25. %H  replaced '\size{<set>}' with '\|<set>\|'
  26. %H
  27. %H  Revision 3.7  1992/03/27  16:17:37  martin
  28. %H  fixed the citation
  29. %H
  30. %H  Revision 3.6  1992/03/13  14:57:45  goetz
  31. %H  added some functions from 'charsymm.tex'.
  32. %H
  33. %H  Revision 3.5  1991/12/27  16:07:04  martin
  34. %H  revised everything for GAP 3.1 manual
  35. %H
  36. %H  Revision 3.4  1991/07/22  14:52:20  martin
  37. %H  added 'RestrictedPartitions'
  38. %H
  39. %H  Revision 3.3  1991/07/21  12:01:00  martin
  40. %H  changed 'Partitions' to return partitions in standard form
  41. %H
  42. %H  Revision 3.2  1991/07/01  13:00:00  martin
  43. %H  added 'Bell'
  44. %H
  45. %H  Revision 3.1  1991/06/28  11:22:00  martin
  46. %H  fixed some minor typos
  47. %H
  48. %H  Revision 3.0  1991/04/11  11:28:53  martin
  49. %H  Initial revision under RCS
  50. %H
  51. %%
  52. \Chapter{Combinatorics}%
  53. \index{selections}\index{partitions}
  54.  
  55. This chapter  describes the functions that   deal with combinatorics.  We
  56. mainly concentrate on two areas.  One  is about *selections*, that is the
  57. ways one   can  select   elements from  a   set.    The  other  is  about
  58. *partitions*, that is the ways one can partition a set  into the union of
  59. pairwise disjoint subsets.
  60.  
  61. First  this package contains  various  functions that are related  to the
  62. number of  selections from a set  (see "Factorial", "Binomial") or to the
  63. number  of  partitions of a  set  (see "Bell", "Stirling1", "Stirling2").
  64. Those numbers satisfy literally thousands of identities,  which  we do no
  65. mention in this document, for a thorough treatment see \cite{GKP90}.
  66.  
  67. Then this package contains functions to compute the selections from a set
  68. (see "Combinations"),  ordered selections, i.e.,   selections where   the
  69. order in which you select the elements is important (see "Arrangements"),
  70. selections with repetitions,  i.e., you  are allowed to   select the same
  71. element more than once  (see  "UnorderedTuples") and  ordered  selections
  72. with repetitions (see "Tuples").
  73.  
  74. As special  cases of ordered  combinations there are functions to compute
  75. all permutations (see "PermutationsList"),  all fixpointfree permutations
  76. (see "Derangements") of a list and the number of permutations  that fit a
  77. given 1-0 matrix (see "Permanent").
  78.  
  79. This package also contains functions to  compute partitions of a set (see
  80. "PartitionsSet"), partitions of  an integer  into   the sum of   positive
  81. integers      (see    "Partitions",  "RestrictedPartitions") and  ordered
  82. partitions of  an  integer  into   the  sum  of positive integers    (see
  83. "OrderedPartitions").
  84.  
  85. Finally this package  also contains  some  miscellaneous  functions  (see
  86. "Fibonacci", "Lucas" and "Bernoulli").
  87.  
  88. All these functions are in the file '\"LIBNAME/combinat.g\"'.
  89.  
  90. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  91. \Section{Factorial}
  92.  
  93. 'Factorial( <n> )'
  94.  
  95. 'Factorial'  returns the *factorial*  $n!$  of the positive  integer <n>,
  96. which is defined as the product $1 \* 2 \* 3 \* .. \* n$.
  97.  
  98. $n!$ is the  number of permutations of a set of $n$ elements.  $1/n!$  is
  99. the coefficient  of  $x^n$  in  the  formal series  $e^x$, which  is  the
  100. generating function for factorial.
  101.  
  102. |    gap> List( [0..10], Factorial );
  103.     [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ]
  104.     gap> Factorial( 30 );
  105.     265252859812191058636308480000000 |
  106.  
  107. 'PermutationsList'  (see   "PermutationsList") computes  the  set  of all
  108. permutations of a list.
  109.  
  110. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  111. \Section{Binomial}%
  112. \index{coefficient!binomial}\index{number!binomial}
  113.  
  114. 'Binomial( <n>, <k> )'
  115.  
  116. 'Binomial' returns the *binomial coefficient* ${n \choose k}$ of integers
  117. <n> and <k>, which  is defined as $n!  / (k!  (n-k)!)$ (see "Factorial").
  118. We define ${0 \choose 0} = 1$, ${n \choose  k} = 0$  if $k\<0$ or $n\<k$,
  119. and ${n \choose k} = (-1)^k {-n+k-1  \choose  k}$ if  $n \<  0$, which is
  120. consistent with ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$.
  121.  
  122. ${n \choose k}$ is the number of combinations with  $k$  elements,  i.e.,
  123. the number of subsets with $k$ elements, of  a  set  with  $n$  elements.
  124. ${n \choose k}$  is the coefficient of the  term $x^k$ of the  polynomial
  125. $(x + 1)^n$, which is the generating function for ${n \choose \*}$, hence
  126. the name.
  127.  
  128. |    gap> List( [0..4], k->Binomial( 4, k ) );
  129.     [ 1, 4, 6, 4, 1 ]    # Knuth calls this the trademark of Binomial
  130.     gap> List( [0..6], n->List( [0..6], k->Binomial( n, k ) ) );;
  131.     gap> PrintArray( last );
  132.     [ [   1,   0,   0,   0,   0,   0,   0 ],    # the lower triangle is
  133.       [   1,   1,   0,   0,   0,   0,   0 ],    # called Pascal\'s triangle
  134.       [   1,   2,   1,   0,   0,   0,   0 ],
  135.       [   1,   3,   3,   1,   0,   0,   0 ],
  136.       [   1,   4,   6,   4,   1,   0,   0 ],
  137.       [   1,   5,  10,  10,   5,   1,   0 ],
  138.       [   1,   6,  15,  20,  15,   6,   1 ] ]
  139.     gap> Binomial( 50, 10 );
  140.     10272278170 |
  141.  
  142. 'NrCombinations' (see "Combinations") is the generalization of 'Binomial'
  143. for multisets.  'Combinations' (see "Combinations")  computes the set  of
  144. all combinations of a multiset.
  145.  
  146. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  147. \Section{Bell}%
  148. \index{number!Bell}
  149.  
  150. 'Bell( <n> )'
  151.  
  152. 'Bell' returns the *Bell number* $B(n)$.  The Bell numbers are defined by
  153. $B(0)=1$ and the recurrence $B(n+1) = \sum_{k=0}^{n}{{n \choose k}B(k)}$.
  154.  
  155. $B(n)$ is the  number of ways to  partition a  set of <n>   elements into
  156. pairwise disjoint  nonempty subsets  (see "PartitionsSet").  This implies
  157. of  course that   $B(n) =  \sum_{k=0}^{n}{S_2(n,k)}$  (see  "Stirling2").
  158. $B(n)/n!$ is the coefficient of  $x^n$ in the formal series  $e^{e^x-1}$,
  159. which is the generating function for $B(n)$.
  160.  
  161. |    gap> List( [0..6], n -> Bell( n ) );
  162.     [ 1, 1, 2, 5, 15, 52, 203 ]
  163.     gap> Bell( 14 );
  164.     190899322 |
  165.  
  166. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  167. \Section{Stirling1}%
  168. \index{Stirling number of the first kind}%
  169. \index{number!Stirling, of the first kind}
  170.  
  171. 'Stirling1( <n>, <k> )'
  172.  
  173. 'Stirling1' returns the *Stirling number of the first kind* $S_1(n,k)$ of
  174. the integers <n> and <k>.  Stirling numbers of the first kind are defined
  175. by $S_1(0,0)  = 1$, $S_1(n,0) =  S_1(0,k) = 0$  if  $n, k \<> 0$  and the
  176. recurrence $S_1(n,k) = (n-1) S_1(n-1,k) + S_1(n-1,k-1)$.
  177.  
  178. $S_1(n,k)$ is the number  of permutations of  <n> points with <k> cycles.
  179. Stirling numbers of  the first kind  appear as coefficients in the series
  180. $n! {x \choose n} = \sum_{k=0}^{n}{S_1(n,k) x^k}$ which is the generating
  181. function for Stirling numbers of the first kind.  Note  the similarity to
  182. $x^n =  \sum_{k=0}^{n}{S_2(n,k) k!  {x  \choose k}}$  (see  "Stirling2").
  183. Also the definition of $S_1$ implies $S_1(n,k) = S_2(-k,-n)$ if $n,k\<0$.
  184. There are  many  formulae relating Stirling numbers of  the first kind to
  185. Stirling numbers of the second kind, Bell numbers, and Binomial numbers.
  186.  
  187. |    gap> List( [0..4], k->Stirling1( 4, k ) );
  188.     [ 0, 6, 11, 6, 1 ]    # Knuth calls this the trademark of $S_1$
  189.     gap> List( [0..6], n->List( [0..6], k->Stirling1( n, k ) ) );;
  190.     gap> PrintArray( last );
  191.     [ [    1,    0,    0,    0,    0,    0,    0 ],    # Note the similarity
  192.       [    0,    1,    0,    0,    0,    0,    0 ],    # with Pascal\'s
  193.       [    0,    1,    1,    0,    0,    0,    0 ],    # triangle for the
  194.       [    0,    2,    3,    1,    0,    0,    0 ],    # Binomial numbers
  195.       [    0,    6,   11,    6,    1,    0,    0 ],
  196.       [    0,   24,   50,   35,   10,    1,    0 ],
  197.       [    0,  120,  274,  225,   85,   15,    1 ] ]
  198.     gap> Stirling1(50,10);
  199.     101623020926367490059043797119309944043405505380503665627365376 |
  200.  
  201. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  202. \Section{Stirling2}%
  203. \index{Stirling number of the second kind}%
  204. \index{number!Stirling, of the second kind}
  205.  
  206. 'Stirling2( <n>, <k> )'
  207.  
  208. 'Stirling2' returns the *Stirling number of  the  second kind* $S_2(n,k)$
  209. of the integers <n>  and <k>.  Stirling  numbers  of the second  kind are
  210. defined by $S_2(0,0) = 1$, $S_2(n,0) = S_2(0,k) = 0$ if $n,  k \<> 0$ and
  211. the recurrence $S_2(n,k) = k S_2(n-1,k) + S_2(n-1,k-1)$.
  212.  
  213. $S_2(n,k)$ is the number of ways to partition a set of <n>  elements into
  214. <k> pairwise disjoint nonempty  subsets  (see "PartitionsSet").  Stirling
  215. numbers of the second kind  appear as  coefficients  in the  expansion of
  216. $x^n = \sum_{k=0}^{n}{S_2(n,k) k!  {x  \choose k}}$.  Note the similarity
  217. to $n! {x \choose  n} = \sum_{k=0}^{n}{S_1(n,k) x^k}$ (see  "Stirling1").
  218. Also the definition of $S_2$ implies $S_2(n,k) = S_1(-k,-n)$ if $n,k\<0$.
  219. There are many formulae relating  Stirling numbers of  the second kind to
  220. Stirling numbers of the first kind, Bell numbers, and Binomial numbers.
  221.  
  222. |    gap> List( [0..4], k->Stirling2( 4, k ) );
  223.     [ 0, 1, 7, 6, 1 ]    # Knuth calls this the trademark of $S_2$
  224.     gap> List( [0..6], n->List( [0..6], k->Stirling2( n, k ) ) );;
  225.     gap> PrintArray( last );
  226.     [ [   1,   0,   0,   0,   0,   0,   0 ],    # Note the similarity with
  227.       [   0,   1,   0,   0,   0,   0,   0 ],    # Pascal\'s triangle for
  228.       [   0,   1,   1,   0,   0,   0,   0 ],    # the Binomial numbers
  229.       [   0,   1,   3,   1,   0,   0,   0 ],
  230.       [   0,   1,   7,   6,   1,   0,   0 ],
  231.       [   0,   1,  15,  25,  10,   1,   0 ],
  232.       [   0,   1,  31,  90,  65,  15,   1 ] ]
  233.     gap> Stirling2( 50, 10 );
  234.     26154716515862881292012777396577993781727011 |
  235.  
  236. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  237. \Section{Combinations}%
  238. \index{NrCombinations}\index{powerset}\index{subsets}
  239.  
  240. 'Combinations( <mset> )' \\
  241. 'Combinations( <mset>, <k> )'
  242.  
  243. 'NrCombinations( <mset> )' \\
  244. 'NrCombinations( <mset>, <k> )'
  245.  
  246. In the  first form 'Combinations' returns the  set of all combinations of
  247. the multiset  <mset>.  In the  second form 'Combinations' returns the set
  248. of all combinations of the multiset <mset> with <k> elements.
  249.  
  250. In the first form 'NrCombinations'  returns the number of combinations of
  251. the multiset  <mset>.   In the  second form  'NrCombinations' returns the
  252. number of combinations of the multiset <mset> with <k> elements.
  253.  
  254. A *combination* of  <mset> is an  unordered selection without repetitions
  255. and is represented by a sorted sublist of <mset>.   If <mset> is a proper
  256. set, there  are  ${\|mset\| \choose  k}$  (see  "Binomial")  combinations
  257. with <k> elements, and the set of all combinations is just the *powerset*
  258. of <mset>, which contains all   *subsets* of <mset>  and has  cardinality
  259. $2^{\|mset\|}$.
  260.  
  261. |    gap> Combinations( [1,2,2,3] );
  262.     [ [  ], [ 1 ], [ 1, 2 ], [ 1, 2, 2 ], [ 1, 2, 2, 3 ], [ 1, 2, 3 ],
  263.       [ 1, 3 ], [ 2 ], [ 2, 2 ], [ 2, 2, 3 ], [ 2, 3 ], [ 3 ] ]
  264.     gap> NrCombinations( [1..52], 5 );
  265.     2598960    # number of different hands in a game of poker |
  266.  
  267. The   function 'Arrangements'   (see  "Arrangements")   computes  ordered
  268. selections without repetitions, 'UnorderedTuples' (see "UnorderedTuples")
  269. computes  unordered  selections  with   repetitions  and 'Tuples'    (see
  270. "Tuples") computes ordered selections with repetitions.
  271.  
  272. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  273. \Section{Arrangements}
  274.  
  275. 'Arrangements( <mset> )' \\
  276. 'Arrangements( <mset>, <k> )'
  277.  
  278. 'NrArrangements( <mset> )' \\
  279. 'NrArrangements( <mset>, <k> )'
  280.  
  281. In the first form  'Arrangements' returns the  set of arrangements of the
  282. multiset  <mset>.   In the second  form 'Arrangements' returns the set of
  283. all arrangements with <k> elements of the multiset <mset>.
  284.  
  285. In the first form 'NrArrangements' returns the  number of arrangements of
  286. the  multiset <mset>.   In  the second form  'NrArrangements' returns the
  287. number of arrangements with <k> elements of the multiset <mset>.
  288.  
  289. An  *arrangement* of <mset>  is an ordered selection  without repetitions
  290. and is represented by a list that contains only elements from <mset>, but
  291. maybe  in a different  order.   If <mset>  is  a proper  set   there  are
  292. $\|mset\|!  /  (\|mset\|-k)!$ (see  "Factorial")  arrangements  with  <k>
  293. elements.
  294.  
  295. As an example of arrangements of a multiset, think  of the game Scrabble.
  296. Suppose you have the six characters of the word 'settle'  and you have to
  297. make a four letter word.  Then the possibilities are given by
  298.  
  299. |    gap> Arrangements( ["s","e","t","t","l","e"], 4 );
  300.     [ [ "e", "e", "l", "s" ], [ "e", "e", "l", "t" ],
  301.       [ "e", "e", "s", "l" ], [ "e", "e", "s", "t" ],
  302.       # 96 more possibilities
  303.       [ "t", "t", "s", "e" ], [ "t", "t", "s", "l" ] ] |
  304.  
  305. Can you find the five proper English words, where 'lets' does  not count?
  306. Note that the fact that the  list  returned by 'Arrangements' is a proper
  307. set means in this example that the possibilities are  listed in  the same
  308. order as they appear in the dictionary.
  309.  
  310. |    gap> NrArrangements( ["s","e","t","t","l","e"] );
  311.     523 |
  312.  
  313. The   function  'Combinations'  (see  "Combinations")  computes unordered
  314. selections without repetitions, 'UnorderedTuples' (see "UnorderedTuples")
  315. computes  unordered   selections  with   repetitions  and  'Tuples'  (see
  316. "Tuples") computes ordered selections with repetitions.
  317.  
  318. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  319. \Section{UnorderedTuples}%
  320. \index{NrUnorderedTuples}
  321.  
  322. 'UnorderedTuples( <set>, <k> )'
  323.  
  324. 'NrUnorderedTuples( <set>, <k> )'
  325.  
  326. 'UnorderedTuples' returns the  set of all  unordered tuples of length <k>
  327. of the set <set>.
  328.  
  329. 'NrUnorderedTuples' returns the number of unordered  tuples of length <k>
  330. of the set <set>.
  331.  
  332. An *unordered tuple* of length <k> of <set> is a unordered selection with
  333. repetitions  of <set> and  is represented by a sorted  list of length <k>
  334. containing  elements  from  <set>.   There  are ${\|set\|+k-1 \choose k}$
  335. (see "Binomial") such unordered tuples.
  336.  
  337. Note that the fact that 'UnOrderedTuples' returns a set  implies that the
  338. last  index runs   fastest.   That means the   first  tuple  contains the
  339. smallest element from <set>   <k> times,  the  second tuple  contains the
  340. smallest element of <set> at all  positions except at the last positions,
  341. where it contains the second smallest element from <set> and so on.
  342.  
  343. As an example for unordered tuples think of a poker-like game played with
  344. 5 dices.  Then each possible hand corresponds to an  unordered five-tuple
  345. from the set [1..6]
  346.  
  347. |    gap> NrUnorderedTuples( [1..6], 5 );
  348.     252
  349.     gap> UnorderedTuples( [1..6], 5 );
  350.     [ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 1, 2 ], [ 1, 1, 1, 1, 3 ],
  351.       [ 1, 1, 1, 1, 4 ], [ 1, 1, 1, 1, 5 ], [ 1, 1, 1, 1, 6 ],
  352.       # 99 more tuples
  353.       [ 1, 3, 4, 5, 6 ], [ 1, 3, 4, 6, 6 ], [ 1, 3, 5, 5, 5 ],
  354.       # 99 more tuples
  355.       [ 3, 3, 4, 4, 5 ], [ 3, 3, 4, 4, 6 ], [ 3, 3, 4, 5, 5 ],
  356.       # 39 more tuples
  357.       [ 5, 5, 6, 6, 6 ], [ 5, 6, 6, 6, 6 ], [ 6, 6, 6, 6, 6 ] ] |
  358.  
  359. The function  'Combinations'  (see  "Combinations")   computes  unordered
  360. selections  without  repetitions,    'Arrangements' (see  "Arrangements")
  361. computes ordered   selections without  repetitions   and   'Tuples'  (see
  362. "Tuples") computes ordered selections with repetitions.
  363.  
  364. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  365. \Section{Tuples}%
  366. \index{NrTuples}
  367.  
  368. 'Tuples( <set>, <k> )'
  369.  
  370. 'NrTuples( <set>, <k> )'
  371.  
  372. 'Tuples' returns the set of all ordered tuples  of length <k> of  the set
  373. <set>.
  374.  
  375. 'NrTuples' returns the number of all ordered tuples  of length <k> of the
  376. set <set>.
  377.  
  378. An *ordered tuple* of  length <k> of <set> is  an ordered selection  with
  379. repetition and is represented by a list of length <k> containing elements
  380. of <set>.  There are $\|set\|^k$ such ordered tuples.
  381.  
  382. Note that the fact  that 'Tuples' returns  a  set implies that   the last
  383. index runs  fastest.  That means  the first tuple   contains the smallest
  384. element from <set> <k>  times,  the  second tuple  contains the  smallest
  385. element of <set> at all positions except at the  last positions, where it
  386. contains the second smallest element from <set> and so on.
  387.  
  388. |    gap> Tuples( [1,2,3], 2 );
  389.     [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], 
  390.       [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ]
  391.     gap> NrTuples( [1..10], 5 );
  392.     100000 |
  393.  
  394. 'Tuples(<set>,<k>)' can also be viewed  as the <k>-fold cartesian product
  395. of <set> (see "Cartesian").
  396.  
  397. The  function  'Combinations'  (see  "Combinations")  computes  unordered
  398. selections  without   repetitions,  'Arrangements'  (see  "Arrangements")
  399. computes ordered selections without repetitions, and finally the function
  400. 'UnorderedTuples' (see "UnorderedTuples")  computes unordered  selections
  401. with repetitions.
  402.  
  403. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  404. \Section{PermutationsList}%
  405. \index{NrPermutationsList}\index{permutations!list}
  406.  
  407. 'PermutationsList( <mset> )'
  408.  
  409. 'NrPermutationsList( <mset> )'
  410.  
  411. 'PermutationsList' returns the   set   of permutations of    the multiset
  412. <mset>.
  413.  
  414. 'NrPermutationsList' returns the  number of permutations  of the multiset
  415. <mset>.
  416.  
  417. A *permutation* is represented by a  list  that contains exactly the same
  418. elements as  <mset>,  but possibly in   different order.  If <mset>  is a
  419. proper  set there are $\|mset\| !$ (see "Factorial")  such  permutations.
  420. Otherwise if the  first elements appears $k_1$  times, the second element
  421. appears  $k_2$  times   and   so  on,  the  number   of   permutations is
  422. $\|mset\|! /  (k_1! k_2! ..)$,  which  is  sometimes  called  multinomial
  423. coefficient.
  424.  
  425. |    gap> PermutationsList( [1,2,3] );
  426.     [ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ],
  427.       [ 3, 2, 1 ] ]
  428.     gap> PermutationsList( [1,1,2,2] );
  429.     [ [ 1, 1, 2, 2 ], [ 1, 2, 1, 2 ], [ 1, 2, 2, 1 ], [ 2, 1, 1, 2 ],
  430.       [ 2, 1, 2, 1 ], [ 2, 2, 1, 1 ] ]
  431.     gap> NrPermutationsList( [1,2,2,3,3,3,4,4,4,4] );
  432.     12600 |
  433.  
  434. The function 'Arrangements' (see "Arrangements") is the generalization of
  435. 'PermutationsList'   that  allows  you  to specify   the  size   of   the
  436. permutations.  'Derangements' (see "Derangements") computes  permutations
  437. that have no fixpoints.
  438.  
  439. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  440. \Section{Derangements}%
  441. \index{NrDerangements}\index{permutations!fixpointfree}
  442.  
  443. 'Derangements( <list> )'
  444.  
  445. 'NrDerangements( <list> )'
  446.  
  447. 'Derangements' returns the set of all derangements of the list <list>.
  448.  
  449. 'NrDerangements' returns the number of derangements of the list <list>.
  450.  
  451. A   *derangement* is  a   fixpointfree  permutation  of   <list>   and is
  452. represented by a list that contains exactly the  same elements as <list>,
  453. but in such  an order  that the  derangement has at  no position the same
  454. element as  <list>.  If the  list  <list> contains no element twice there
  455. are  exactly  $\|list\|!  (1/2!   -  1/3!    +  1/4!  -  ..   (-1)^n/n!)$
  456. derangements.
  457.  
  458. Note that the  ratio 'NrPermutationsList([1..n])/NrDerangements([1..n])',
  459. which  is  $n!  /  (n!   (1/2!  -  1/3!  + 1/4!  - .. (-1)^n/n!))$  is an
  460. approximation for the base of the natural logarithm  $e =  2.7182818285$,
  461. which is correct to about $n$ digits.
  462.  
  463. As an  example of  derangements suppose    that  you have  to  send  four
  464. different letters  to   four  different  people.    Than  a   derangement
  465. corresponds  to a way  to send those letters such  that no letter reaches
  466. the intended person.
  467.  
  468. |    gap> Derangements( [1,2,3,4] );
  469.     [ [ 2, 1, 4, 3 ], [ 2, 3, 4, 1 ], [ 2, 4, 1, 3 ], [ 3, 1, 4, 2 ],
  470.       [ 3, 4, 1, 2 ], [ 3, 4, 2, 1 ], [ 4, 1, 2, 3 ], [ 4, 3, 1, 2 ],
  471.       [ 4, 3, 2, 1 ] ]
  472.     gap> NrDerangements( [1..10] );
  473.     1334961
  474.     gap> Int( 10^7*NrPermutationsList([1..10])/last );
  475.     27182816
  476.     gap> Derangements( [1,1,2,2,3,3] );
  477.     [ [ 2, 2, 3, 3, 1, 1 ], [ 2, 3, 1, 3, 1, 2 ], [ 2, 3, 1, 3, 2, 1 ],
  478.       [ 2, 3, 3, 1, 1, 2 ], [ 2, 3, 3, 1, 2, 1 ], [ 3, 2, 1, 3, 1, 2 ],
  479.       [ 3, 2, 1, 3, 2, 1 ], [ 3, 2, 3, 1, 1, 2 ], [ 3, 2, 3, 1, 2, 1 ],
  480.       [ 3, 3, 1, 1, 2, 2 ] ]
  481.     gap> NrDerangements( [1,2,2,3,3,3,4,4,4,4] );
  482.     338 |
  483.  
  484. The function  'PermutationsList'  (see  "PermutationsList")  computes all
  485. permutations of a list.
  486.  
  487. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  488. \Section{Permanent}
  489.  
  490. 'Permanent( <mat> )'
  491.  
  492. 'Permanent' returns the *permanent* of the matrix  <mat>.  The  permanent
  493. is defined by $\sum_{p \in Symm(n)}{\prod_{i=1}^{n}{mat[i][i^p]}}$.
  494.  
  495. Note the similarity of the definition of  the permanent to the definition
  496. of the determinant.  In  fact the only  difference is the missing sign of
  497. the permutation.  However the  permanent is quite unlike the determinant,
  498. for example   it is  not  multilinear or  alternating.  It   has  however
  499. important combinatorical properties.
  500.  
  501. |    gap> Permanent( [[0,1,1,1],
  502.     >                [1,0,1,1],
  503.     >                [1,1,0,1],
  504.     >                [1,1,1,0]] );
  505.     9    # inefficient way to compute 'NrDerangements([1..4])'
  506.     gap> Permanent( [[1,1,0,1,0,0,0],
  507.     >                [0,1,1,0,1,0,0],
  508.     >                [0,0,1,1,0,1,0],
  509.     >                [0,0,0,1,1,0,1],
  510.     >                [1,0,0,0,1,1,0],
  511.     >                [0,1,0,0,0,1,1],
  512.     >                [1,0,1,0,0,0,1]] );
  513.     24    # 24 permutations fit the projective plane of order 2 |
  514.  
  515. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  516. \Section{PartitionsSet}%
  517. \index{NrPartitionsSet}\index{partitions!of a set}
  518.  
  519. 'PartitionsSet( <set> )' \\
  520. 'PartitionsSet( <set>, <k> )'
  521.  
  522. 'NrPartitionsSet( <set> )' \\
  523. 'NrPartitionsSet( <set>, <k> )'
  524.  
  525. In  the first  form  'PartitionsSet'  returns the  set  of  all unordered
  526. partitions of the set <set>.   In the second form 'PartitionsSet' returns
  527. the set of  all unordered partitions of the  set <set> into  <k> pairwise
  528. disjoint nonempty sets.
  529.  
  530. In  the first  form  'NrPartitionsSet' returns   the number of  unordered
  531. partitions of   the  set <set>.   In  the  second  form 'NrPartitionsSet'
  532. returns  the number of  unordered  partitions of  the  set <set> into <k>
  533. pairwise disjoint nonempty sets.
  534.  
  535. An *unordered partition* of <set> is  a set of pairwise disjoint nonempty
  536. sets with union <set>  and is represented by  a sorted list of such sets.
  537. There are $B( \|set\| )$ (see "Bell") partitions of  the  set  <set>  and
  538. $S_2( \|set\|, k )$ (see "Stirling2") partitions with <k> elements.
  539.  
  540. |    gap> PartitionsSet( [1,2,3] );
  541.     [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 2, 3 ] ], [ [ 1, 2 ], [ 3 ] ],
  542.       [ [ 1, 2, 3 ] ], [ [ 1, 3 ], [ 2 ] ] ]
  543.     gap> PartitionsSet( [1,2,3,4], 2 );
  544.     [ [ [ 1 ], [ 2, 3, 4 ] ], [ [ 1, 2 ], [ 3, 4 ] ],
  545.       [ [ 1, 2, 3 ], [ 4 ] ], [ [ 1, 2, 4 ], [ 3 ] ],
  546.       [ [ 1, 3 ], [ 2, 4 ] ], [ [ 1, 3, 4 ], [ 2 ] ],
  547.       [ [ 1, 4 ], [ 2, 3 ] ] ]
  548.     gap> NrPartitionsSet( [1..6] );
  549.     203
  550.     gap> NrPartitionsSet( [1..10], 3 );
  551.     9330 |
  552.  
  553. Note  that 'PartitionsSet' does currently  not support multisets and that
  554. there is currently no ordered counterpart.
  555.  
  556. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  557. \Section{Partitions}%
  558. \index{NrPartitions}\index{partitions!of an integer}
  559.  
  560. 'Partitions( <n> )' \\
  561. 'Partitions( <n>, <k> )'
  562.  
  563. 'NrPartitions( <n> )' \\
  564. 'NrPartitions( <n>, <k> )'
  565.  
  566. In  the  first  form 'Partitions'   returns  the set  of all  (unordered)
  567. partitions of the positive integer  <n>.  In the second form 'Partitions'
  568. returns the set of all (unordered) partitions of the positive integer <n>
  569. into sums with <k> summands.
  570.  
  571. In   the first form  'NrPartitions'  returns   the number of  (unordered)
  572. partitions    of  the   positive integer   <n>.     In   the second  form
  573. 'NrPartitions' returns the     number of (unordered) partitions  of   the
  574. positive integer <n> into sums with <k> summands.
  575.  
  576. An *unordered partition* is an  unordered sum $n =  p_1+p_2 +..+ p_k$  of
  577. positive integers and is represented by the list  $p = [p_1,p_2,..,p_k]$,
  578. in nonincreasing order, i.e., $p_1>=p_2>=..>=p_k$.  We write $p\vdash n$.
  579. There   are approximately $E^{\pi \sqrt{2/3 n}}    / {4 \sqrt{3} n}$ such
  580. partitions.
  581.  
  582. It  is possible to  associate with every partition  of the integer  <n> a
  583. conjugacy class of permutations in the symmetric group on <n>  points and
  584. vice  versa.   Therefore $p(n) \:=   NrPartitions(n)$  is  the  number of
  585. conjugacy classes of the symmetric group on <n> points.
  586.  
  587. Ramanujan found the identities $p(5i+4) = 0$ mod 5, $p(7i+5) = 0$  mod  7
  588. and  $p(11i+6) = 0$ mod 11 and many  other  fascinating  things about the
  589. number of partitions.
  590.  
  591. Do not call 'Partitions' with an <n> much larger than 40, in  which  case
  592. there are 37338 partitions, since the list will simply become too large.
  593.  
  594. |    gap> Partitions( 7 );
  595.     [ [ 1, 1, 1, 1, 1, 1, 1 ], [ 2, 1, 1, 1, 1, 1 ], [ 2, 2, 1, 1, 1 ],
  596.       [ 2, 2, 2, 1 ], [ 3, 1, 1, 1, 1 ], [ 3, 2, 1, 1 ], [ 3, 2, 2 ],
  597.       [ 3, 3, 1 ], [ 4, 1, 1, 1 ], [ 4, 2, 1 ], [ 4, 3 ], [ 5, 1, 1 ],
  598.       [ 5, 2 ], [ 6, 1 ], [ 7 ] ]
  599.     gap> Partitions( 8, 3 );
  600.     [ [ 3, 3, 2 ], [ 4, 2, 2 ], [ 4, 3, 1 ], [ 5, 2, 1 ], [ 6, 1, 1 ] ]
  601.     gap> NrPartitions( 7 );
  602.     15
  603.     gap> NrPartitions( 100 );
  604.     190569292 |
  605.  
  606. The function 'OrderedPartitions' (see "OrderedPartitions") is the ordered
  607. counterpart of 'Partitions'.
  608.  
  609. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  610. \Section{OrderedPartitions}%
  611. \index{NrOrderedPartitions}%
  612. \index{partitions!ordered, of an integer}%
  613. \index{partitions!improper, of an integer}%
  614.  
  615. 'OrderedPartitions( <n> )' \\
  616. 'OrderedPartitions( <n>, <k> )'
  617.  
  618. 'NrOrderedPartitions( <n> )' \\
  619. 'NrOrderedPartitions( <n>, <k> )'
  620.  
  621. In the  first  form 'OrderedPartitions'  returns the  set  of all ordered
  622. partitions  of  the  positive    integer  <n>.    In  the   second   form
  623. 'OrderedPartitions' returns the  set  of  all ordered partitions  of  the
  624. positive integer <n> into sums with <k> summands.
  625.  
  626. In the first form  'NrOrderedPartitions'  returns the number of   ordered
  627. partitions  of  the   positive   integer   <n>.   In the    second   form
  628. 'NrOrderedPartitions' returns  the number  of ordered  partitions  of the
  629. positive integer <n> into sums with <k> summands.
  630.  
  631. An *ordered partition* is an ordered sum $n = p_1 + p_2 + ..   +  p_k$ of
  632. positive integers and is represented by the list $[ p_1, p_2, .., p_k ]$.
  633. There are  totally $2^{n-1}$ ordered  partitions  and ${n-1 \choose k-1}$
  634. (see "Binomial") partitions with <k> summands.
  635.  
  636. Do not call 'OrderedPartitions' with an <n>  larger  than  15,  the  list
  637. will simply become too large.
  638.  
  639. |    gap> OrderedPartitions( 5 );
  640.     [ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 2 ], [ 1, 1, 2, 1 ], [ 1, 1, 3 ],
  641.       [ 1, 2, 1, 1 ], [ 1, 2, 2 ], [ 1, 3, 1 ], [ 1, 4 ], [ 2, 1, 1, 1 ],
  642.       [ 2, 1, 2 ], [ 2, 2, 1 ], [ 2, 3 ], [ 3, 1, 1 ], [ 3, 2 ], 
  643.       [ 4, 1 ], [ 5 ] ]
  644.     gap> OrderedPartitions( 6, 3 );
  645.     [ [ 1, 1, 4 ], [ 1, 2, 3 ], [ 1, 3, 2 ], [ 1, 4, 1 ], [ 2, 1, 3 ],
  646.       [ 2, 2, 2 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ], [ 4, 1, 1 ] ]
  647.     gap> NrOrderedPartitions(20);
  648.     524288 |
  649.  
  650. The function 'Partitions' (see "Partitions") is the unordered counterpart
  651. of 'OrderedPartitions'.
  652.  
  653. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  654. \Section{RestrictedPartitions}%
  655. \index{NrRestrictedPartitions}%
  656. \index{partitions!restricted, of an integer}
  657.  
  658. 'RestrictedPartitions( <n>, <set> )' \\
  659. 'RestrictedPartitions( <n>, <set>, <k> )'
  660.  
  661. 'NrRestrictedPartitions( <n>, <set> )' \\
  662. 'NrRestrictedPartitions( <n>, <set>, <k> )'
  663.  
  664. In the   first  form  'RestrictedPartitions'   returns   the set   of all
  665. restricted  partitions of the positive integer  <n>  with the summands of
  666. the   partition  coming  from the    set  <set>.   In    the second  form
  667. 'RestrictedPartitions' returns the set of all  partitions of the positive
  668. integer <n> into   sums  with <k>  summands   with the summands  of   the
  669. partition coming from the set <set>.
  670.  
  671. In  the first  form    'NrRestrictedPartitions'  returns the  number   of
  672. restricted partitions of  the   positive integer <n>  with  the  summands
  673. coming from the  set <set>.  In  the second form 'NrRestrictedPartitions'
  674. returns the number of restricted  partitions of the positive integer  <n>
  675. into sums  with <k> summands  with the  summands  of the partition coming
  676. from the set <set>.
  677.  
  678. A *restricted partition* is like an ordinary partition (see "Partitions")
  679. an  unordered  sum $n =  p_1+p_2 +..+  p_k$ of  positive  integers and is
  680. represented by the list  $p =  [p_1,p_2,..,p_k]$, in nonincreasing order.
  681. The difference is that  here  the $p_i$ must   be elements from the   set
  682. <set>, while for ordinary partitions they may be elements from '[1..n]'.
  683.  
  684. |    gap> RestrictedPartitions( 8, [1,3,5,7] );
  685.     [ [ 1, 1, 1, 1, 1, 1, 1, 1 ], [ 3, 1, 1, 1, 1, 1 ], [ 3, 3, 1, 1 ],
  686.       [ 5, 1, 1, 1 ], [ 5, 3 ], [ 7, 1 ] ]
  687.     gap> NrRestrictedPartitions( 50, [1,5,10,25,50] );
  688.     50 |
  689.  
  690. The last example tells us that there are 50 ways to return 50 cent change
  691. using 1, 5, 10 cent coins, quarters and halfdollars.
  692.  
  693. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  694. \Section{SignPartition}
  695.  
  696. 'SignPartition( <pi> )'
  697.  
  698. returns the sign of a permutation with cycle structure <pi>.
  699.  
  700. |    gap> SignPartition([6,5,4,3,2,1]);
  701.     -1|
  702.  
  703. This function actually describes  a homomorphism of  the  symmetric group
  704. $S_n$ into  the  cyclic group of order  2,  whose  kernel  is exactly the
  705. alternating  group $A_n$  (see "SignPerm").  Partitions  of  sign  1  are
  706. called *even* partitions while partitions of sign $-1$ are called *odd*.
  707.  
  708. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  709. \Section{AssociatedPartition}
  710.  
  711. 'AssociatedPartition( <pi> )'
  712.  
  713. returns the associated partition of the partition <pi>.
  714.  
  715. |    gap> AssociatedPartition([4,2,1]);
  716.     [ 3, 2, 1, 1 ]
  717.     gap> AssociatedPartition([6]);
  718.     [ 1, 1, 1, 1, 1, 1 ]|
  719.  
  720. The  *associated  partition*  of a  partition  <pi> is  defined to be the
  721. partition belonging to the transposed of the Young diagram of <pi>.
  722.  
  723. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  724. \Section{PowerPartition}\index{symmetric group!powermap}
  725.  
  726. 'PowerPartition( <pi>, <k> )'
  727.  
  728. returns the  partition corresponding to the <k>-th power of a permutation
  729. with cycle structure <pi>.
  730.  
  731. |    gap> PowerPartition([6,5,4,3,2,1], 3);
  732.     [ 5, 4, 2, 2, 2, 2, 1, 1, 1, 1 ]|
  733.  
  734. Each part $l$ of <pi> is replaced by $d = \gcd(l, k)$ parts $l/d$.  So if
  735. <pi> is a partition of $n$ then $<pi>^{<k>}$ also is a partition of  $n$.
  736. 'PowerPartition'  describes  the  powermap  of  symmetric   groups.
  737.  
  738. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  739. \Section{PartitionTuples}
  740.  
  741. 'PartitionTuples( <n>, <r> )'
  742.  
  743. returns the list of all <r>--tuples of partitions that together partition
  744. <n>.
  745.  
  746. |    gap> PartitionTuples(3, 2);
  747.     [ [ [ 1, 1, 1 ], [  ] ], [ [ 1, 1 ], [ 1 ] ], [ [ 1 ], [ 1, 1 ] ],
  748.       [ [  ], [ 1, 1, 1 ] ], [ [ 2, 1 ], [  ] ], [ [ 1 ], [ 2 ] ],
  749.       [ [ 2 ], [ 1 ] ], [ [  ], [ 2, 1 ] ], [ [ 3 ], [  ] ],
  750.       [ [  ], [ 3 ] ] ] |
  751.  
  752. <r>--tuples  of partitions describe the  classes  and  the  characters of
  753. wreath products of groups with  <r> conjugacy classes with the  symmetric
  754. group $S_n$.
  755.  
  756. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  757. \Section{Fibonacci}%
  758. \index{sequence!fibonacci}
  759.  
  760. 'Fibonacci( <n> )'
  761.  
  762. 'Fibonacci'  returns  the <n>th number  of the *Fibonacci sequence*.  The
  763. Fibonacci sequence $F_n$ is defined by the initial conditions $F_1=F_2=1$
  764. and  the recurrence relation  $F_{n+2} = F_{n+1}  + F_{n}$.  For negative
  765. $n$  we  define $F_n = (-1)^{n+1}  F_{-n}$, which  is consistent with the
  766. recurrence relation.
  767.  
  768. Using generating functions one can prove that $F_n  = \phi^n - 1/\phi^n$,
  769. where $\phi$ is $(\sqrt{5} + 1)/2$, i.e., one root of $x^2  - x - 1 = 0$.
  770. Fibonacci numbers have the property  $Gcd(  F_m,  F_n ) =  F_{Gcd(m,n)}$.
  771. But a pair  of Fibonacci numbers requires  more division steps in Euclids
  772. algorithm (see "Gcd") than any other  pair of integers  of the same size.
  773. 'Fibonnaci(<k>)' is the special case 'Lucas(1,-1,<k>)[1]' (see "Lucas").
  774.  
  775. |    gap> Fibonacci( 10 );
  776.     55
  777.     gap> Fibonacci( 35 );
  778.     9227465
  779.     gap> Fibonacci( -10 );
  780.     -55 |
  781.  
  782. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  783. \Section{Lucas}%
  784. \index{sequence!lucas}
  785.  
  786. 'Lucas( <P>, <Q>, <k> )'
  787.  
  788. 'Lucas' returns the <k>-th values of the *Lucas sequence* with parameters
  789. <P> and <Q>, which must be integers, as a list of three integers.
  790.  
  791. Let $\alpha, \beta$ be the two roots of  $x^2 - P x + Q$  then we  define\\
  792. $Lucas( P, Q, k )[1] = U_k = (\alpha^k - \beta^k) / (\alpha - \beta)$ and\\
  793. $Lucas( P, Q, k )[2] = V_k = (\alpha^k + \beta^k)$  and as  a convenience\\
  794. $Lucas( P, Q, k )[3] = Q^k$.
  795.  
  796. The following recurrence relations are easily derived from the definition\\
  797. $U_0 = 0, U_1 = 1, U_k = P U_{k-1} - Q U_{k-2}$ and \\
  798. $V_0 = 2, V_1 = P, V_k = P V_{k-1} - Q V_{k-2}$. \\
  799. Those relations are actually used to define 'Lucas' if $\alpha = \beta$.
  800.  
  801. Also the more complex relations used in 'Lucas' can be easily derived\\
  802. $U_{2k} = U_k V_k,        U_{2k+1} = (P U_{2k} + V_{2k}) / 2$ and \\
  803. $V_{2k} = V_k^2 - 2 Q^k,  V_{2k+1} = ((P^2-4Q) U_{2k} + P V_{2k}) / 2$.
  804.  
  805. 'Fibonnaci(<k>)' (see "Fibonacci") is simply 'Lucas(1,-1,<k>)[1]'.  In an
  806. abuse of notation, the sequence  'Lucas(1,-1,<k>)[2]' is sometimes called
  807. the Lucas sequence.
  808.  
  809. |    gap> List( [0..10], i->Lucas(1,-2,i)[1] );
  810.     [ 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341 ]    # $2^k - (-1)^k)/3$
  811.     gap> List( [0..10], i->Lucas(1,-2,i)[2] );
  812.     [ 2, 1, 5, 7, 17, 31, 65, 127, 257, 511, 1025 ]    # $2^k + (-1)^k$
  813.     gap> List( [0..10], i->Lucas(1,-1,i)[1] );
  814.     [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]    # Fibonacci sequence
  815.     gap> List( [0..10], i->Lucas(2,1,i)[1] );
  816.     [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]    # the roots are equal |
  817.  
  818. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  819. \Section{Bernoulli}%
  820. \index{sequence!bernoulli}
  821.  
  822. 'Bernoulli( <n> )'
  823.  
  824. 'Bernoulli' returns the <n>-th *Bernoulli number* $B_n$, which is defined
  825. by $B_0 = 1$ and $B_n = -\sum_{k=0}^{n-1}{{n+1 \choose k} B_k}/(n+1)$.
  826.  
  827. $B_n/n!$ is the coefficient of $x^n$  in the power series of $x/{e^x-1}$.
  828. Except for $B_1=-1/2$ the Bernoulli numbers for odd indices $m$ are zero.
  829.  
  830. |    gap> Bernoulli( 4 );
  831.     -1/30
  832.     gap> Bernoulli( 10 );
  833.     5/66
  834.     gap> Bernoulli( 12 );
  835.     -691/2730    # there is no simple pattern in Bernoulli numbers
  836.     gap> Bernoulli( 50 );
  837.     495057205241079648212477525/66    # and they grow fairly fast |
  838.  
  839. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  840. %%
  841. %E  Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables
  842. %%
  843. %%  Local Variables:
  844. %%  mode:               outline
  845. %%  outline-regexp:     "\\\\Chapter\\|\\\\Section"
  846. %%  fill-column:        73
  847. %%  eval:               (hide-body)
  848. %%  End:
  849. %%
  850.  
  851.  
  852.  
  853.