Пакеты функций комбинаторики

Пакет combinat

Функции комбинаторики достаточно известны из обычного курса математики. При вызове пакета выводится (если вывод не заблокирован двоеточием) список его функций:

> with(combinat);

Warning, the protected name Chi has been redefined and unprotected

[Chi,bell, binomialcartprod, character, choose, composition, conjpart, decodepart, encodepart,fibonacci,firstpart, graycode, inttovec, lastpart, multinomial, nextpart, numbcomb, numbcomp, numbpart, numbperm, partition, permute, powerset, prevpart, randcomb, randpart, randperm, Stirling], stirling2, subsets, vectoint]

Ввиду важности функций комбинаторики приведем их полные определения:

•  Chi(x) — гиперболический косинусный интеграл;
•  bell(n) —возвращает число ехр(ехр(х)-1) =sum(ben(n)/n!*x^n, n=0..infinity), причем для вычислении используется рекуррентное соотношение bell(n+1) = (bell(n)+1)^n;
•  binomial (n, r) — возвращает биноминальные коэффициенты, причем, если n и r — целые числа, удовлетворяющие условию 0 <= r<= n, то функция возвращает C(n.r)=n!/(r!(n-r)!), а в общем случае С(n, r) = limit(GAMMA(N+D/ GAMMA(R+l)/GAMMA(N-R-t-l),R=r,N=n);
•  composition(n, k) — возвращает списки композиций для целых неотрицательных n и k;
•  fibonacci(n) — возвращает числа Фибоначчи, вычисляемые по рекуррентной формуле F(n) =F(n - 1) +F(n - 2), где F(0) =0 и F(1) =1;
•  fibonacci(n, х) — возвращает значение полинома Фибоначчи F(n, x) =-х F(n - 1,x) + F(n - 2, х), где F(0,x) = 0 и F(l,x) = 1, при этом F(n) = F(n, 1);
•  firstpart(n) — возвращает первую часть каноническей последовательности ряда;
•  nextpart(l) — возвращает следующую часть канонической последовательности ряда;
•  lastpart(n) — возвращает последнюю часть канонической последовательности ряда;
•  prevpart(1) — возвращает предыдущую часть канонической последовательности ряда;
•  conjpart(l) — возвращает объединенный раздел в канонической последовательности ряда;
•  graycode(n) — возвращает список кодов Грея для габитовых чисел;
•  multinomial (n, kl, k2, .... km) — возвращает мультиномиальные коэффициенты;
•  numbcomb(n) и numbcomb(n. m) — возвращает число комбинаций;
•  numbcomp(n, k) — возвращает число композиций;
•  numbpart(n) — возвращает список всех возможных сумм, дающих п;
•  permute(n) и permute(n, r) — возвращает numbperm(n, r) = nops(permute(n. r));
•  powerset(s) — возвращает степень множества в множестве s;
•  randcomb(n, m) — возвращает случайную комбинацию;
•  randpart(n) — возвращает случайную часть;
•  randperm(n) — возвращает случайную композицию; 
•  stirling(n, m) — возвращает число Стирлинга первого рода;
•  stirling2(n, m) — возвращает число Стирлинга второго рода;
•  subsets(L) — задает итерационную процедуру над степенями множества или списка L;
•  vectoint(l) — возвращает индекс вектора канонического упорядочения 1;
•  inttovec(m, n) — возвращает вектор канонического упорядочения для неотрицательных целых чисел тип.

Ниже даны примеры применения некоторых из этих функций:

> choose(4,3); 

[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

> choose([a,a,b,c].3):

[[a,a,b],[a,a,c],[atb,c]] 

> composition(3,2):

{[2,1],[1,2]} 

> decodepart(4,2);

[1,1,2] 

> fibonacci(l0);

55 

> seq(fibonacci(1),i-l..l2):

1,1,2,3,5,8,13,21,34,55,89,144

 > partition(5);

[[1,1,1,1,1], [1,1,1,2], [1,2,2], [1,1,3], [2,3], [1,4], [5]] 

> firstpart(3):

[1,1,1] 

> nextpart(%);

[1,2] 

> prevpart(%);

[1,1,1] 

> 1astpart(3):

[3] 

> conjpart(%): 

[1,1,1] 

> multinomial(8,2,3,3);

560 

> numbcomp(8,5):

35  

> nuropart(3);

numpart(3) 

> numbperm(4); 

24  

> numbperm([a,b]):

2 

 > numbperm({a,b,c},2);

6 

> permute(3,2);

[[l,-2],[l,3],[2,l],[2,3],[3,l],[3,2]] 

> permute([a,a,b],2):

[[a,a],[a,b],(b,a]] 

> powerset([a,a,b]):

[[],[а],[b],[а,Ь],[а,а],[а,а,b-]]

> randcomb([a,b,c,d],3):

[a,c,d] 

> randcomb([a,b,c,d],3);

[a,b,d]

 > randpart(l0);

[2,8]

> randpart(l0):

[10] 

> stirling(10,5);

-269325 

> stirling2(10,5):

42525

> S:=subsets({l,2}):

 > while not S[finished] do S[nextva1ue]() od:

{ }

{1}

{2}

{1,2} 

> vectoint([l,0,0]);

1

 > inttovec(6,3);

[1,0,1]

Читателю, желающему использовать данный пакет, рекомендуется внимательно ознакомиться с этими простыми примерами и просмотреть примеры из справочной базы данных для имеющихся в пакете функций.