Permutacje, to mówiąc nieformalnie różne ustawienia elementów danego zbioru skończonego, w których każdy element występuje dokładnie raz.

Definicja 11.4.1

Permutacją n-elementowego zbioru X nazywamy dowolny ciąg n-elementowy o różnych wyrazach należących do zbioru X. Inaczej mówiąc, permutacja, to funkcja różnowartościowa ze zbioru {1,...,n} w zbiór X.

Na ile sposobów można zorganizować wycieczkę, a czasie której chcemy odwiedzić 3 wybrane miejscowości?

Niech miejscowościami, o których mowa w zadaniu będą A, B, C. Wtedy mamy następujące trasy A B C, A C B, B A C, B C A, C A B, C B A. Razem 6 różnych tras.

Jak wynika z rozważań w poprzednim paragrafie i powyższej definicji, n-elementowe permutacje zbioru n-elementowego X, to n-elementowe wariacje w zbiorze n-elementowym. Mamy więc natychmiastowy wniosek z Twierdzenia 11.3.1

Twierdzenie 11.4.1

Liczba permutacji w dowolnym zbiorze n-elementowym wynosi n!, dla dowolnej liczby naturalnej n.

Dowód. Przeprowadzimy dowód tego twierdzenia stosując zasadę indukcji matematycznej por. wykład IX.

Baza indukcji. Jeśli n=1, tzn. dysponujemy tylko jednym elementem, to możemy utworzyć tylko jeden ciąg. Ponieważ 1! =1 , zatem twierdzenie jest prawdziwe dla n=1.

Założenie indukcyjne: Dla pewnego k, liczba permutacji w zbiorze k-elementowym wynosi k!.

Teza: Liczba permutacji w zbiorze (k+1)-elementowym wynosi (k+1)!.
Dowód tezy : Przedstawmy zbiór (k+1)-elementowy X' w postaci X ∪ {x _k+1}, gdzie X jest zbiorem k-elementowym i x _k+1do niego nie należy. Permutację zbioru X' możemy uzyskać biorąc jakąkolwiek permutację zbioru X i uzupełnić ją wstawiając na wszystkie możliwe pozycje element x_k+1
.Pozycji, na których mogę umieścić nowy element, jest oczywiście (k+1) (przed pierwszym elementem, przed drugim itd. ..., po ostatnim).

Na mocy założenia indukcyjnego, k-elementowych permutacji jest k!. Zatem wszystkich (k+1)-elementowych permutacji jest k! *(k+1) , czyli (k+1)!.

Ponieważ wszystkie założenia zasady indukcji matematycznej zostały spełnione, więc twierdzenie 11.4.1 jest prawdziwe dla wszystkich liczb naturalnych. ♦

Zastanówmy się jeszcze co to za liczba n!. Łatwo zauważyć, że n! ≤ n ⁿ. Dzięki wzorowi Stirlinga mamy nieco dokładniejszą informację

Nawet dla bardzo małych zbiorów (np.5-cio elementowych), liczba permutacji jest bardzo duża (125). Bezbłędne wypisanie takiego zbioru ciągów jest już prawie niemożliwe dla człowieka. A co z komputerem? Czy komputer też miałby z tym problem?

Przede wszystkim musimy przygotować algorytm, a więc jednorodne postępowanie, które niezależnie od typu elementów i liczby n zawsze da w wyniku pełny zestaw permutacji danego zbioru. Ponieważ natura elementów nie jest ważna zatem wystarczy rozważyć zbiory liczbowe, a najlepiej dla danego n, zbiór {1,2,3,...,n}.

Takie postępowanie daje dla n = 4, kolejno ( najpierw pierwszą kolumnę potem drugą kolumnę itd.) ciągi:

Zauważmy, że uzyskany porządek permutacji jest porządkiem leksykograficznym.

Wygeneruj wszystkie (n-1)! permutacje zbioru {2,...,n} i umieść 1 na pierwszej pozycji w każdej z nich.
Wygeneruj wszystkie (n-1)! permutacji zbioru {2,...,n} i umieść 1 na drugiej pozycji w każdej z nich, itd.

Dokładniejszy algorytm rekurencyjny realizujący tę metodę postępowania mógłby wyglądać następująco (por. R.Sedgewick, Algorithms, Addison-Wesley Comp., 1983):

procedure visit( k:integer);
var t: integer;
begin now := now+1; val[k]:= now;

if now= n then wypisz_aktualny_stan_tablicy_val fi;
for t := 1 to n do

if val[t]=0 then visit(t);

od;
now := now-1; val[k] := 0;

end;

Chociaż realizacja poszczególnych poleceń tego algorytmu nie sprawi kłopotu żadnemu komputerowi, to jednak wykonanie algorytmu dla niezbyt dużych n (np. dla n=16) zajmie tak dużo czasu, że nie doczekamy się wszystkich wyników. n! jest funkcją rosnącą niezwykle szybko.

Dla każdej z wygenerowanych permutacji umieść 1 na kolejnych n możliwych pozycjach.

Ta ostatnia metoda postępowania jest szczególnie interesująca. Niech będzie graf, którego wierzchołkami są permutacje zbioru {1,...n}, a krawędzie łączą jedynie te wierzchołki a, b, dla których od permutacji a do permutacji b można przejść przez zamianę dwóch sąsiednich pozycji ciągu. Wtedy ciąg wyznaczony przez algorytm 3 wyznacza ścieżkę przechodzącą przez wszystkie wierzchołki grafu i to przez każdy tylko raz (kolumny przebiegamy na zmianę z góry na dół i z dołu na górę). Taką drogę nazywamy drogą Hamiltona w grafie. (Znalezienie drogi Hamiltona w grafie jest jednym z problemów trudnych informatyki.)

Pytanie 11.4.1: Ile jest liczb całkowitych pięciocyfrowych, które w systemie dziesiętnym zapisuje się przy użyciu cyfr 1,2,3,4,5, tab by każda z cyfr występowała dokładnie raz?