Definicja 1

Permutacja bez powtórzeń

Permutacją bez powtórzeń n-elementowego zbioru A nazywamy dowolny n-wyrazowy ciąg utworzony ze wszystkich elementów tego zbioru.

Uwaga 1

Uwaga

Zauważ, że permutacja zbioru powstaje w wyniku zmiany kolejności elementów w danym zbiorze.

Twierdzenie 1

Liczba permutacji bez powtórzeń

Liczba permutacji zbioru n-elementowego wynosi:

(0)P_n=n!

Przykład 1

Przykład

Zbiór 2-elementowy: \left\{a,b\right\}, P_2=2!=2 \cdot 1=2
(0)ab\quad ba
Zbiór 3-elementowy: \left\{a,b,c\right\}, P_3=3!=3 \cdot 2 \cdot 1=6
(0)\begin{array}{cc} abc & bac&cab\\ acb & bca & cba \end{array}
Zbiór 4-elementowy: \left\{a,b,c,d\right\}, P_4=4!=4 \cdot 3 \cdot 2 \cdot 1=24
(0)\begin{array}{cccc} abcd & bacd & cabd& dabc\\ abdc & badc & cadb&dacb\\ acbd & bcad & cbad &dbac\\ acdb & bcda & cbda & dbca\\ adbd & bdac & cdab & dcab\\ adcb & bdca & cdba & dcba \end{array}

Definicja 2

Silnia

Silnią nazywamy funkcję !:\mathbb{N_0}\to\mathbb{N_+} daną wzorem (dla n\ge 1):

(0)n!=\prod_{k=1}^{n}k=1\cdot 2\cdot 3\cdot\ldots\cdot n

Przyjmuje się, że 0!=1.

Definicja 3

Permutacja z powtórzeniami

Niech dany będzie zbiór A=\{a_1,a_2,\ldots,a_k\} składający się z k różnych elementów. Permutacją n-elementową z powtórzeniami, w której każdy z elementów a_1,a_2,\ldots,a_k występuje odpowiednio n_1,n_2,\ldots,n_k razy (n_1+n+2+\ldots+n_k=n) nazywamy dowolny n-wyrazowy ciąg w którym każdy element a_i powtarza się dokładnie n_i razy, 1\le i\le k.

Twierdzenie 2

Liczba permutacji z powtórzeniami

Liczba n-elementowych permutacji zbioru k-elementowego (k\le n) wynosi:

(0)P_k^n=\frac{n!}{n_1!\cdot n_2!\cdot\ldots\cdot n_k!}

Twierdzenie o liczbie permutacji