984501250

I. STRUKTURY LICZBOWE

Także i to twierdzenie można udowodnić metodą indukcyjną. Jeśli zbiór jest jedno-elementowy, to ma oczywiście tylko jedną permutację bo jego elementu nie ma z czym przestawić. Jeśli założymy, że każdy zbiór n-elementowy ma n! permutacji, to nietrudno zauważyć, że zbiór złożony zn+1 elementów będzie miał ich (n + 1)!. Istotnie, jeśli wybierzemy sobie jeden z elementów tego zbioru, to wszystkie pozostałe można ustawić na n! sposobów. Z drugiej zaś strony pojedyńczy element można w permutacji n + 1-elementowej ustawić nan + 1 sposobów. Zatem wszystkich możliwych ustawień jest

(n + 1) • n!,

co na mocy definicji symbolu silni daje (n + 1)!, a to kończy dowód.

Zbiór wszystkich permutacji zbioru n-elementowego {1,..., n} oznaczać będziemy symbolem P_n.

Z powyższego twierdzenia wynika, że lista permutacji w przykładzie 2.4 jest kompletna: powinno ich być 3! czyli 6. atwo również odpowiedzieć na wcześniejsze pytanie o ilość możliwości rozmieszczenia 5 osób przy stole: tych możliwości jest 120. Inny przykład: wszystkich możliwych ułożeń talii 52 kart jest 52!, co w przybliżeniu wynosi 807-10⁶⁵. Jak więc widać liczby n! rosną bardzo szybko. Świadczy o tym także następny przykład.

Przykład 2.5. Dla dowolnej liczby naturalnej n zachodzi nierówność:

(4)    n! ^ 2^n_1.

Istotnie, dla n = 1 po obydwu stronach nierówności mamy 1. Aby sprawdzić warunek (II*) Zasady Indukcji Matematycznej załóżmy, że n > 1 oraz, że zachodzi nierówność (4). Skoro n + 1 > 2, to mamy

(n + 1)! = n\(n + 1) > 2^n_1 • 2 = 2ⁿ,

co kończy dowód.

Okazuje się, że liczby postaci n! rosną znacznie szybciej niż liczby 2ⁿ; w istocie stosunek

n!

2"

rośnie do nieskończoności.

Jeśli A — {1,2,..., n}, to z każdą permutacją elementów zbioru A związane jest pojęcie inwersji.

Definicja 2.2. Mówimy, że para (Xi,Xj) tworzy inwersję w permutacji p = (Xi,X2, ...,x_n)

zbioru {1,2,..., n}, jeśli X{ > Xj, a jednocześnie i < j.

Mówiąc prościej: inwersja w permutacji ma miejsce wtedy, gdy liczba większa występuje w tej permutacji przed liczbą mniejszą. Ilość inwersji w permutacji p będziemy oznaczali symbolem I(p).