Kombinatoryka okiem programisty cz. I

Witam!
Dziś i nie tylko dziś opowiemy sobie o kombinatoryce. Czym jest więc ta kombinatoryka?

Kombinatoryka to teoria obliczania liczby elementów zbiorów skończonych. Powstała dzięki grom hazardowym, a swój rozwój zawdzięcza rachunkowi prawdopodobieństwa, teorii grafów, teorii informacji i innym działom matematyki stosowanej. Stanowi jeden z działów matematyki dyskretnej.

Dla programistów stanowi rzecz równie ważną co algorytmika czy teoria grafów.
Mówiąc w skrócie kombinatoryka zajmuję się zbiorem wyrażeń uporządkowanym. Przykładów zastosowania kombinatoryki jest sporo zwłaszcza w wymienionych powyżej dziedzinach. Opłaca się znać choć jej podstawy by móc powiedzieć ile np. jest możliwych kombinacji liczb w Dużym Lotku. A więc zaczynajmy!
Przykłady będę podawał w 2 językach: Pythonie oraz Haskell'u.
0. Silnia
Ten rozdział jest niejako przypomnieniem czym jest podstawowa funkcja kombinatoryki czyli silna.

Silnią n! liczby naturalnej n nazywamy iloczyn 1 * 2 * 3 * ... * n, gdzie zakłada się, że 1! =1 i 0! = 1.

Czyli na przykład silnią n równemu 4 jest 24, bo:
4! = 1 * 2 * 3 * 4 = 24
1. Rozmieszczenia(wariacje)
Rozmieszczeniami z n elementów po k nazywamy ciągi k-wyrazowe, w których każdej z liczb 1, 2, ..., k odpowiada jeden z n danych przedmiotów. Rozmieszczenia te mogą się różnić bądź elementami, bądź przypadkiem elementów.

Na przykład rozmieszczenia z trzech elementów a, b ,c po 2: ab, ac, bc, ba, ca, cb.

Ilość wszystkich rozmieszczeń z n różnych elementów po k wyraża się wzorem:

Np:

Kod w Haskell'u:

-- Funkcja Silnia
silnia::Int ->Int
silnia 0 = 1
silnia n = n * silina (n-1)
-- Funkcja V
v::Int -> Int -> Int
v k n = silnia(n) / silnia(n-k)

Kod w Python'ie:

def silnia(n):
 return init(reduce(lambda x,y: x*y, range(2, n+1) or [1]))
def v(k,n):
 return silnia(n) / silnia(n-k)

Wiemy jak obliczać ilość możliwych kombinacji, ale bardziej interesujące wydaję się jak je tworzyć.

C.D.N.
2. Permutacje
Permutacjami z n elementów nazywamy ciągi n-wyrazowe, w których każdej z liczb 1,2,...,n odpowiada jeden z n danych przedmiotów. Permutacje różnią się tylko porządkiem elementów. Na przykład permutacje z trzech elementów a, b, c: abc, bca, cab, cba, bac, acb. Ilość wszystkich permutacji z n różnych elementów wyznacza się wzorem:

Jeżeli wśród n elementów a, b, c, ... znajdują się jednakowe elementy:

a występuje α, b występuje  β razy, c występuje γ razy itd., to: