Wróć do informacji o e-podręczniku Wydrukuj Zapisz jako PDF Udostępnij materiał

W poniższych przykładach wykorzystywać będziemy własności permutacjipermutacja zbioru n–elementowegopermutacji.

W rozwiązaniach tych przykładów będziemy stosować twierdzenie o liczbie permutacjiliczba wszystkich permutacji zbioru n-elementowegotwierdzenie o liczbie permutacji.

Przykład 1

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

Rozwiązanie

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++18=18·192=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!

II sposób.

Zauważamy, że wszystkich permutacjipermutacja zbioru n–elementowegopermutacji zbioru 1,2,3,,20 jest 20!. Natomiast permutacjipermutacja zbioru n–elementowegopermutacji zbioru 1,2,3,,20, 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!=20-2·19!=18·19!

Przykład 2

Obliczymy, na ile sposobów możemy rozmieścić liczby ze zbioru 1,2,3,,20 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 I: od 1 do 4,

  • w rzędzie II: od 5 do 8,

  • w rzędzie III: od 9 do 12,

  • w rzędzie IV: od 13 do 16,

  • w rzędzie 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: 45, 89, 1213 oraz 1617. 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!=19-4·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!=19·10-15·18!·2!=

=175·18!·2!.

Przykład 3

Obliczymy, ile jest wszystkich permutacjipermutacja zbioru n–elementowegopermutacji zbioru 1,2,3,4,5,6,7, 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 1,6,4,3,5,7,2.

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

V73=7!7-3!=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.

II sposób.

Wszystkich permutacjipermutacja zbioru n–elementowegopermutacji zbioru 1,2,3,4,5,6,7 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 7!4!=7·6·5=210.

Przykład 4

Obliczymy, ile jest wszystkich permutacjipermutacja zbioru n–elementowegopermutacji zbioru 1,2,3,4,5,6,7, 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 3,5,4,7,6,1,2.

Zauważmy, że jeżeli w dowolnej permutacjipermutacja zbioru n–elementowegopermutacji zbioru 1,2,3,4,5,6,7 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 12·7!=7!2.

Z kolei, gdy w każdej z tych 7!2permutacjipermutacja 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 12·7!2=7!2·2.

Jeżeli następnie w każdej z tych 7!2·2permutacjipermutacja 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 12·7!2·2=7!2·2·2=630.

Przykład 5

Permutacjępermutacja zbioru n–elementowegoPermutację x1,x2,x3,x4,x5,x6,x7 zbioru 1,2,3,4,5,6,7 nazwiemy ciekawą, jeśli spełniony jest warunek

x1+x2<x6+x7.

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

Dowód

Liczba wszystkich permutacjipermutacja zbioru n–elementowegopermutacji x1,x2,x3,x4,x5,x6,x7 zbioru 1,2,3,4,5,6,7 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 x1+x2<x6+x7),

  • zbiór permutacjipermutacja zbioru n–elementowegopermutacji antyciekawych, dla których spełniony jest warunek x1+x2>x6+x7,

  • oraz zbiór permutacjipermutacja zbioru n–elementowegopermutacji obojętnych, dla których spełniony jest warunek x1+x2=x6+x7.

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 (x1,x2,x6,x7) różnych elementów wybranych ze zbioru 1,2,3,4,5,6,7, które spełniają warunek x1+x2=x6+x7 możemy od razu obliczyć, że jest 8 wszystkich czwórek x1,x2,x6,x7, 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 x1,x2,

  • wymienimy ze sobą wartości w parze x6,x7

  • zamienimy ze sobą wartości par x1,x2x6,x7.

Zatem każda znaleziona czwórka (x1,x2,x6,x7) różnych elementów wybranych ze zbioru 1,2,3,4,5,6,7, które spełniają warunek x1+x2=x6+x7 jest reprezentantem 2·2·2=8 czwórek x1,x2,x6,x7 z różnych permutacjipermutacja zbioru n–elementowegopermutacji obojętnych. Ponieważ do każdego z takiej grupy 8 przypadków pozostałe elementy x3,x4,x5 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 x1,x2,x6,x7.

Czwórki te będziemy odróżniać ze względu na wartość sumy x1,x2 oraz przez reprezentanta, którego wyrazy spełniają warunek x1<x6<x7<x2.

Mamy wtedy następujące przypadki:

  • (1) x1+x2=5, którą reprezentuje jedynie czwórka 1,4,2,3,

  • (2) x1+x2=6, którą reprezentuje jedynie czwórka 1,5,2,4,

  • (3) x1+x2=7, którą reprezentują trzy czwórki: 1,6,2,5, 1,6,3,4 oraz 2,5,3,4,

  • (4) x1+x2=8, którą reprezentują trzy czwórki: 1,7,2,6, 1,7,3,5 oraz 2,6,3,5,

  • (5) x1+x2=9, którą reprezentują trzy czwórki: 2,7,3,6, 2,7,4,5 oraz 3,6,4,5,

  • (6) x1+x2=10, którą reprezentuje jedynie czwórka 3,7,4,6,

  • (7) x1+x2=11, którą reprezentuje jedynie czwórka 4,7,5,6.

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 7!-13·8·3!2=2208.

To spostrzeżenie kończy dowód.

Słownik

permutacja zbioru n–elementowego
permutacja zbioru n–elementowego

Każdy ciąg utworzony ze wszystkich elementów zbioru n–elementowego.

liczba wszystkich permutacji zbioru n-elementowego
liczba wszystkich permutacji zbioru n-elementowego

Liczba wszystkich permutacji zbioru n-elementowego jest równa Pn=n!

reguła mnożenia
reguła mnożenia

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 k1 sposobów, druga – na jeden z k2 sposobów, trzecia – na jeden z k3 sposobów i tak dalej do n-tej czynności, która może zakończyć się na jeden z kn sposobów, jest równa

k1·k2··kn

reguła równoliczności
reguła równoliczności

Dwa zbiory AB 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

reguła dodawania
reguła dodawania

jeżeli zbiory A1,A2,,An są parami rozłączne, to liczba elementów zbioru A1A2An jest równa sumie liczb elementów każdego ze zbiorów A1,A2,,An: A1A2An=A1+A2++An

ciąg
ciąg

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