|
Пакеты
функций комбинаторики
Пакет 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]
Читателю, желающему использовать
данный пакет, рекомендуется внимательно ознакомиться с этими простыми примерами
и просмотреть примеры из справочной базы данных для имеющихся в пакете функций.
|
