Podstawy programu MAPLE

Spis treści | Szukaj | << | >>

24. Kombinatoryka

24.1. Początek

> with(combinat);

Warning, the protected name Chi has been redefined and unprotected
[Chi, bell, binomial, cartprod, character, choose, composition, conjpart,

    decodepart, encodepart, fibonacci, firstpart, graycode, inttovec, lastpart,

    multinomial, nextpart, numbcomb, numbcomp, numbpart, numbperm, partition,

    permute, powerset, prevpart, randcomb, randpart, randperm, setpartition,

    stirling1, stirling2, subsets, vectoint]

24.2. Symbol Newton'a

Polecenie binomial(n,k) oblicza wartość symbolu Newton'a eq001

> binomial(13,10);

                                      286

> binomial(z+2,z-2);

                            binomial(z + 2, z - 2)

> expand(binomial(z+2,z-2));

                           4         3         2
                     1/24 z  + 1/12 z  - 1/24 z  - 1/12 z

24.3. Permutacje bez powtórzeń

Możliwe permutacje bez powtórzeń zbioru n-elementowego otrzymuje się przy pomocy funkcji permute(n):

> permute(4);

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

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

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

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

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

> permute({a,b,c,d});

[[c, b, a, d], [c, b, d, a], [c, a, b, d], [c, a, d, b], [c, d, b, a],

    [c, d, a, b], [b, c, a, d], [b, c, d, a], [b, a, c, d], [b, a, d, c],

    [b, d, c, a], [b, d, a, c], [a, c, b, d], [a, c, d, b], [a, b, c, d],

    [a, b, d, c], [a, d, c, b], [a, d, b, c], [d, c, b, a], [d, c, a, b],

    [d, b, c, a], [d, b, a, c], [d, a, c, b], [d, a, b, c]]

Ilość możliwych permutacji bez powtórzeń Zbioru n-elementowego (tj. n!) zwraca funkcja numbperm(n)

> numbperm(4);

                                      24

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

                                      24

24.4. Permutacje z powtórzeniami

Ilość możliwych permutacji z powtórzeniami elementów zbioru n-elemetowego, gdzie elementy powtarzają się k1, k2... kn razy, oraz k1+k2+...+kn = n (czyli eq002) zwraca funkcja multinomial(n,k1,k2,...,kn).

> multinomial(26,6,6,2,2,3,7);

                               6431499730656000

24.5. Wariacje bez powtórzeń

Możliwe k-elementowe wariacje bez powtórzeń elementów zbioru n-elementowego można otrzymać przy użyciu funkcji permute(n,k):

> permute(4,2);

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

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

> permute({a,b,c,d},2);

[[c, b], [c, a], [c, d], [b, c], [b, a], [b, d], [a, c], [a, b], [a, d],

    [d, c], [d, b], [d, a]]

Ilość możliwych wariacji bez powtórzeń (tj. eq003) zwraca funkcja numbperm(n,k):

> numbperm(4,2);

                                      12

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

                                      12

24.6. Kombinacje

24.6.1. Kombinacje k-elementowe

Możliwe k-elementowe kombinacje zbioru n-elementowego można otrzymać przy pomocy funkcji choose(n,k):

> choose(4,2);

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

> choose({a,b,c,d},2);

               {{c, d}, {b, d}, {a, d}, {c, b}, {c, a}, {b, a}}

Ilość możliwych k-elementowych kombinacji zbioru n-elementowego (tj. eq004) zwraca funkcja numbcomb(n,k):

> numbcomb(4,2);

                                       6

> numbcomb({a,b,c,d},2);

                                       6

24.6.2. Wszystkie możliwe kombinacje

W celu wypisania wszystkich możliwych k-elementowych kombinacji zbioru n-elementowego, gdzie k = 0, 1, ... n należy zastosować funkcję choose(n):

> choose(4);

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

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

> choose({a,b,c,d});

{{}, {d}, {c, d}, {b, d}, {c, b, d}, {a, d}, {c, a, d}, {b, a, d},

    {c, b, a, d}, {c}, {b}, {c, b}, {a}, {c, a}, {b, a}, {c, b, a}}

Ilość możliwych k-elementowych kombinacji zbioru n-elementowego, gdzie k = 1, 2, ... n (tj. eq005) zwraca funkcja numbcomb(n):

> numbcomb(4);

                                      16

> numbcomb({a,b,c,d});

                                      16

24.6.3. Kombinacje liczb naturalnych

Funkcja composition(m,n) wypisuje wszystkie n-elementowe listy liczb naturalnych, których suma równa jest m:

> composition(6,3);

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

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

O ilości zwracanych list dowiemy się po użyciu polecenia numbcomp(m,n):

> numbcomp(6,3);

                                      10

W połączeniu z poleceniem wykonywania sekwencyjnego seq funkcja composition może być użyta do znalezienia wszystkich możliwych sum liczb naturalnych nie większych niż zadana liczba naturalna, na przykład:

> seq(composition(5,i),i=1..5);

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

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

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

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

Jednakże zauważamy, że takie postępowanie w wyniku daje powtarzające się odpowiedzi (na przykład [2,1,2] oraz [1,2,2]). Aby wypisać niepowtarzające się rozkłady liczby naturalnej n na sumę liczba naturalnych należy użyć funkcji partition(n):

> partition(5);

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

O ilości zwracanych list dowiemy się po użyciu polecenia numbpart(n):

> numbpart(5);

                                       7

[koniec]