984501249

2. LICZBY NATURALNE. INDUKCJA MATEMATYCZNA

Przykładem takiej sytuacji jest definicja symbolu n\ (czytamy „en silnia”). Przyjmujemy więc co następuje:

0! = 1,

1! = 1,

(n + 1)! = n! • (n + 1).

Innymi słowy n\ (dla n ^ 1) jest to iloczyn wszystkich kolejnych liczb naturalnych licząc od 1 aż do n włącznie, tzn.

n! = 1 • 2.....n.

Przy pomocy tego pojęcia możemy policzyć ilość wszystkich możliwych ustawień elementów zbioru n-elementowego. Można odpowiedzieć na przykład na pytanie: na ile sposobów można posadzić 5 osób przy stole prezydialnym? Zanim odpowiemy na to pytanie, sprecyzujemy pojęcie „ustawienia” lub „uszeregowania”. Są to synonimy słowa permutacja.

DEFINICJA 2.1. Permutacją elementów zbioru {ajj,..., x_n} nazywamy każdy układ postaci

P= (*!,>*<»•--iSO.

w którym dla każdego k ^ n element X{_k stoi na pozycji k.

Zatem permutacja elementów zbioru

A = {xi,... ,x_n}

polega na tym, że pozycja każdego elementu zbioru A jest w niej ściśle określona. Przestawienie elementów daje nam inną permutację. Na przykład zbiór {x, y, z} jest identyczny ze zbiorem {z,y,x} bo ma te same elementy, a permutacje (x,y,z) oraz (z, y, x) tego samego zbioru elementów są różne.

Przykład 2.4. Lista wszystkich permutacji zbioru A = {1,2,3} jest następująca: Pi = (1,2,3)

P2 = (1,3,2)

Pa = (2,1,3) p₄ = (2,3,1)

PB = (3,1,2)

P« = (3,2,1).

Łatwo zauważyć, że wszystkie te permutacje różnią się między sobą. Natomiast fakt, że wyczerpują one całą listę możliwych permutacji wymaga już zastanowienia lub zastosowania następującego twierdzenia:

Twierdzenie 2.3. Dla każdej liczby naturalnej n, każdy zbiór składający się z n elementów ma dokładnie n\ permutacji.