Obliczymy, ile jest wszystkich siedmiocyfrowych liczb naturalnych zapisanych za pomocą cyfr $1,2,3,4,5,6,7$, w których każde dwie cyfry są różne oraz cyfry $1$ i $2$ nie są zapisane obok siebie.

Rozwiązanie

Pokażemy, że liczbie $7$-cyfrowej, która spełnia warunki zadania można przyporządkować dokładnie jedną permutację $11$-elementową utworzoną w pewien szczególny sposób ze wszystkich cyfr danej liczby oraz z $4$ elementów równych $0$.

W tym celu najpierw z kolejnych cyfr takiej $7$-cyfrowej liczby naturalnej tworzymy $7$-elementową permutację, do której dopisujemy cztery elementy równe $0$ według zasad podanych w poniższych punktach:
(1) wstawiamy po jednym zerze między każde dwa elementy nieparzyste, które są zapisane obok siebie – jeżeli w ten sposób wstawiliśmy cztery zera, to procedurę uzupełniania kończymy, w przeciwnym przypadku przechodzimy do kolejnego punktu;
(2) jeżeli pierwszym elementem jest cyfra nieparzysta, to wstawiamy przed nim element $0$ – jeżeli po wykonaniu tego kroku permutacja liczy $11$ elementów, to procedurę uzupełniania kończymy, w przeciwnym przypadku jako ostatni, jedenasty element permutacji wstawiamy $0$.

Rozpatrzmy z kolei $11$-elementową permutacjępermutacja zbioru $n$–elementowegopermutację $\left(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10},a_{11}\right)$, w której:

• na $5$ miejscach o indeksach parzystych rozmieszczamy cyfry ze zbioru $\left\{3,4,5,6,7\right\}$ (można to zrobić na $5!=5·4·3·2·1=120$ sposobów),

• na wybranych dwóch spośród $6$ miejsc o indeksach nieparzystych rozmieszczamy elementy ze zbioru $\left\{1,2\right\}$ (można to zrobić na $\left(\begin{array}{c}6\\ 2\end{array}\right)·2!=6·5=30$ sposobów),

• na każdym spośród $4$ pozostałych miejsc wstawiamy $0$ (co można zrobić na $1$ sposób).

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia stwierdzamy, że wszystkich takich permutacjipermutacja zbioru $n$–elementowegopermutacji jest $5!·6·5=120·30=3600$.

Zauważmy, że po usunięciu zer z tak otrzymanej permutacjipermutacja zbioru $n$–elementowegopermutacji dostaniemy $7$-elementową permutacjępermutacja zbioru $n$–elementowegopermutację, której kolejne elementy tworzą liczbę $7$-cyfrową spełniającą warunki zadania.

Pokazaliśmy w ten sposób, że każdej liczbie $7$-cyfrowej spełniającej warunki zadania odpowiada dokładnie jedna permutacja $11$-elementowa, w której na $5$ miejscach o numerach parzystych rozmieszczone są elementy ze zbioru $\left\{3,4,5,6,7\right\}$, a na pozostałych miejscach rozmieszczone są: $1$, $2$ i cztery zera.

Wynika stąd, że wszystkich $7$-cyfrowych liczb naturalnych, które spełniają warunki zadania jest $3600$.

Rozpatrujemy wszystkie permutacjepermutacja zbioru $n$–elementowegopermutacje siedmioelementowego zbioru $\left\{2,3,4,5,6,7,8\right\}$. Obliczymy, ile jest wśród utworzonych ciągów takich, w których iloczyn każdych dwóch kolejnych elementów jest liczbą parzystą.

Rozwiązanie

Zauważmy, że permutacja danego zbioru spełnia warunki zadania wtedy i tylko wtedy, gdy żadne dwa spośród jej sąsiednich elementów nie są liczbami nieparzystymi. Należy więc rozdzielić elementy $3,5,7$ używając do tego elementów $\left\{2,4,6,8\right\}$.
Postępujemy podobnie, jak w poprzednim przykładzie.

Rozpatrujemy $9$-elementową permutacjępermutacja zbioru $n$–elementowegopermutację $\left(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9\right)$, w której:

• na $4$ miejscach o indeksach parzystych rozmieszczamy cyfry ze zbioru $\left\{2,4,6,8\right\}$ (można to zrobić na $4!=4·3·2·1=24$ sposoby),

• na wybranych trzech spośród $5$ miejsc o indeksach nieparzystych rozmieszczamy elementy ze zbioru $\left\{3,5,7\right\}$ (można to zrobić na $\left(\begin{array}{c}5\\ 3\end{array}\right)·3!=5·4·3=60$ sposobów),

• na każdym spośród $2$ pozostałych miejsc wstawiamy $0$ (co można zrobić na $1$ sposób).

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia stwierdzamy, że wszystkich takich permutacjipermutacja zbioru $n$–elementowegopermutacji jest $4!·5·4·3=24·60=1440$.

Na koniec zauważamy, że każdej permutacjipermutacja zbioru $n$–elementowegopermutacji spełniającej warunki zadania można wzajemnie jednoznacznie przypisać ciąg $11$-elementowy, który tworzymy w sposób opisany powyżej.

Oznacza to, że jest $1440$ wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji siedmioelementowego zbioru $\left\{2,3,4,5,6,7,8\right\}$, w których iloczyn każdych dwóch kolejnych elementów jest liczbą parzystą.

