Obliczymy, ile jest wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji zbioru $\left\{1,2,3,\dots ,20\right\}$ dwudziestu początkowych dodatnich liczb całkowitych, w których elementy $1$ oraz $2$ nie sąsiadują ze sobą.

Rozwiązanie

• $\text{I}$ sposób:

  Zauważmy, że jeżeli wyznaczymy liczbę niesąsiadujących miejsc dla liczb $1$ oraz $2$, to w każdym z otrzymanych przypadków te liczby rozmieścimy na przydzielonych miejscach na $2!$ sposobów, a pozostałe $18$ liczb rozmieścimy na pozostałych miejscach na $18!$ sposobów.
  Najpierw wybieramy więc parę niesąsiadujących miejsc w permutacjipermutacja zbioru $n$–elementowegopermutacji, postępując według zasady: do miejsca o mniejszym numerze dobieramy miejsce o większym numerze. Wtedy

  • do miejsca numer $1$ mamy $18$ miejsc możliwych do wyboru (od $3$ do $20$),

  • do miejsca numer $2$ mamy $17$ miejsc możliwych do wyboru (od $4$ do $20$),

  • do miejsca numer $3$ mamy $16$ miejsc możliwych do wyboru (od $5$ do $20$),

  i tak dalej, aż do miejsca numer $18$, gdzie mamy $1$ miejsce do wyboru (ostatnie, numer $20$).
  Zatem wszystkich możliwych miejsc do wyboru dla pary liczb $1$, $2$ jest
  $1+2+3+\dots +18=\frac{18·19}{2}=9·19=171$.
  Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia, stwierdzamy ostatecznie, że wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji spełniających warunki zadania jest $171·2!·18!=9·2·19·18!=18·19!$

• $\text{II}$ sposób:

  Zauważamy, że wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji zbioru $\left\{1,2,3,\dots ,20\right\}$ jest $\mathrm{,20}!$. Natomiast permutacjipermutacja zbioru $n$–elementowegopermutacji zbioru $\left\{1,2,3,\dots ,20\right\}$, w których elementy $1$, $2$ sąsiadują ze sobą jest $19!·2!$.
  Wynika z tego, że permutacjipermutacja zbioru $n$–elementowegopermutacji spełniających warunki zadania jest $20!-19!·2!=\left(20-2\right)·19!=18·19!$

Obliczymy, na ile sposobów możemy rozmieścić liczby ze zbioru $\left\{1,2,3,\dots ,20\right\}$ dwudziestu początkowych dodatnich liczb całkowitych w $5$ rzędach po $4$ liczby tak, aby elementy $1$ oraz $2$ nie sąsiadowały ze sobą. Przyjmujemy tutaj, że liczby sąsiadują ze sobą jeśli leżą obok siebie w tym samym rzędzie.

Rozwiązanie

Dla porządku numerujemy miejsca w rzędach:

• w rzędzie $\text{I}$: od $1$ do $4$,

• w rzędzie $\text{II}$: od $5$ do $8$,

• w rzędzie $\text{III}$: od $9$ do $12$,

• w rzędzie $\text{IV}$: od $13$ do $16$,

• w rzędzie $\text{V}$: od $17$ do $20$.

Rozwiązanie przedstawimy w nawiązaniu do rozwiązania poprzedniego przykładu i obu przedstawionych tam sposobów.

W nawiązaniu do pierwszego sposobu zauważmy, że do liczby miejsc wtedy obliczonych wystarczy doliczyć $4$ pary miejsc, które mają sąsiednie numery, ale w tym przypadku już nie sąsiadują ze sobą.

Są to pary miejsc o numerach: $4$ i $5$, $8$ i $9$, $12$ i $13$ oraz $16$ i $17$. Zatem ogółem niesąsiadujących miejsc dla liczb $1$ oraz $2$ jest $171+4=175$, a więc szukana liczba rozmieszczeń jest równa $175·18!·2!$.

