chap16.txt

  
  16 Combinatorics
  
  This  chapter  describes  functions  that deal with combinatorics. We mainly
  concentrate  on two areas. One is about selections, that is the ways one can
  select  elements from a set. The other is about partitions, that is the ways
  one can partition a set into the union of pairwise disjoint subsets.
  
  
  16.1 Combinatorial Numbers
  
  16.1-1 Factorial
  
  Factorial( n )  function
  
  returns  the factorial n! of the positive integer n, which is defined as the
  product 1 ⋅ 2 ⋅ 3 ⋯ n.
  
  n!  is  the  number  of  permutations  of a set of n elements. 1 / n! is the
  coefficient  of  x^n  in  the  formal series exp(x), which is the generating
  function for factorial.
  
    Example  
    gap> List( [0..10], Factorial );
    [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ]
    gap> Factorial( 30 );
    265252859812191058636308480000000
  
  
  PermutationsList (16.2-12) computes the set of all permutations of a list.
  
  16.1-2 Binomial
  
  Binomial( n, k )  function
  
  returns  the binomial coefficient {n choose k} of integers n and k, which is
  defined as n! / (k! (n-k)!) (see Factorial (16.1-1)). We define {0 choose 0}
  =  1,  {n choose k} = 0 if k < 0 or n < k, and {n choose k} = (-1)^k {-n+k-1
  choose  k}  if  n < 0, which is consistent with the equivalent definition {n
  choose k} = {n-1 choose k} + {n-1 choose k-1}.
  
  {n choose k} is the number of combinations with k elements, i.e., the number
  of  subsets  with  k elements, of a set with n elements. {n choose k} is the
  coefficient  of  the  term  x^k  of  the  polynomial (x + 1)^n, which is the
  generating function for {n choose .}, hence the name.
  
    Example  
    gap> # Knuth calls this the trademark of Binomial:
    gap> List( [0..4], k->Binomial( 4, k ) );
    [ 1, 4, 6, 4, 1 ]
    gap> List( [0..6], n->List( [0..6], k->Binomial( n, k ) ) );;
    gap> # the lower triangle is called Pascal's triangle:
    gap> PrintArray( last );
    [ [   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
  
  
  NrCombinations  (16.2-3)  is  the  generalization of Binomial for multisets.
  Combinations (16.2-1) computes the set of all combinations of a multiset.
  
  16.1-3 Bell
  
  Bell( n )  function
  
  returns  the  Bell number B(n). The Bell numbers are defined by B(0) = 1 and
  the recurrence B(n+1) = ∑_{k = 0}^n {n choose k} B(k).
  
  B(n)  is  the  number of ways to partition a set of n elements into pairwise
  disjoint  nonempty  subsets  (see  PartitionsSet (16.2-16)). This implies of
  course that B(n) = ∑_{k = 0}^n S_2(n,k) (see Stirling2 (16.1-6)). B(n)/n! is
  the  coefficient  of  x^n in the formal series exp( exp(x)-1 ), which is the
  generating function for B(n).
  
    Example  
    gap> List( [0..6], n -> Bell( n ) );
    [ 1, 1, 2, 5, 15, 52, 203 ]
    gap> Bell( 14 );
    190899322
  
  
  16.1-4 Bernoulli
  
  Bernoulli( n )  function
  
  returns the n-th Bernoulli number B_n, which is defined by B_0 = 1 and B_n =
  -∑_{k = 0}^{n-1} {n+1 choose k} B_k/(n+1).
  
  B_n  /  n!  is the coefficient of x^n in the power series of x / (exp(x)-1).
  Except for B_1 = -1/2 the Bernoulli numbers for odd indices are zero.
  
    Example  
    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
  
  
  16.1-5 Stirling1
  
  Stirling1( n, k )  function
  
  returns the Stirling number of the first kind S_1(n,k) of the integers n and
  k.  Stirling numbers of the first kind are defined by S_1(0,0) = 1, S_1(n,0)
  = S_1(0,k) = 0 if n, k ne 0 and the recurrence S_1(n,k) = (n-1) S_1(n-1,k) +
  S_1(n-1,k-1).
  
  S_1(n,k)  is  the number of permutations of n points with k cycles. Stirling
  numbers  of the first kind appear as coefficients in the series n! {x choose
  n}  = ∑_{k = 0}^n S_1(n,k) x^k which is the generating function for Stirling
  numbers of the first kind. Note the similarity to x^n = ∑_{k = 0}^n S_2(n,k)
  k! {x choose k} (see Stirling2 (16.1-6)). Also the definition of S_1 implies
  S_1(n,k) = S_2(-k,-n) if n, k < 0. There are many formulae relating Stirling
  numbers  of  the  first  kind  to  Stirling numbers of the second kind, Bell
  numbers, and Binomial coefficients.
  
    Example  
    gap> # Knuth calls this the trademark of S_1:
    gap> List( [0..4], k -> Stirling1( 4, k ) );
    [ 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 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
  
  
  16.1-6 Stirling2
  
  Stirling2( n, k )  function
  
  returns  the  Stirling  number of the second kind S_2(n,k) of the integers n
  and  k.  Stirling  numbers  of  the second kind are defined by S_2(0,0) = 1,
  S_2(n,0)  =  S_2(0,k)  =  0  if  n,  k  ne 0 and the recurrence S_2(n,k) = k
  S_2(n-1,k) + S_2(n-1,k-1).
  
  S_2(n,k)  is  the  number  of  ways  to partition a set of n elements into k
  pairwise  disjoint  nonempty subsets (see PartitionsSet (16.2-16)). Stirling
  numbers  of the second kind appear as coefficients in the expansion of x^n =
  ∑_{k = 0}^n S_2(n,k) k! {x choose k}. Note the similarity to n! {x choose n}
  =  ∑_{k = 0}^n S_1(n,k) x^k (see Stirling1 (16.1-5)). Also the definition of
  S_2  implies  S_2(n,k)  =  S_1(-k,-n)  if  n, k < 0. There are many formulae
  relating  Stirling  numbers  of  the  second kind to Stirling numbers of the
  first kind, Bell numbers, and Binomial coefficients.
  
    Example  
    gap> # Knuth calls this the trademark of S_2:
    gap> List( [0..4], k->Stirling2( 4, k ) );
    [ 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 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
  
  
  
  16.2 Combinations, Arrangements and Tuples
  
  16.2-1 Combinations
  
  Combinations( mset[, k] )  function
  
  returns  the set of all combinations of the multiset mset (a list of objects
  which  may  contain  the same object several times) with k elements; if k is
  not given it returns all combinations of mset.
  
  A  combination  of mset is an unordered selection without repetitions and is
  represented  by a sorted sublist of mset. If mset is a proper set, there are
  {|mset|  choose k} (see Binomial (16.1-2)) combinations with k elements, and
  the  set  of  all combinations is just the power set of mset, which contains
  all subsets of mset and has cardinality 2^{|mset|}.
  
  To  loop  over  combinations of a larger multiset use IteratorOfCombinations
  (16.2-2)  which  produces  combinations  one  by  one  and may save a lot of
  memory.   Another  memory  efficient  representation  of  the  list  of  all
  combinations is provided by EnumeratorOfCombinations (16.2-2).
  
  
  16.2-2 Iterator and enumerator of combinations
  
  IteratorOfCombinations( mset[, k] )  function
  EnumeratorOfCombinations( mset )  function
  
  IteratorOfCombinations  returns  an  Iterator (30.8-1) for combinations (see
  Combinations (16.2-1)) of the given multiset mset. If a non-negative integer
  k  is given as second argument then only the combinations with k entries are
  produced, otherwise all combinations.
  
  EnumeratorOfCombinations   returns  an  Enumerator  (30.3-2)  of  the  given
  multiset  mset.  Currently  only  a  variant  without  second  argument k is
  implemented.
  
  The  ordering of combinations from these functions can be different and also
  different from the list returned by Combinations (16.2-1).
  
    Example  
    gap> m:=[1..15];; Add(m, 15);
    gap> NrCombinations(m);
    49152
    gap> i := 0;; for c in Combinations(m) do i := i+1; od;
    gap> i;
    49152
    gap> cm := EnumeratorOfCombinations(m);;
    gap> cm[1000];
    [ 1, 2, 3, 6, 7, 8, 9, 10 ]
    gap> Position(cm, [1,13,15,15]);
    36866
  
  
  16.2-3 NrCombinations
  
  NrCombinations( mset[, k] )  function
  
  returns the number of Combinations(mset,k).
  
    Example  
    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> # number of different hands in a game of poker:
    gap> NrCombinations( [1..52], 5 );
    2598960
  
  
  The  function  Arrangements  (16.2-4)  computes  ordered  selections without
  repetitions,  UnorderedTuples  (16.2-6)  computes  unordered selections with
  repetitions,   and   Tuples   (16.2-8)   computes  ordered  selections  with
  repetitions.
  
  16.2-4 Arrangements
  
  Arrangements( mset[, k] )  function
  
  returns  the  set  of  arrangements  of  the  multiset  mset  that contain k
  elements. If k is not given it returns all arrangements of mset.
  
  An  arrangement  of  mset is an ordered selection without repetitions and is
  represented  by a list that contains only elements from mset, but maybe in a
  different  order.  If  mset  is a proper set there are |mset|! / (|mset|-k)!
  (see Factorial (16.1-1)) arrangements with k elements.
  
  16.2-5 NrArrangements
  
  NrArrangements( mset[, k] )  function
  
  returns the number of Arrangements(mset,k).
  
  As  an  example  of  arrangements of a multiset, think of the game Scrabble.
  Suppose  you  have  the  six characters of the word "settle" and you have to
  make a four letter word. Then the possibilities are given by
  
    Example  
    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" ] ]
  
  
  Can  you  find  the  five proper English words, where "lets" does not count?
  Note  that  the  fact  that  the list returned by Arrangements (16.2-4) is a
  proper  set  means  in this example that the possibilities are listed in the
  same order as they appear in the dictionary.
  
    Example  
    gap> NrArrangements( ["s","e","t","t","l","e"] );
    523
  
  
  The  function  Combinations  (16.2-1)  computes unordered selections without
  repetitions,  UnorderedTuples  (16.2-6)  computes  unordered selections with
  repetitions,   and   Tuples   (16.2-8)   computes  ordered  selections  with
  repetitions.
  
  16.2-6 UnorderedTuples
  
  UnorderedTuples( set, k )  function
  
  returns the set of all unordered tuples of length k of the set set.
  
  An  unordered  tuple  of  length  k  of  set  is an unordered selection with
  repetitions  of  set  and  is  represented  by  a  sorted  list  of length k
  containing  elements  from  set.  There  are  {|set|  + k - 1 choose k} (see
  Binomial (16.1-2)) such unordered tuples.
  
  Note  that the fact that UnorderedTuples returns a set implies that the last
  index runs fastest. That means the first tuple contains the smallest element
  from  set  k times, the second tuple contains the smallest element of set at
  all  positions  except  at  the last positions, where it contains the second
  smallest element from set and so on.
  
  16.2-7 NrUnorderedTuples
  
  NrUnorderedTuples( set, k )  function
  
  returns the number of UnorderedTuples(set,k).
  
  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, 2, ..., 6 }.
  
    Example  
    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 ] ]
  
  
  The  function  Combinations  (16.2-1)  computes unordered selections without
  repetitions,  Arrangements  (16.2-4)  computes  ordered  selections  without
  repetitions,   and   Tuples   (16.2-8)   computes  ordered  selections  with
  repetitions.
  
  16.2-8 Tuples
  
  Tuples( set, k )  function
  
  returns the set of all ordered tuples of length k of the set set.
  
  An  ordered tuple of length k of set is an ordered selection with repetition
  and  is  represented by a list of length k containing elements of set. There
  are |set|^k such ordered tuples.
  
  Note  that  the  fact  that Tuples returns a set implies that the last index
  runs  fastest. That means the first tuple contains the smallest element from
  set  k  times,  the second tuple contains the smallest element of set at all
  positions  except  at  the  last  positions,  where  it  contains the second
  smallest element from set and so on.
  
  16.2-9 EnumeratorOfTuples
  
  EnumeratorOfTuples( set, k )  function
  
  This  function  is referred to as an example of enumerators that are defined
  by  functions  but are not constructed from a domain. The result is equal to
  that  of Tuples( set, k ). However, the entries are not stored physically in
  the list but are created/identified on demand.
  
  16.2-10 IteratorOfTuples
  
  IteratorOfTuples( set, k )  function
  
  For a set set and a positive integer k, IteratorOfTuples returns an iterator
  (see 30.8)  of the set of all ordered tuples (see Tuples (16.2-8)) of length
  k of the set set. The tuples are returned in lexicographic order.
  
  16.2-11 NrTuples
  
  NrTuples( set, k )  function
  
  returns the number of Tuples(set,k).
  
    Example  
    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
  
  
  Tuples(set,k) can also be viewed as the k-fold cartesian product of set (see
  Cartesian (21.20-16)).
  
  The  function  Combinations  (16.2-1)  computes unordered selections without
  repetitions,  Arrangements  (16.2-4)  computes  ordered  selections  without
  repetitions,  and  finally  the  function  UnorderedTuples (16.2-6) computes
  unordered selections with repetitions.
  
  16.2-12 PermutationsList
  
  PermutationsList( mset )  function
  
  PermutationsList returns the set of permutations of the multiset mset.
  
  A  permutation  is  represented  by  a  list  that contains exactly the same
  elements  as  mset, but possibly in different order. If mset is a proper set
  there  are |mset| ! (see Factorial (16.1-1)) such permutations. Otherwise if
  the  first  elements appears k_1 times, the second element appears k_2 times
  and  so  on, the number of permutations is |mset| ! / (k_1! k_2! ...), which
  is sometimes called multinomial coefficient.
  
  16.2-13 NrPermutationsList
  
  NrPermutationsList( mset )  function
  
  returns the number of PermutationsList(mset).
  
    Example  
    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
  
  
  The function Arrangements (16.2-4) is the generalization of PermutationsList
  (16.2-12)  that  allows  you  to  specify  the  size  of  the  permutations.
  Derangements (16.2-14) computes permutations that have no fixed points.
  
  16.2-14 Derangements
  
  Derangements( list )  function
  
  returns the set of all derangements of the list list.
  
  A  derangement is a fixpointfree permutation of list and is represented by a
  list  that  contains exactly the same elements as list, but in such an order
  that  the  derangement  has  at no position the same element as list. If the
  list list contains no element twice there are exactly |list|! (1/2! - 1/3! +
  1/4! - ⋯ + (-1)^n / n!) derangements.
  
  Note  that  the ratio NrPermutationsList( [ 1 .. n ] ) / NrDerangements( [ 1
  ..  n  ]  ), which is n! / (n! (1/2! - 1/3! + 1/4! - ⋯ + (-1)^n / n!)) is an
  approximation  for  the  base  of the natural logarithm e = 2.7182818285...,
  which is correct to about n digits.
  
  16.2-15 NrDerangements
  
  NrDerangements( list )  function
  
  returns the number of Derangements(list).
  
  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.
  
    Example  
    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
  
  
  The function PermutationsList (16.2-12) computes all permutations of a list.
  
  16.2-16 PartitionsSet
  
  PartitionsSet( set[, k] )  function
  
  returns  the  set of all unordered partitions of the set set into k pairwise
  disjoint  nonempty  sets.  If  k  is  not  given  it  returns  all unordered
  partitions of set for all k.
  
  An  unordered  partition  of set is a set of pairwise disjoint nonempty sets
  with  union  set and is represented by a sorted list of such sets. There are
  B( |set| ) (see Bell (16.1-3)) partitions of the set set and S_2( |set|, k )
  (see Stirling2 (16.1-6)) partitions with k elements.
  
  16.2-17 NrPartitionsSet
  
  NrPartitionsSet( set[, k] )  function
  
  returns the number of PartitionsSet(set,k).
  
    Example  
    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
  
  
  Note  that  PartitionsSet (16.2-16) does currently not support multisets and
  that there is currently no ordered counterpart.
  
  16.2-18 Partitions
  
  Partitions( n[, k] )  function
  
  returns the set of all (unordered) partitions of the positive integer n into
  sums  with k summands. If k is not given it returns all unordered partitions
  of set for all k.
  
  An  unordered  partition  is  an  unordered  sum  n = p_1 + p_2 + ⋯ + p_k of
  positive integers and is represented by the list p = [ p_1, p_2, ..., p_k ],
  in  nonincreasing  order, i.e., p_1 ≥ p_2 ≥ ... ≥ p_k. We write p ⊢ n. There
  are  approximately  exp(π  sqrt{2/3 n}) / (4 sqrt{3} n) such partitions, use
  NrPartitions (16.2-20) to compute the precise number.
  
  If you want to loop over all partitions of some larger n use the more memory
  efficient IteratorOfPartitions (16.2-19).
  
  It  is  possible  to  associate  with  every  partition  of  the integer n a
  conjugacy  class of permutations in the symmetric group on n points and vice
  versa.  Therefore  p(n) :=NrPartitions(n) is the number of conjugacy classes
  of the symmetric group on n points.
  
  Ramanujan  found  the  identities  p(5i+4)  = 0 mod 5, p(7i+5) = 0 mod 7 and
  p(11i+6)  =  0  mod 11 and many other fascinating things about the number of
  partitions.
  
  16.2-19 IteratorOfPartitions
  
  IteratorOfPartitions( n )  function
  
  For   a   positive  integer  n,  IteratorOfPartitions  returns  an  iterator
  (see 30.8)  of  the  set  of partitions of n (see Partitions (16.2-18)). The
  partitions of n are returned in lexicographic order.
  
  16.2-20 NrPartitions
  
  NrPartitions( n[, k] )  function
  
  returns the number of Partitions(set,k).
  
    Example  
    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
  
  
  The  function  OrderedPartitions  (16.2-21)  is  the  ordered counterpart of
  Partitions (16.2-18).
  
  16.2-21 OrderedPartitions
  
  OrderedPartitions( n[, k] )  function
  
  returns  the  set  of  all ordered partitions of the positive integer n into
  sums with k summands. If k is not given it returns all ordered partitions of
  set for all k.
  
  An ordered partition is an ordered sum n = p_1 + p_2 + ... + p_k of positive
  integers  and  is  represented by the list [ p_1, p_2, ..., p_k ]. There are
  totally  2^{n-1}  ordered  partitions  and  {n-1  choose  k-1} (see Binomial
  (16.1-2)) ordered partitions with k summands.
  
  Do  not  call OrderedPartitions with an n much larger than 15, the list will
  simply become too large.
  
  16.2-22 NrOrderedPartitions
  
  NrOrderedPartitions( n[, k] )  function
  
  returns the number of OrderedPartitions(set,k).
  
    Example  
    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
  
  
  The   function   Partitions   (16.2-18)  is  the  unordered  counterpart  of
  OrderedPartitions (16.2-21).
  
  16.2-23 PartitionsGreatestLE
  
  PartitionsGreatestLE( n, m )  function
  
  returns  the set of all (unordered) partitions of the integer n having parts
  less or equal to the integer m.
  
  16.2-24 PartitionsGreatestEQ
  
  PartitionsGreatestEQ( n, m )  function
  
  returns  the  set  of  all  (unordered)  partitions  of the integer n having
  greatest part equal to the integer m.
  
  16.2-25 RestrictedPartitions
  
  RestrictedPartitions( n, set[, k] )  function
  
  In  the  first  form  RestrictedPartitions returns the set of all restricted
  partitions  of  the  positive  integer  n into sums with k summands with the
  summands  of  the  partition  coming from the set set. If k is not given all
  restricted partitions for all k are returned.
  
  A  restricted  partition  is  like  an  ordinary  partition  (see Partitions
  (16.2-18))  an  unordered sum n = p_1 + p_2 + ... + p_k of positive integers
  and  is represented by the list p = [ p_1, p_2, ..., p_k ], in nonincreasing
  order.  The  difference  is  that here the p_i must be elements from the set
  set, while for ordinary partitions they may be elements from [ 1 .. n ].
  
  16.2-26 NrRestrictedPartitions
  
  NrRestrictedPartitions( n, set[, k] )  function
  
  returns the number of RestrictedPartitions(n,set,k).
  
    Example  
    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
  
  
  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.
  
  16.2-27 SignPartition
  
  SignPartition( pi )  function
  
  returns the sign of a permutation with cycle structure pi.
  
  This function actually describes a homomorphism from the symmetric group S_n
  into  the  cyclic  group of order 2, whose kernel is exactly the alternating
  group  A_n  (see  SignPerm  (42.4-1)).  Partitions of sign 1 are called even
  partitions while partitions of sign -1 are called odd.
  
    Example  
    gap> SignPartition([6,5,4,3,2,1]);
    -1
  
  
  16.2-28 AssociatedPartition
  
  AssociatedPartition( pi )  function
  
  AssociatedPartition  returns  the  associated  partition of the partition pi
  which is obtained by transposing the corresponding Young diagram.
  
    Example  
    gap> AssociatedPartition([4,2,1]);
    [ 3, 2, 1, 1 ]
    gap> AssociatedPartition([6]);
    [ 1, 1, 1, 1, 1, 1 ]
  
  
  16.2-29 PowerPartition
  
  PowerPartition( pi, k )  function
  
  PowerPartition  returns  the  partition corresponding to the k-th power of a
  permutation with cycle structure pi.
  
  Each  part  l  of  pi  is replaced by d = gcd(l, k) parts l/d. So if pi is a
  partition  of n then pi^k also is a partition of n. PowerPartition describes
  the power map of symmetric groups.
  
    Example  
    gap> PowerPartition([6,5,4,3,2,1], 3);
    [ 5, 4, 2, 2, 2, 2, 1, 1, 1, 1 ]
  
  
  16.2-30 PartitionTuples
  
  PartitionTuples( n, r )  function
  
  PartitionTuples  returns  the  list  of  all  r-tuples  of  partitions which
  together form a partition of n.
  
  r-tuples  of  partitions  describe  the classes and the characters of wreath
  products of groups with r conjugacy classes with the symmetric group S_n.
  
  16.2-31 NrPartitionTuples
  
  NrPartitionTuples( n, r )  function
  
  returns the number of PartitionTuples( n, r ).
  
    Example  
    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 ] ] ]
  
  
  
  16.3 Fibonacci and Lucas Sequences
  
  16.3-1 Fibonacci
  
  Fibonacci( n )  function
  
  returns the nth number of the Fibonacci sequence. The Fibonacci sequence F_n
  is  defined  by  the  initial  conditions  F_1  = F_2 = 1 and the recurrence
  relation  F_{n+2} = F_{n+1} + F_n. For negative n we define F_n = (-1)^{n+1}
  F_{-n}, which is consistent with the recurrence relation.
  
  Using  generating functions one can prove that F_n = ϕ^n - 1/ϕ^n, where ϕ is
  (sqrt{5}  +  1)/2, i.e., one root of x^2 - x - 1 = 0. Fibonacci numbers have
  the property gcd( F_m, F_n ) = F_{gcd(m,n)}. But a pair of Fibonacci numbers
  requires  more  division steps in Euclid's algorithm (see Gcd (56.7-1)) than
  any  other  pair  of  integers of the same size. Fibonacci(k) is the special
  case Lucas(1,-1,k)[1] (see Lucas (16.3-2)).
  
    Example  
    gap> Fibonacci( 10 );
    55
    gap> Fibonacci( 35 );
    9227465
    gap> Fibonacci( -10 );
    -55
  
  
  16.3-2 Lucas
  
  Lucas( P, Q, k )  function
  
  returns the k-th values of the Lucas sequence with parameters P and Q, which
  must  be  integers, as a list of three integers. If k is a negative integer,
  then  the  values of the Lucas sequence may be nonintegral rational numbers,
  with denominator roughly Q^k.
  
  Let  α,  β  be  the two roots of x^2 - P x + Q then we define Lucas( P, Q, k
  )[1]  =  U_k  = (α^k - β^k) / (α - β) and Lucas( P, Q, k )[2] = V_k = (α^k +
  β^k) and as a convenience Lucas( P, Q, k )[3] = Q^k.
  
  The  following  recurrence  relations are easily derived from the definition
  U_0  = 0, U_1 = 1, U_k = P U_{k-1} - Q U_{k-2} and V_0 = 2, V_1 = P, V_k = P
  V_{k-1}  - Q V_{k-2}. Those relations are actually used to define Lucas if α
  = β.
  
  Also  the  more complex relations used in Lucas can be easily derived U_2k =
  U_k V_k, U_{2k+1} = (P U_2k + V_2k) / 2 and V_2k = V_k^2 - 2 Q^k, V_{2k+1} =
  ((P^2-4Q) U_2k + P V_2k) / 2.
  
  Fibonacci(k)  (see  Fibonacci  (16.3-1))  is  simply Lucas(1,-1,k)[1]. In an
  abuse  of  notation,  the  sequence Lucas(1,-1,k)[2] is sometimes called the
  Lucas sequence.
  
    Example  
    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 ]
  
  
  
  16.4 Permanent of a Matrix
  
  16.4-1 Permanent
  
  Permanent( mat )  function
  
  returns  the permanent of the matrix mat. The permanent is defined by ∑_{p ∈
  Sym(n)} ∏_{i = 1}^n mat[i][i^p].
  
  Note  the similarity of the definition of the permanent to the definition of
  the  determinant  (see DeterminantMat (24.4-4)). 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.
  
    Example  
    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> # 24 permutations fit the projective plane of order 2:
    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