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. This is defined by the conditions {n choose k} = 0 for k < 0, {0 choose k} = 0 for k ≠ 0, {0 choose 0} = 1 and the relation {n choose k} = {n-1 choose k} + {n-1 choose k-1} for all n and k. There are many ways of describing this function. For example, if n ≥ 0 and 0 ≤ k ≤ n, then {n choose k} = n! / (k! (n-k)!) and for n < 0 and k ≥ 0 we have {n choose k} = (-1)^k {-n+k-1 choose k}. If n ≥ 0 then {n choose k} is the number of subsets with k elements of a set with n elements. Also, {n choose k} is the coefficient of x^k in 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-15)). 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 n 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-21) 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 IteratorOfPartitionsSet IteratorOfPartitionsSet( set[, k[, flag]] )  function IteratorOfPartitionsSet returns an iterator (see 30.8) for all unordered partitions of the set set into pairwise disjoint nonempty sets (see PartitionsSet (16.2-16)). If k given and flag is omitted or equal to false, then only partitions of size k are computed. If k is given and flag is equal to true, then only partitions of size at most k are computed. 16.2-21 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-22) is the ordered counterpart of Partitions (16.2-18). 16.2-22 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-23 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-22). 16.2-24 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-25 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-26 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-27 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-28 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-29 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-30 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-31 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 on n points, see CharacterTableWreathSymmetric (71.20-6) and CharacterValueWreathSymmetric (71.20-7). 16.2-32 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.2-33 BetaSet BetaSet( alpha )  function For a list alpha that describes a partition of a nonnegative integer (see Partitions (16.2-18)), BetaSet returns the list of integers obtained by reversing the order of alpha and then adding the sequence [ 0, 1, 2, ... ] of the same length, cf. [JK81, Section 2.7].  Example  gap> BetaSet( [ 4, 2, 1 ] ); [ 1, 3, 6 ] gap> BetaSet( [] ); [ ]  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 )  attribute 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