Функция Factorial(n) возвращает n! = 1 * 2 * ... * n для натурального числа n. Значение 0! полагается равным 1. Например, вычислим n! для целых чисел от нуля до 10:

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

n! можно интерпретировать следующим образом. Пусть M - множество из n элементов. Всякое расположение элементов множества M в некотором определенном порядке называется перестановкой из n элементов. Тогда количество различных перестановок из n элементов равняется n!.

Заметим, что в явном виде все эти перестановки можно получить с помощью функции PermutationsList. Эта функция возвращает множество всех перестановок из элементов заданного множества:

gap> pl:=PermutationsList([1,2,3]);
[ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ]
gap> Length(pl)=Factorial(3); # количество перестановок = 6 = 3!
true

С помощью функции PermutationList можно также находить перестановки с повторениями, которые получаются, если рассматривать упорядоченные наборы из k элементов множества M = {s₁, ... s_n}, в которых элемент s_i содержится ровно v_i раз и v₁+...+v_n = k. (Тогда перестановки множества из n элементов получаем при v₁ = ... = v_n = 1). Число C_k(v₁,...,v_n) различных перестановок множества M с повторениями равно k! / (v₁! ...v_n!) и может быть получено с помощью функции NrPermutationsList.

Пример 1: составить всевозможные слова из четырех букв, содержащие два раза букву "a", один раз букву "b" и один раз букву "c":

gap> PermutationsList(["a","a","b","c"]);
[ [ "a", "a", "b", "c" ], [ "a", "a", "c", "b" ], [ "a", "b", "a", "c" ],
[ "a", "b", "c", "a" ], [ "a", "c", "a", "b" ], [ "a", "c", "b", "a" ],
[ "b", "a", "a", "c" ], [ "b", "a", "c", "a" ], [ "b", "c", "a", "a" ],
[ "c", "a", "a", "b" ], [ "c", "a", "b", "a" ], [ "c", "b", "a", "a" ] ]
gap> List(last,Concatenation);
[ "aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "bcaa",
"caab", "caba", "cbaa" ]

Пример 2: определить количество различных 10-значных чисел, содержащих трижды цифру 1, дважды цифру 5, дважды цифру 7, и по одной цифре 3, 4, 9:

gap> NrPermutationsList([1,1,1,5,5,7,7,3,4,9]);
151200

Функция Binomial( n, k ) возвращает биномиальный коэффициент C_n^k = n! / (k! (n−k)!), т.е. коэффициент при x^k в многочлене (x + 1)ⁿ.

gap> List( [0..4], k->Binomial( 4, k ) ); 
[ 1, 4, 6, 4, 1 ]
gap> x:=Indeterminate(Integers,"x");;
gap> (1+x)^4;
x^4+4*x^3+6*x^2+4*x+1
gap> CoefficientsOfUnivariatePolynomial( (1+x)^4 );
[ 1, 4, 6, 4, 1 ]
gap> List( [0..6], n->List( [0..6], k->Binomial( n, k ) ) );;
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 ] ]

Кроме того, C_n^k показывает количество сочетаний из n элементов по k, т.е. количество k-элементных подмножеств множества, состоящего из n элементов.

gap> Binomial(49,6);  
13983816
gap> Binomial(36,5);  
376992

gap> Combinations([1..5],3);
[ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ],
[ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ]
gap>

Если второй параметр не указывать, то возвращается список всех подмножеств заданного множества:

gap> Combinations([1..5]);
[ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 5 ], [ 1, 2, 4 ], [ 1, 2, 4, 5 ], [ 1, 2, 5 ], [ 1, 3 ],
[ 1, 3, 4 ], [ 1, 3, 4, 5 ], [ 1, 3, 5 ], [ 1, 4 ], [ 1, 4, 5 ], [ 1, 5 ],
[ 2 ], [ 2, 3 ], [ 2, 3, 4 ], [ 2, 3, 4, 5 ], [ 2, 3, 5 ], [ 2, 4 ],
[ 2, 4, 5 ], [ 2, 5 ], [ 3 ], [ 3, 4 ], [ 3, 4, 5 ], [ 3, 5 ], [ 4 ],
[ 4, 5 ], [ 5 ] ]

Количество сочетаний можно также получить и с помощью функции NrCombinations:

gap> Binomial(52,5)=NrCombinations([1..52],5);
true
gap> NrCombinations([1..52])=2^52;
true

Однако, NrCombinations является обобщением функции Binomial на случай множеств, содержащих повторяющиеся элементы, которые различаются как элементы этих множеств. Например, определим, сколько различных наборов букв можно выбрать из букв a, b, b и c, и, в частности, сколько различных пар букв можно выбрать из них:

gap> NrCombinations( ["a","b","b","c"] );
12
gap> NrCombinations( ["a","b","b","c"],2 );
4

В явном виде эти наборы можно получить с помощью функции Combinations:

gap> Combinations( ["a","b","b","c"] );
[ [ ], [ "a" ], [ "a", "b" ], [ "a", "b", "b" ], [ "a", "b", "b", "c" ],
[ "a", "b", "c" ], [ "a", "c" ], [ "b" ], [ "b", "b" ], [ "b", "b", "c" ],
[ "b", "c" ], [ "c" ] ]
gap> Combinations( ["a","b","b","c"],2 );
[ [ "a", "b" ], [ "a", "c" ], [ "b", "b" ], [ "b", "c" ] ]
gap>