W nawiązaniu do drugiego sposobu zauważmy, że od liczby $19!·2!$ permutacjipermutacja zbioru $n$–elementowegopermutacji, w których elementy $1$ oraz $2$ sąsiadują ze sobą należy odjąć $4$ wymienione powyżej przypadki, które już nie opisują pary sąsiednich miejsc. Otrzymamy wtedy, że przypadków dla sąsiadujących miejsc jest

$19!·2!-4·18!·2!=\left(19-4\right)·18!·2!=15·18!·2!$.

Zatem przypadków, kiedy $1$ oraz $2$ nie sąsiadują ze sobą jest

$20!-15·18!·2!=20·19·18!-15·18!·2!=\left(19·10-15\right)·18!·2!=$

$=175·18!·2!$.

Obliczymy, ile jest wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji zbioru $\left\{1,2,3,4,5,6,7\right\}$, w których liczba $1$ jest zapisana na wcześniejszym miejscu niż liczba $3$, liczba $3$ jest zapisana na wcześniejszym miejscu niż liczba $5$ oraz liczba $5$ jest zapisana na wcześniejszym miejscu niż liczba $7$. Warunki zadania spełnia np. permutacjapermutacja zbioru $n$–elementowegopermutacja $\left(1,6,4,3,5,7,2\right)$.

• $\text{I}$ sposób:

  Najpierw wstawimy do tej permutacjipermutacja zbioru $n$–elementowegopermutacji liczby $2$, $4$ oraz $6$: ponieważ dla trzech różnych elementów mamy wybrać trzy miejsca z siedmiu dostępnych, to wszystkich możliwości jest
  $V_7^3=\frac{7!}{\left(7-3\right)!}=7·6·5=210$.

  Zauważmy, że zgodnie z warunkami zadania jest tylko jeden sposób ustawienia liczb $1$, $3$, $5$, $7$ na pozostałych $4$ miejscach. Wobec tego jest $210$ permutacjipermutacja zbioru $n$–elementowegopermutacji spełniających warunki zadania.

• $\text{II}$ sposób:

  Wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji zbioru $\left\{1,2,3,4,5,6,7\right\}$ jest $7!$

  Zauważmy, że jeżeli w dowolnej permutacjipermutacja zbioru $n$–elementowegopermutacji tego zbioru ustalimy $4$ miejsca dla liczb $1$, $3$, $5$, $7$, to rozmieszczając je na tych ustalonych miejscach tylko w jednym przypadku będą one zapisane w żądanej kolejności. A ponieważ wszystkich przypadków rozmieszczenia $4$ liczb na $4$ ustalonych miejscach jest $4!$, więc na podstawie reguły równolicznościreguła równolicznościreguły równoliczności dostajemy, że permutacjipermutacja zbioru $n$–elementowegopermutacji spełniających warunki zadania jest $\frac{7!}{4!}=7·6·5=210$.

Obliczymy, ile jest wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji zbioru $\left\{1,2,3,4,5,6,7\right\}$, w których liczba $1$ jest zapisana na wcześniejszym miejscu niż liczba $2$, liczba $3$ jest zapisana na wcześniejszym miejscu niż liczba $4$ oraz liczba $5$ jest zapisana na wcześniejszym miejscu niż liczba $6$. Warunki zadania spełnia np. permutacjapermutacja zbioru $n$–elementowegopermutacja $\left(3,5,4,7,6,1,2\right)$.

Zauważmy, że jeżeli w dowolnej permutacjipermutacja zbioru $n$–elementowegopermutacji zbioru $\left\{1,2,3,4,5,6,7\right\}$ ustalimy dwa miejsca dla liczb $1$, $2$, to przy ich rozmieszczaniu na ustalonych miejscach będą one zapisane w żądanej kolejności w jednym przypadku z dwóch możliwych. Takich permutacjipermutacja zbioru $n$–elementowegopermutacji jest więc $\frac{1}{2}·7!=\frac{7!}{2}$.

Z kolei, gdy w każdej z tych $\frac{7!}{2}$ permutacjipermutacja zbioru $n$–elementowegopermutacji ustalimy dwa miejsca dla liczb $3$, $4$, to przy ich rozmieszczaniu na ustalonych miejscach będą one zapisane w żądanej kolejności w jednym przypadku z dwóch możliwych. Zatem permutacjipermutacja zbioru $n$–elementowegopermutacji spełniających oba powyższe warunki jest $\frac{1}{2}·\frac{7!}{2}=\frac{7!}{2·2}$.

Jeżeli następnie w każdej z tych $\frac{7!}{2·2}$ permutacjipermutacja zbioru $n$–elementowegopermutacji ustalimy dwa miejsca dla liczb $5$, $6$, to przy ich rozmieszczaniu na ustalonych miejscach będą one zapisane w żądanej kolejności w jednym przypadku z dwóch możliwych. Wobec tego permutacjipermutacja zbioru $n$–elementowegopermutacji spełniających wszystkie trzy podane warunki jest $\frac{1}{2}·\frac{7!}{2·2}=\frac{7!}{2·2·2}=630$.

Permutacjępermutacja zbioru $n$–elementowegoPermutację $\left(x_1,x_2,x_3,x_4,x_5,x_6,x_7\right)$ zbioru $\left\{1,2,3,4,5,6,7\right\}$ nazwiemy ciekawą, jeśli spełniony jest warunek

$x_1+x_2<x_6+x_7$.

Wykażemy, że wszystkich ciekawych permutacjipermutacja zbioru $n$–elementowegopermutacji jest $2208$.

Dowód

Liczba wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji $\left(x_1,x_2,x_3,x_4,x_5,x_6,x_7\right)$ zbioru $\left\{1,2,3,4,5,6,7\right\}$ jest równa $7!$

Wszystkie te permutacjepermutacja zbioru $n$–elementowegopermutacje możemy podzielić na trzy rozłączne zbiory:

• zbiór permutacjipermutacja zbioru $n$–elementowegopermutacji ciekawych (dla każdej z nich spełniony jest warunek $x_1+x_2<x_6+x_7$),

• zbiór permutacjipermutacja zbioru $n$–elementowegopermutacji antyciekawych, dla których spełniony jest warunek $x_1+x_2>x_6+x_7$,

• oraz zbiór permutacjipermutacja zbioru $n$–elementowegopermutacji obojętnych, dla których spełniony jest warunek $x_1+x_2=x_6+x_7$.

Zauważmy, że każdej permutacjipermutacja zbioru $n$–elementowegopermutacji ciekawej można wzajemnie jednoznacznie przyporządkować permutacjępermutacja zbioru $n$–elementowegopermutację antyciekawą: wystarczy w permutacjipermutacja zbioru $n$–elementowegopermutacji jednego typu zamienić jednocześnie wyrazy pierwszy z ostatnim oraz drugi z przedostatnim a otrzymamy permutacjępermutacja zbioru $n$–elementowegopermutację drugiego typu.

Na podstawie reguły równolicznościreguła równolicznościreguły równoliczności stwierdzamy zatem, że liczba wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji ciekawych jest równa liczbie permutacjipermutacja zbioru $n$–elementowegopermutacji antyciekawych.

Obliczymy, ile jest permutacjipermutacja zbioru $n$–elementowegopermutacji obojętnych.

Zauważmy, że po wyznaczeniu przykładowej czwórki $(x_1,x_2,x_6,x_7)$ różnych elementów wybranych ze zbioru $\left\{1,2,3,4,5,6,7\right\}$, które spełniają warunek $x_1+x_2=x_6+x_7$ możemy od razu obliczyć, że jest $8$ wszystkich czwórek $\left(x_1,x_2,x_6,x_7\right)$, które są szczególnymi permutacjamipermutacja zbioru $n$–elementowegopermutacjami wyznaczonej czwórki. Mianowicie, dla tej szczególnej wyznaczonej jak powyżej czwórki warunek zostanie zachowany, gdy:

• wymienimy ze sobą wartości w parze $x_1,x_2$,

• wymienimy ze sobą wartości w parze $x_6,x_7$

• zamienimy ze sobą wartości par $x_1,x_2$ z $x_6,x_7$.

Zatem każda znaleziona czwórka $(x_1,x_2,x_6,x_7)$ różnych elementów wybranych ze zbioru $\left\{1,2,3,4,5,6,7\right\}$, które spełniają warunek $x_1+x_2=x_6+x_7$ jest reprezentantem $2·2·2=8$ czwórek $\left(x_1,x_2,x_6,x_7\right)$ z różnych permutacjipermutacja zbioru $n$–elementowegopermutacji obojętnych. Ponieważ do każdego z takiej grupy $8$ przypadków pozostałe elementy $x_3,x_4,x_5$ permutacjipermutacja zbioru $n$–elementowegopermutacji obojętnej można dopisać na $3!$ sposobów, więc liczba permutacjipermutacja zbioru $n$–elementowegopermutacji obojętnych jest równa $8·3!·n$, gdzie $n$ to liczba reprezentantów różnych czwórek $\left(x_1,x_2,x_6,x_7\right)$.

Czwórki te będziemy odróżniać ze względu na wartość sumy $x_1,x_2$ oraz przez reprezentanta, którego wyrazy spełniają warunek $x_1<x_6<x_7<x_2$.

Mamy wtedy następujące przypadki:

1. $x_1+x_2=5$, którą reprezentuje jedynie czwórka $\left(1,4,2,3\right)$,

2. $x_1+x_2=6$, którą reprezentuje jedynie czwórka $\left(1,5,2,4\right)$,

3. $x_1+x_2=7$, którą reprezentują trzy czwórki: $\left(1,6,2,5\right)$, $\left(1,6,3,4\right)$ oraz $\left(2,5,3,4\right)$,

4. $x_1+x_2=8$, którą reprezentują trzy czwórki: $\left(1,7,2,6\right)$, $\left(1,7,3,5\right)$ oraz $\left(2,6,3,5\right)$,

5. $x_1+x_2=9$, którą reprezentują trzy czwórki: $\left(2,7,3,6\right)$, $\left(2,7,4,5\right)$ oraz $\left(3,6,4,5\right)$,

6. $x_1+x_2=10$, którą reprezentuje jedynie czwórka $\left(3,7,4,6\right)$,

7. $x_1+x_2=11$, którą reprezentuje jedynie czwórka $\left(4,7,5,6\right)$.

Zatem $n=1+1+3+3+3+1+1=13$, co oznacza, że wszystkich permutacjipermutacja zbioru $n$–elementowegopermutacji obojętnych jest $13·8·3!$.

Wobec tego permutacjipermutacja zbioru $n$–elementowegopermutacji ciekawych jest $\frac{7!-13·8·3!}{2}=2208$.

To spostrzeżenie kończy 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

$k_1·k_2·\dots ·k_n$

Dwa zbiory $A$ i $B$ są równoliczne (mają tyle samo elementów) jeżeli ich elementy można przyporządkować wzajemnie jednoznacznie, to znaczy: każdemu elementowi zbioru $A$ przyporządkujemy dokładnie jeden element zbioru $B$ oraz każdemu elementowi zbioru $B$ przyporządkujemy dokładnie jeden element zbioru $A$

jeżeli zbiory $A_1,A_2,\dots ,A_n$ są parami rozłączne, to liczba elementów zbioru $A_1\cup A_2\cup \dots \cup A_n$ jest równa sumie liczb elementów każdego ze zbiorów $A_1,A_2,\dots ,A_n$: $\left|A_1\cup A_2\cup \dots \cup A_n\right|=\left|A_1\right|+\left|A_2\right|+\dots +\left|A_n\right|$

funkcja, której dziedziną jest zbiór wszystkich dodatnich liczb całkowitych lub pewien jego podzbiór, a wartościami są liczby rzeczywiste