Z wyrazów $10$-elementowego zbioru $\left\{a,d,e,l,o,p,r,t,u,x\right\}$ tworzymy dziesięcioliterowy ciąg, którego elementy się nie powtarzają. Obliczymy, ile jest takich ciągów, w których żadne dwie samogłoski (czyli elementy zbioru $\left\{a,e,o,u\right\}$) nie są zapisane na sąsiednich miejscach.
Uwaga. Przykładowym ciągiem spełniającym warunki zadania jest $\left(l,u,x,t,o,r,p,e,d,a\right)$.

Rozwiązanie

Zauważmy, że permutacja zbioru $\left\{a,d,e,l,o,p,r,t,u,x\right\}$ spełnia warunki zadania wtedy i tylko wtedy, gdy rozdzielimy $4$ elementy: $a,e,o,u$, używając do tego $6$ elementów: $d,l,p,r,t,x$.
Postępujemy podobnie, jak w poprzednich przykładach.

Rozpatrujemy $13$-elementową permutacjępermutacja zbioru $n$–elementowegopermutację $\left(a_1,a_2,a_3,a_4,a_5,a_6,a_7,\dots ,a_{13}\right)$, w której:

• na $6$ miejscach o indeksach parzystych rozmieszczamy litery ze zbioru $\left\{d,l,p,r,t,x\right\}$ (możemy to zrobić na $6!=6·5·4·3·2·1=720$ sposobów),

• na wybranych czterech spośród $7$ miejsc o indeksach nieparzystych rozmieszczamy elementy ze zbioru $\left\{a,e,o,u\right\}$ (można to zrobić na $\left(\begin{array}{c}7\\ 4\end{array}\right)·4!=7·6·5·4=840$ sposobów),

• na każdym spośród $3$ pozostałych miejsc wstawiamy $0$ (co można zrobić na $1$ sposób).

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia stwierdzamy, że wszystkich tak utworzonych permutacjipermutacja zbioru $n$–elementowegopermutacji jest $6!·7·6·5·4=840·720=604800$.

Ostatecznie zauważamy, że każdemu ciągowi spełniającemu warunki zadania można wzajemnie jednoznacznie przypisać $13$-elementową permutacjępermutacja zbioru $n$–elementowegopermutację, którą tworzymy w sposób opisany powyżej.

Oznacza to, że jest $604800$ wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji $10$-elementowego zbioru $\left\{a,d,e,l,o,p,r,t,u,x\right\}$, w których żadne dwie samogłoski nie są zapisane na sąsiednich miejscach.

Grupę $16$ osób, wśród których jest $10$ dorosłych oraz sześcioro dzieci: Ania, Basia, Czarek, Damian, Ewa i Franek, należy rozsadzić w rzędzie, w którym jest $16$ miejsc siedzących. Rozpatrujemy wszystkie takie sposoby rozmieszczenia tej grupy osób, aby każde z dzieci siedziało pomiędzy dorosłymi.
Wykażemy, że liczba otrzymanych w ten sposób rozmieszczeń jest większa niż $2·{10}^{11}$.

Rozwiązanie

Zauważmy, że rozmieszczenie opisanej w treści zadania grupy $16$ osób spełnia warunki zadania wtedy i tylko wtedy, gdy rozdzielimy każde spośród $6$ dzieci sadzając je między dorosłymi w taki sposób, żeby żadne z dzieci nie zajęło żadnego z dwóch skrajnych miejsc.
Aby to osiągnąć zmodyfikujemy pomysły omówione w poprzednich przykładach.

Rozpatrujemy $19$-elementową permutacjępermutacja zbioru $n$–elementowegopermutację $\left(a_1,a_2,a_3,a_4,a_5,a_6,a_7,\dots ,a_{19}\right)$, w której:

• na $10$ miejscach o indeksach nieparzystych rozmieszczamy wszystkich dorosłych (możemy to zrobić na $10!$ sposobów),

• na wybranych sześciu spośród $9$ miejsc o indeksach parzystych rozmieszczamy $6$ dzieci (można to zrobić na $\left(\begin{array}{c}9\\ 6\end{array}\right)·6!=9·8·7·6·5·4$ sposobów),

• każde spośród $3$ pozostałych miejsc pozostawiamy puste.

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia stwierdzamy, że wszystkich tak utworzonych permutacjipermutacja zbioru $n$–elementowegopermutacji jest
$10!·9·8·7·6·5·4=219469824000$.

Na koniec zauważmy, że jeżeli z rozpatrywanej powyżej permutacjipermutacja zbioru $n$–elementowegopermutacji $19$-elementowej usuniemy elementy puste, a następnie ponumerujemy od $1$ do $16$ kolejne elementy tak otrzymanej permutacji $16$-elementowej, to w ten sposób przydzielimy każdej z osób rozpatrywanego zbioru unikalny numer miejsca w rzędzie, a także spełnione będą warunki zadania.

Oznacza to, że jest $219469824000$ wszystkich takich rozmieszczeń omawianej grupy $16$ osób, że każde z dzieci będzie siedziało pomiędzy dorosłymi.

Ostatecznie stwierdzamy, że $219469824000>200000000000=2·{10}^{11}$.
W ten sposób zakończyliśmy dowód.

każdy ciąg utworzony ze wszystkich elementów zbioru $n$–elementowego

liczba wszystkich permutacji zbioru $n$-elementowego jest równa $P_n=n!$

liczba wszystkich możliwych wyników doświadczenia polegającego na wykonaniu po kolei $n$ czynności, z których pierwsza może zakończyć się na jeden z $k_1$ sposobów, druga – na jeden z $k_2$ sposobów, trzecia – na jeden z $k_3$ sposobów i tak dalej do $n$–tej czynności, która może zakończyć się na jeden z $k_n$ sposobów, jest równa