img199

Przejdźmy teraz do przypadku ogólnego. Zatóżmy, że n e N₊ i że dany jest pe wien n-elementowy zbiór A = {a_v a₂, ..., a_n). Ze wszystkich jego elementów twe rżymy n-wyrazowe ciągi.

DEFINICJA1.

Permutacją bez powtórzeń zbioru n-elementowego, n e N₊, nazywamy każdy n-wyrazowy ciąg utworzony ze wszystkich elementów danego zbioru n-elementowego.

TWIERDZENIE 1.

Viczba P_n per mutacji bez powtórzeń zbioru n-elementowego (n e. wyrażą S\< wzorem-.

^pn = ⁿ ' (n - 1) ' [n - 2) ■    - 3 -2 ■ Z ^

Dowód.

To twierdzenie udowodnimy metodą indukcji matematycznej.

1 ° Gdy n = 1, to liczba permutacji wynosi 1, a więc P₁ = 1 i oczywiście P₁ = 1!. Tak więc wzór jest prawdziwy dla n = 1.

2 Wykażemy, że A

k g N k> 1

Dowód:

ki

zatożenie

indukcyjne

teza indukcyjna

Obliczmy P*₊1 w następujący sposób: podzielmy ten zbiór (k + 1 )-elementowy na dwa podzbiory: zbiór k-elementowy i zbiór jednoelementowy. Możemy to uczynić na k + 1 sposobów (na tyle sposobów można wybrać ten jeden element). Zgodnie z założeniem indukcyjnym, wszystkich permutacji pierwszego z tych zbiorów jest P_k = ki. Jeżeli do każdej z takich permutacji dodamy element zbioru jednoele-mentowego, to w ten sposób otrzymamy wszystkie (k + 1)-wyrazowe permutacje zbioru (k + 1)-elementowego. Zatem jest ich P_k+1 = ki(k + 1) = (k + 1)! (uzasadnij ostatnią równość), co należało udowodnić.

Tak więc, na mocy zasady indukcji matematycznej, z punktów 1 ° i 2° wynika, że wzór występujący w tezie twierdzenia jest prawdziwy dla dowolnej liczby naturalnej n, n > 1.

Przypomnijmy: symbol „ni” czytamy „n silnia” Oznacza on iloczyn kolejnych liczb naturalnych od 1 do n włącznie (jeśli n > 1) Dodatkowo przyjmuje się, że 0! = 1 i 1 =1