Отправляет email-рассылки с помощью сервиса Sendsay

Система компьютерной алгебры GAP

Подписаться Бесплатная «Серебряная» новостная рассылка . Временно не выходит ,возобновит выход - нет информации Подписчиков 783 RSS
←   Март 2005   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://www.gap-system.org/ukrgap/
Открыта: 05-02-2002

Автор
Александр Борисович Коновалов

Статистика

783 подписчиков
0 за неделю
←   Все выпуски   →

Система компьютерной алгебры GAP - #48, 18-03-05 (Combinatorics in GAP)


Информационный Канал Subscribe.Ru
Рассылка "Система компьютерной алгебры GAP"
(http://subscribe.ru/catalog/science.exact.gap/)
ведущий рассылки А.Б.Коновалов, a_konovalov [at] hotmail [dot] com
выпуск 48 от 18 марта 2005 г.
Элементы комбинаторики в системе GAP
На сайте Украинской группы пользователей GAP (http://ukrgap.exponenta.ru/) в разделе "Изучаем алгебру с GAP" помещен новый материал по теме "Элементы комбинаторики". Предлагаем Вам ознакомиться с ним в данном выпуске рассылки.
Данный раздел посвящен обзору основных функций системы компьютерной алгебры GAP, связанных с комбинаторикой. Более подробно о них и других комбинаторных функциях можно узнать в разделе "Комбинаторика" справочного руководства по системе GAP.

Функция 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 = {s1, ... sn}, в которых элемент si содержится ровно vi раз и v1+...+vn = k. (Тогда перестановки множества из n элементов получаем при v1 = ... = vn = 1). Число Ck(v1,...,vn) различных перестановок множества M с повторениями равно k! / (v1! ...vn!) и может быть получено с помощью функции 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 ) возвращает биномиальный коэффициент Cnk = n! / (k! (n−k)!), т.е. коэффициент при xk в многочлене (x + 1)n.

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

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

gap> Binomial(49,6);  
13983816
gap> Binomial(36,5);  
376992
Сами же эти эти сочетания можно получить с помощью функции Combinations( set, k ). Например, найдем всевозможные тройки, которые можно составить из чисел 1, 2 , 3 , 4, 5 :

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 = p1+p2 +…+ pk натуральных чисел описывается списком p = [p1,p2,…,pk], элементы которого перечислены в невозрастающем порядке. Учтите, что уже 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-й элемент последовательности Фибоначчи, которая определена следующим образом: F1=F2=1 и Fn+2 = Fn+1 + Fn. Получим список первых пятидесяти ее элементов и продемонстрируем одно интересное свойство данной последовательности: 

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
С уважением,
Александр Борисович Коновалов
председатель Украинской группы пользователей GAP (http://ukrgap.exponenta.ru/)
доцент кафедры алгебры и геометрии Запорожского государственного университета
E-mail: a_konovalov [at] hotmail [dot] com

http://subscribe.ru/
http://subscribe.ru/feedback/		 Подписан адрес:
Код этой рассылки: science.exact.gap		 Отписаться
В избранное