5600235760

7 Permutacje 17

Zgodnie z zasadą mnożenia 6.1 funkcji różnowartościowych jest

m(m — l)(m — 2)... (m — n + 1) = —^m ...    (5)

(m — n)\

Przykład 6.13. Ile jest czterocyfrowych PIN-kodów, w których cyfry nie powtarzają się?

Zbiory X i Y są jak w 6.12, zatem z uwagi na (5) mamy 10 • 9 • 8 • 7 = 5040 takich PIN-kodów.

6.6 Zliczanie podzbiorów

Niech X będzie dowolnym zbiorem o n elementach. Policzmy ile jest wszystkich podzbiorów w X. W tym celu przez A oznaczmy dowolny podzbiór X. Rozważmy funkcję /: X —* {0,1} daną następującym wzorem

/(*) =

gdy x#A, gdy x e A.

Taką funkcję / nazywamy funkcją charakterystyczną zbioru A.

Zauważmy, że ustalony podzbiór A wyznacza jednoznacznie funkcję / i na odwrót, gdy mamy taką funkcję to A = {x E X: f(x) = 1}. Zatem podzbiory X wzajemnie jednoznacznie odpowiadają funkcjom charakterystycznym. Aby więc policzyć podzbiory wystarczy policzyć funkcje charakterystyczne zbioru A a to już umiemy - patrz podpunkt 6.5. Tak więc wszystkich podzbiorów w zbiorze n elementowym jest dokładnie 2ⁿ.

Wyznaczeniem ilości fc-elementowych podzbiorów w zbiorze n-elementowym zajmiemy się później.

7 Permutacje

Permutacja zbioru skończonego X to bijekcja z X na X.

Niech Z_n oznacza zbiór reszt przy dzieleniu przez liczbę n, to znaczy

Z_n = {0,1,2,... ,n}.

Zbiór permutacji zbioru Z_n oznaczamy przez S_n. Zbiór n-elementowy ma dokładnie n! permutacji,

|S„| = n\.

Przykład 7.1. Rozważmy funkcję 7r: Z7 —> Z7 zadaną poniższą tabelą:

n	0	1	2	3	4	5	6
7r (n)	2	3	6	0	4	1	5

Funkcja n jest bijekcją z Z7 w Z7, zatem jest permutacją i ir E S7.