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

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

Пакет 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]

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