Przeczytaj
W poniższych przykładach wykorzystywać będziemy własności permutacjipermutacji.
W rozwiązaniach tych przykładów będziemy stosować twierdzenie o liczbie permutacjitwierdzenie o liczbie permutacji.
Obliczymy, ile jest wszystkich permutacjipermutacji zbioru dwudziestu początkowych dodatnich liczb całkowitych, w których elementy oraz nie sąsiadują ze sobą.
Rozwiązanie
sposób:
Zauważmy, że jeżeli wyznaczymy liczbę niesąsiadujących miejsc dla liczb oraz , to w każdym z otrzymanych przypadków te liczby rozmieścimy na przydzielonych miejscach na sposobów, a pozostałe liczb rozmieścimy na pozostałych miejscach na sposobów.
Najpierw wybieramy więc parę niesąsiadujących miejsc w permutacjipermutacji, postępując według zasady: do miejsca o mniejszym numerze dobieramy miejsce o większym numerze. Wtedydo miejsca numer mamy miejsc możliwych do wyboru (od do ),
do miejsca numer mamy miejsc możliwych do wyboru (od do ),
do miejsca numer mamy miejsc możliwych do wyboru (od do ),
i tak dalej, aż do miejsca numer , gdzie mamy miejsce do wyboru (ostatnie, numer ).
Zatem wszystkich możliwych miejsc do wyboru dla pary liczb , jest
.
Korzystając z reguły mnożeniareguły mnożenia, stwierdzamy ostatecznie, że wszystkich permutacjipermutacji spełniających warunki zadania jestsposób:
Zauważamy, że wszystkich permutacjipermutacji zbioru jest . Natomiast permutacjipermutacji zbioru , w których elementy , sąsiadują ze sobą jest .
Wynika z tego, że permutacjipermutacji spełniających warunki zadania jest
Obliczymy, na ile sposobów możemy rozmieścić liczby ze zbioru dwudziestu początkowych dodatnich liczb całkowitych w rzędach po liczby tak, aby elementy oraz 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 : od do ,
w rzędzie : od do ,
w rzędzie : od do ,
w rzędzie : od do ,
w rzędzie : od do .
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ć pary miejsc, które mają sąsiednie numery, ale w tym przypadku już nie sąsiadują ze sobą.
Są to pary miejsc o numerach: i , i , i oraz i . Zatem ogółem niesąsiadujących miejsc dla liczb oraz jest , a więc szukana liczba rozmieszczeń jest równa .
W nawiązaniu do drugiego sposobu zauważmy, że od liczby permutacjipermutacji, w których elementy oraz sąsiadują ze sobą należy odjąć wymienione powyżej przypadki, które już nie opisują pary sąsiednich miejsc. Otrzymamy wtedy, że przypadków dla sąsiadujących miejsc jest
.
Zatem przypadków, kiedy oraz nie sąsiadują ze sobą jest
.
Obliczymy, ile jest wszystkich permutacjipermutacji zbioru , w których liczba jest zapisana na wcześniejszym miejscu niż liczba , liczba jest zapisana na wcześniejszym miejscu niż liczba oraz liczba jest zapisana na wcześniejszym miejscu niż liczba . Warunki zadania spełnia np. permutacjapermutacja .
sposób:
Najpierw wstawimy do tej permutacjipermutacji liczby , oraz : ponieważ dla trzech różnych elementów mamy wybrać trzy miejsca z siedmiu dostępnych, to wszystkich możliwości jest
.Zauważmy, że zgodnie z warunkami zadania jest tylko jeden sposób ustawienia liczb , , , na pozostałych miejscach. Wobec tego jest permutacjipermutacji spełniających warunki zadania.
sposób:
Wszystkich permutacjipermutacji zbioru jest
Zauważmy, że jeżeli w dowolnej permutacjipermutacji tego zbioru ustalimy miejsca dla liczb , , , , 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 liczb na ustalonych miejscach jest , więc na podstawie reguły równolicznościreguły równoliczności dostajemy, że permutacjipermutacji spełniających warunki zadania jest .
Obliczymy, ile jest wszystkich permutacjipermutacji zbioru , w których liczba jest zapisana na wcześniejszym miejscu niż liczba , liczba jest zapisana na wcześniejszym miejscu niż liczba oraz liczba jest zapisana na wcześniejszym miejscu niż liczba . Warunki zadania spełnia np. permutacjapermutacja .
Zauważmy, że jeżeli w dowolnej permutacjipermutacji zbioru ustalimy dwa miejsca dla liczb , , to przy ich rozmieszczaniu na ustalonych miejscach będą one zapisane w żądanej kolejności w jednym przypadku z dwóch możliwych. Takich permutacjipermutacji jest więc .
Z kolei, gdy w każdej z tych permutacjipermutacji ustalimy dwa miejsca dla liczb , , to przy ich rozmieszczaniu na ustalonych miejscach będą one zapisane w żądanej kolejności w jednym przypadku z dwóch możliwych. Zatem permutacjipermutacji spełniających oba powyższe warunki jest .
Jeżeli następnie w każdej z tych permutacjipermutacji ustalimy dwa miejsca dla liczb , , 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 permutacjipermutacji spełniających wszystkie trzy podane warunki jest .
PermutacjęPermutację zbioru nazwiemy ciekawą, jeśli spełniony jest warunek
.
Wykażemy, że wszystkich ciekawych permutacjipermutacji jest .
Dowód
Liczba wszystkich permutacjipermutacji zbioru jest równa
Wszystkie te permutacjepermutacje możemy podzielić na trzy rozłączne zbiory:
zbiór permutacjipermutacji ciekawych (dla każdej z nich spełniony jest warunek ),
zbiór permutacjipermutacji antyciekawych, dla których spełniony jest warunek ,
oraz zbiór permutacjipermutacji obojętnych, dla których spełniony jest warunek .
Zauważmy, że każdej permutacjipermutacji ciekawej można wzajemnie jednoznacznie przyporządkować permutacjępermutację antyciekawą: wystarczy w permutacjipermutacji jednego typu zamienić jednocześnie wyrazy pierwszy z ostatnim oraz drugi z przedostatnim a otrzymamy permutacjępermutację drugiego typu.
Na podstawie reguły równolicznościreguły równoliczności stwierdzamy zatem, że liczba wszystkich permutacjipermutacji ciekawych jest równa liczbie permutacjipermutacji antyciekawych.
Obliczymy, ile jest permutacjipermutacji obojętnych.
Zauważmy, że po wyznaczeniu przykładowej czwórki różnych elementów wybranych ze zbioru , które spełniają warunek możemy od razu obliczyć, że jest wszystkich czwórek , które są szczególnymi permutacjamipermutacjami 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 ,
wymienimy ze sobą wartości w parze
zamienimy ze sobą wartości par z .
Zatem każda znaleziona czwórka różnych elementów wybranych ze zbioru , które spełniają warunek jest reprezentantem czwórek z różnych permutacjipermutacji obojętnych. Ponieważ do każdego z takiej grupy przypadków pozostałe elementy permutacjipermutacji obojętnej można dopisać na sposobów, więc liczba permutacjipermutacji obojętnych jest równa , gdzie to liczba reprezentantów różnych czwórek .
Czwórki te będziemy odróżniać ze względu na wartość sumy oraz przez reprezentanta, którego wyrazy spełniają warunek .
Mamy wtedy następujące przypadki:
, którą reprezentuje jedynie czwórka ,
, którą reprezentuje jedynie czwórka ,
, którą reprezentują trzy czwórki: , oraz ,
, którą reprezentują trzy czwórki: , oraz ,
, którą reprezentują trzy czwórki: , oraz ,
, którą reprezentuje jedynie czwórka ,
, którą reprezentuje jedynie czwórka .
Zatem , co oznacza, że wszystkich permutacjipermutacji obojętnych jest .
Wobec tego permutacjipermutacji ciekawych jest .
To spostrzeżenie kończy dowód.
Słownik
Każdy ciąg utworzony ze wszystkich elementów zbioru –elementowego.
Liczba wszystkich permutacji zbioru -elementowego jest równa
liczba wszystkich możliwych wyników doświadczenia polegającego na wykonaniu po kolei czynności, z których pierwsza może zakończyć się na jeden z sposobów, druga – na jeden z sposobów, trzecia – na jeden z sposobów i tak dalej do -tej czynności, która może zakończyć się na jeden z sposobów, jest równa
Dwa zbiory i są równoliczne (mają tyle samo elementów) jeżeli ich elementy można przyporządkować wzajemnie jednoznacznie, to znaczy: każdemu elementowi zbioru przyporządkujemy dokładnie jeden element zbioru oraz każdemu elementowi zbioru przyporządkujemy dokładnie jeden element zbioru
jeżeli zbiory są parami rozłączne, to liczba elementów zbioru jest równa sumie liczb elementów każdego ze zbiorów :
funkcja, której dziedziną jest zbiór wszystkich dodatnich liczb całkowitych lub pewien jego podzbiór, a wartościami są liczby rzeczywiste