Zadanie 1.6.1: Piętnastu uczniów postanowiło, że codziennie będą siadać w klasie na swoich miejscach w innej kolejności, tak by wyczerpać wszystkie możliwości. Czy zdążą przed maturą?
Rozwiązanie:
∎
Z reguły mnożenia wynika, że wszystkich sposobów usadzenia uczniów jest
\(15 \cdot 14 \cdot 13 \cdot \ldots \cdot 2 \cdot 1 = 15!\)
A czy to dużo?
Okazuje się, że
15! = 1307674368000.
Tyle dni trwałoby wypróbowanie wszystkich możliwości. Przyjmując średnio, że w roku jest 365,25 dni, otrzymalibyśmy ponad 3,5 miliarda lat, czyli nasi uczniowie przed maturą nie zdążą.
Wynik 15! mogliśmy otrzymać natychmiast ze wzoru na liczbę wariacji bez powtórzeń. Zauważmy, że jeśli ustalimy kolejność miejsc, to każdy sposób usadzenia chłopców na tych miejscach wyznacza pewien ciąg 15-elementowy tych chłopców, w którym żaden wyraz się nie powtarza (bo nikt nie może siedzieć jednocześnie na dwóch miejscach). Zatem każdy sposób usadzenia chłopców jest 15-elementową wariacją bez powtórzeń ze zbioru 15-elementowego. Wiemy już, że takich wariacji jest 15!. (To, że uczniowie przed maturą nie zdążą, sprawdziliśmy już wyżej).
Pora na formalną definicję:
|
Permutacją zbioru n-elementowego A nazywamy n-elementową wariację bez powtórzeń z tego zbioru.
|
Wprost ze wzoru na liczbę wariacji bez powtórzeń wynika, że istnieje n! permutacji zbioru n-elementowego.