В отличие от функции Combinations, вычисляющей неупорядоченные наборы без повторений, функция Arrangements вычисляет размещения, т.е. всевозможные упорядоченные наборы из k элементов исходного множества без повторений. Если аргумент k не задан, то возвращаются все всевозможные наборы для каждого допустимого значения k. Соответственно, количество наборов с указанными свойствами возвращает функция NrArrangements. Например, определим, сколько различных слов можно составить из букв a, b, b и c, и, в частности, сколько различных двухбуквенных слов можно составить из них, а затем выпишем все эти слова:

gap> NrArrangements( ["a","b","b","c"] );
35
gap> NrArrangements( ["a","b","b","c"],2 );
7
gap> List( Arrangements( ["a","b","b","c"] ), Concatenation );
[ [ ], "a", "ab", "abb", "abbc", "abc", "abcb", "ac", "acb", "acbb", "b",
"ba", "bab", "babc", "bac", "bacb", "bb", "bba", "bbac", "bbc", "bbca",
"bc", "bca", "bcab", "bcb", "bcba", "c", "ca", "cab", "cabb", "cb", "cba",
"cbab", "cbb", "cbba" ]
gap> List( Arrangements( ["a","b","b","c"],2 ), Concatenation );
[ "ab", "ac", "ba", "bb", "bc", "ca", "cb" ]

Далее, функция UnorderedTuples(set, k) вычисляет сочетания с повторениями, т.е. всевозможные неупорядоченные наборы из k элементов исходного множества с повторениями. Функция Tuples(set, k) вычисляет размещения с повторениями, т.е. всевозможные упорядоченные наборы из k элементов исходного множества с повторениями (фактически она возвращает список элементов декартова произведения множества на себя k раз.). Соответственно, количество наборов с указанными свойствами возвращают функции NrUnorderedTuples и NrTuples.

gap> UnorderedTuples([1..3],2);
[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ], [ 3, 3 ] ]
gap> Tuples([1..3],2);
[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ],
[ 3, 2 ], [ 3, 3 ] ]
gap> NrUnorderedTuples([1..52],5);
3819816
gap> NrTuples([-5..5],5);
161051

PartitionsSet( set [, k] ) возвращает множество всевозможных неупорядоченных разбиений множества set в объединение k попарно непересекающихся непустых множеств. Если k не задано, то возвращаются всевозможные разбиения для всех допустимых значений k. Количество таких разбиений определяется с помощью функции NrPartitionsSet( set [, k] ).

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

Partitions( n [, k] ) возвращает множество всех (неупорядоченных) разбиений натурального числа n, т.е. его представлений в виде (неупорядоченной) суммы k слагаемых. Если число k не задано, то возвращается множество всевозможных таких разбиений для всех допустимых значений k. Разбиение числа n в виде неупорядоченной суммы n = p₁+p₂ +…+ p_k натуральных чисел описывается списком p = [p₁,p₂,…,p_k], элементы которого перечислены в невозрастающем порядке. Учтите, что уже Partitions(40) возвращает 37338 таких разбиений, а для последующих чисел количество их разбиений будет еще больше. Его можно определить с помощью функции NrPartitions( n [, k] ), не вычисляя при этом сами разбиения.

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

Аналогами этих функций, имеющими дело с упорядоченными разбиениями натурального числа n, являются функции OrderedPartitions( n [, k] ) и NrOrderedPartitions( n [, k] ). Учтите, что уже для n=15 результат функции OrderedPartitions(15) будет достаточно объемным.

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

Также имеются функции, позволяющие рассматривать только те разбиения, которые удовлетворяют некоторым дополнительным условиям. Функция PartitionsGreatestLE( n, m ) возвращает множество всех (неупорядоченных) разбиений натурального числа n, каждое слагаемое которых меньше или равняется m. Функция PartitionsGreatestEQ( n, m ) возвращает множество всех (неупорядоченных) разбиений натурального числа n, в которых максимальное слагаемое равняется m.

Функция RestrictedPartitions( n, set [, k] ) возвращает множество всех (неупорядоченных) разбиений натурального числа n (на k слагаемых, если задан аргумент k, или всевозможных, если он не задан), в которых слагаемые принадлежат множеству set. Число таких разбиений можно получить с помощью функции NrRestrictedPartitions( n, set [, k] ).

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(100,[1,2,5,10,25,50]);
3953

Последний пример показывает, что существует 3953 способа выдать 1 гривню монетами в 1, 2, 5, 10, 25 и 50 копеек.

Функция Fibonacci( n ) возвращает n-й элемент последовательности Фибоначчи, которая определена следующим образом: F₁=F₂=1 и F_n+2 = F_n+1 + F_n. Получим список первых пятидесяти ее элементов и продемонстрируем одно интересное свойство данной последовательности:

gap> fib:=List([1..50],Fibonacci);
[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 
  4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 
  514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 
  24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 
  701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 
  12586269025 ]
gap> Gcd( fib[50], fib[25] ) = fib[ Gcd(50,25) ];
true

---