% This file was created automatically from combinat.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%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}

\>Factorial( <n> ) F

returns the *factorial*  $n!$  of the positive  integer <n>, which is
defined as the product $1 . 2 . 3 \cdots  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  $e^x$, which  is
the generating function for 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.

\>Binomial( <n>, <k> ) F

returns the *binomial coefficient* ${n \choose k}$ of integers <n> and
<k>, which  is defined as $n!  / (k!  (n-k)!)$ (see "Factorial").  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.



\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.

\>Bell( <n> ) F

returns the *Bell number* $B(n)$.  The Bell numbers are defined by
$B(0)=1$ and the recurrence $B(n+1) = \sum_{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").  This
implies of  course that $B(n) =  \sum_{k=0}^{n}{S_2(n,k)}$  (see
"Stirling2").  $B(n)/n!$ is the coefficient of  $x^n$ in the formal
series  $e^{e^x-1}$, which is the generating function for $B(n)$.



\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

\>Bernoulli( <n> ) F

returns the <n>-th *Bernoulli number* $B_n$, which is defined by $B_0 =
1$ and $B_n = -\sum_{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/{e^x-1}$.  Except for $B_1=-1/2$ the Bernoulli numbers for odd
indices are zero.



\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

\>Stirling1( <n>, <k> ) F

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} = \sum_{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 =  \sum_{k=0}^{n}{S_2(n,k) k!  {x  \choose k}}$
(see  "Stirling2").  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.



\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

\>Stirling2( <n>, <k> ) F

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").
Stirling numbers of the second kind  appear as  coefficients  in the
expansion of $x^n = \sum_{k=0}^{n}{S_2(n,k) k!  {x  \choose k}}$.  Note
the similarity to $n! {x \choose  n} = \sum_{k=0}^{n}{S_1(n,k) x^k}$
(see  "Stirling1").  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.



\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}

\>Combinations( <mset> [, <k>] ) F

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")  combinations with <k> elements, and the set of all
combinations is just the *powerset* of <mset>, which contains all
*subsets* of <mset>  and has  cardinality $2^{|mset|}$.


\>NrCombinations( <mset> [, <k>] ) F

returns the number of `Combinations(<mset>,<k>)'.



\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.

\>Arrangements( <mset> [, <k>] ) F

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")
arrangements  with  <k> elements.


\>NrArrangements( <mset> [, <k>] ) F

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

%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.

\>UnorderedTuples( <set>, <k> ) F

returns the  set of all  unordered tuples of length <k> of the set <set>.

An *unordered tuple* of length <k> of <set> is a 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") 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.


\>NrUnorderedTuples( <set>, <k> ) F

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..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.

\>Tuples( <set>, <k> ) F

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.


\>NrTuples( <set>, <k> ) F

returns the number of `Tuples(<set>,<k>)'.



\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.

\>PermutationsList( <mset> ) F

`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")  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! \ldots)$,  which  is
sometimes  called  multinomial coefficient.


\>NrPermutationsList( <mset> ) F

returns the number of `PermutationsList(<mset>)'.



\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.

\>Derangements( <list> ) F

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! - \cdots + (-1)^n/n!)$ derangements.

Note that the ratio
`NrPermutationsList([1..n])/NrDerangements([1..n])',
which is $n! / (n! (1/2! - 1/3! + 1/4! - \cdots + (-1)^n/n!))$
is an approximation for the base of the natural logarithm
$e = 2\.7182818285\ldots$, which is correct to about $n$ digits.


\>NrDerangements( <list> ) F

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.

\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.

\>PartitionsSet( <set> [, <k>] ) F

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") partitions of  the
set  <set>  and $S_2( |set|, k )$ (see "Stirling2") partitions with
<k> elements.


\>NrPartitionsSet( <set> [, <k>] ) F

returns the number of `PartitionsSet(<set>,<k>)'.



\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.

\>Partitions( <n> [, <k>] ) F

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 +\cdots+ p_k$
of positive integers and is represented by the list 
$p = [p_1,p_2,\ldots,p_k]$, in nonincreasing order, i.e., 
$p_1>=p_2>= \ldots  >=p_k$.
We write $p\vdash n$.  There are approximately $e^{\pi \sqrt{2/3 n}}
/ {4 \sqrt{3} n}$ such partitions.

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.

Do not call `Partitions' with an <n> much larger than 40, in  which
case there are 37338 partitions, since the list will simply become too
large.


\>NrPartitions( <n> [, <k>] ) F

returns the number of `Partitions(<set>,<k>)'.



\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'.

\>OrderedPartitions( <n> [, <k>] ) F

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 +\ldots+  p_k$ of
positive integers and is represented by the list $[ p_1, p_2,\ldots, p_k ]$.
There are  totally $2^{n-1}$ ordered  partitions  and ${n-1 \choose k-1}$
(see "Binomial") ordered partitions with <k> summands.

Do not call `OrderedPartitions' with an <n> much larger  than  15,  the
list will simply become too large.


\>NrOrderedPartitions( <n> [, <k>] ) F

returns the number of `OrderedPartitions(<set>,<k>)'.



\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'.

\>PartitionsGreatestLE( <n>, <m> ) F

returns the set of all (unordered) partitions of the integer <n> having
parts less or equal to the integer <m>.


\>PartitionsGreatestEQ( <n>, <m> ) F

returns the set of all (unordered) partitions of the integer <n> having
greatest part equal to the integer <m>.



\>RestrictedPartitions( <n>, <set> [, <k>] ) F

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") an  unordered  sum $n = p_1+p_2+\ldots+p_k$ of  positive
integers and is represented by the list  $p =  [p_1,p_2,\ldots,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]'.


\>NrRestrictedPartitions( <n>, <set> [, <k>] ) F

returns the number of `RestrictedPartitions(<n>,<set>,<k>)'.



\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.

\>SignPartition( <pi> ) F

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").  Partitions  of
sign  1  are called *even* partitions while partitions of sign $-1$ are
called *odd*.



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

\>AssociatedPartition( <pi> ) F

`AssociatedPartition'  returns the associated partition  of the partition
<pi> which is obtained by transposing the corresponding Young diagram.



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

\>PowerPartition( <pi>, <k> ) F

`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  powermap  of  symmetric groups.



\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

\>PartitionTuples( <n>, <r> ) F

`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$.


\>NrPartitionTuples( <n>, <r> ) F

returns the number of `PartitionTuples( <n>, <r> )'.



\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}

\>Fibonacci( <n> ) F

returns  the <n>th 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 = \phi^n  -
1/\phi^n$, where  $\phi$ 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") than any  other  pair of
integers of the same size.  `Fibonacci(<k>)' is the special case
`Lucas(1,-1,<k>)[1]' (see "Lucas").



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

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

\>Lucas( <P>, <Q>, <k> ) F

returns the <k>-th values of the *Lucas sequence* with parameters <P>
and <Q>, which must be integers, as a list of three integers.

Let $\alpha, \beta$ be the two roots of  $x^2 - P x + Q$  then we
define $Lucas( P, Q, k )[1] = U_k = (\alpha^k - \beta^k) / (\alpha -
\beta)$ and $Lucas( P, Q, k )[2] = V_k = (\alpha^k + \beta^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 $\alpha = \beta$.

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") 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.



\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}

\>Permanent( <mat> ) F

returns the *permanent* of the matrix  <mat>.  The  permanent is defined
by $\sum_{p \in Symm(n)}{\prod_{i=1}^{n}{mat[i][i^p]}}$.

Note the similarity of the definition of the permanent to the
definition of the determinant (see~"DeterminantMat").
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.



\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