%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  combinat.msk                GAP documentation            Martin Schoenert
%A                                                           Alexander Hulpke
%%
%A  @(#)$Id: combinat.msk,v 1.19 2002/09/04 11:27:01 gap Exp $
%%
%Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Combinatorics}

This chapter  describes the 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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Combinatorial Numbers}

\Declaration{Factorial}

\beginexample
gap> List( [0..10], Factorial );
[ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ]
gap> Factorial( 30 );
265252859812191058636308480000000
\endexample

`PermutationsList'  (see~"PermutationsList") computes  the  set  of all
permutations of a list.

\Declaration{Binomial}

\index{coefficient!binomial}\atindex{number!binomial}{@number!binomial}

\beginexample
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
\endexample

`NrCombinations' (see "Combinations") is the generalization of `Binomial'
for multisets.  `Combinations' (see "Combinations")  computes the set  of
all combinations of a multiset.

\Declaration{Bell}

\atindex{number!Bell}{@number!Bell}

\beginexample
gap> List( [0..6], n -> Bell( n ) );
[ 1, 1, 2, 5, 15, 52, 203 ]
gap> Bell( 14 );
190899322
\endexample

\Declaration{Bernoulli}

\atindex{sequence!Bernoulli}{@sequence!Bernoulli}

\beginexample
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
\endexample

\Declaration{Stirling1}

\atindex{Stirling number of the first kind}{@Stirling number of the first kind}
\atindex{number!Stirling, of the first kind}%
{@number!Stirling, of the first kind}

\beginexample
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
\endexample

\Declaration{Stirling2}

\atindex{Stirling number of the second kind}%
{@Stirling number of the second kind}
\atindex{number!Stirling, of the second kind}%
{@number!Stirling, of the second kind}

\beginexample
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
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Combinations, Arrangements and Tuples}

\Declaration{Combinations}
\Declaration{NrCombinations}

\index{powerset}\index{subsets}

\beginexample
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
\endexample

The   function `Arrangements'   (see  "Arrangements")   computes  ordered
selections without repetitions, `UnorderedTuples' (see "UnorderedTuples")
computes  unordered  selections  with   repetitions  and `Tuples'    (see
"Tuples") computes ordered selections with repetitions.

\Declaration{Arrangements}
\Declaration{NrArrangements}

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

%notest
\beginexample
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" ] ]
\endexample

Can you find the five proper English words, where `lets' does  not count?
Note that the fact that the  list  returned by `Arrangements' is a proper
set means in this example that the possibilities are  listed in  the same
order as they appear in the dictionary.

\beginexample
gap> NrArrangements( ["s","e","t","t","l","e"] );
523
\endexample

The   function  `Combinations'  (see  "Combinations")  computes unordered
selections without repetitions, `UnorderedTuples' (see "UnorderedTuples")
computes  unordered   selections  with   repetitions  and  `Tuples'  (see
"Tuples") computes ordered selections with repetitions.

\Declaration{UnorderedTuples}
\Declaration{NrUnorderedTuples}

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]

%notest
\beginexample
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 ] ]
\endexample

The function  `Combinations'  (see  "Combinations")   computes  unordered
selections  without  repetitions,    `Arrangements' (see  "Arrangements")
computes ordered   selections without  repetitions   and   `Tuples'  (see
"Tuples") computes ordered selections with repetitions.

\Declaration{Tuples}
\Declaration{NrTuples}

\beginexample
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
\endexample

`Tuples(<set>,<k>)' can also be viewed  as the <k>-fold cartesian product
of <set> (see "Cartesian").

The  function  `Combinations'  (see  "Combinations")  computes  unordered
selections  without   repetitions,  `Arrangements'  (see  "Arrangements")
computes ordered selections without repetitions, and finally the function
`UnorderedTuples' (see "UnorderedTuples")  computes unordered  selections
with repetitions.

\Declaration{PermutationsList}
\Declaration{NrPermutationsList}

\beginexample
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
\endexample

The function `Arrangements' (see "Arrangements") is the generalization of
`PermutationsList'   that  allows  you  to specify   the  size   of   the
permutations.  `Derangements' (see "Derangements") computes  permutations
that have no fixpoints.

\Declaration{Derangements}
\Declaration{NrDerangements}

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.

\beginexample
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
\endexample

The function  `PermutationsList'  (see  "PermutationsList")  computes all
permutations of a list.

\Declaration{PartitionsSet}
\Declaration{NrPartitionsSet}

\beginexample
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
\endexample

Note  that `PartitionsSet' does currently  not support multisets and that
there is currently no ordered counterpart.

\Declaration{Partitions}
\Declaration{NrPartitions}

\beginexample
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
\endexample

The function `OrderedPartitions' (see "OrderedPartitions") is the ordered
counterpart of `Partitions'.

\Declaration{OrderedPartitions}
\Declaration{NrOrderedPartitions}

\index{partitions!ordered, of an integer}
\index{partitions!improper, of an integer}

\beginexample
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
\endexample

The function `Partitions' (see "Partitions") is the unordered counterpart
of `OrderedPartitions'.

\Declaration{PartitionsGreatestLE}
\Declaration{PartitionsGreatestEQ}

\Declaration{RestrictedPartitions}
\Declaration{NrRestrictedPartitions}

\index{partitions!restricted, of an integer}

\beginexample
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
\endexample

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.

\Declaration{SignPartition}

\beginexample
gap> SignPartition([6,5,4,3,2,1]);
-1
\endexample

\Declaration{AssociatedPartition}

\beginexample
gap> AssociatedPartition([4,2,1]);
[ 3, 2, 1, 1 ]
gap> AssociatedPartition([6]);
[ 1, 1, 1, 1, 1, 1 ]
\endexample

\Declaration{PowerPartition}

\index{symmetric group!powermap}

\beginexample
gap> PowerPartition([6,5,4,3,2,1], 3);
[ 5, 4, 2, 2, 2, 2, 1, 1, 1, 1 ]
\endexample

\Declaration{PartitionTuples}
\Declaration{NrPartitionTuples}

\beginexample
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 ] ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Fibonacci and Lucas Sequences}

\Declaration{Fibonacci}

\atindex{sequence!Fibonacci}{@sequence!Fibonacci}

\beginexample
gap> Fibonacci( 10 );
55
gap> Fibonacci( 35 );
9227465
gap> Fibonacci( -10 );
-55
\endexample

\Declaration{Lucas}

\atindex{sequence!Lucas}{@sequence!Lucas}

\beginexample
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 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Permanent of a Matrix}

\Declaration{Permanent}

\beginexample
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
\endexample