Przeczytaj
Poniżej prezentowane są przykłady dotyczące liczby rozmieszczeń (permutacji) elementów pewnych zbiorów, w których wybrane elementy spełniają określone warunki.
W pierwszym przykładzie rozwiążemy zadanie dotyczące liczby permutacjiliczby permutacji pewnego zbioru, w którym należy rozdzielić dwa jego wyróżnione elementy.
W kolejnych przykładach liczba rozdzielanych elementów będzie się zwiększała.
Obliczymy, ile jest wszystkich siedmiocyfrowych liczb naturalnych zapisanych za pomocą cyfr , w których każde dwie cyfry są różne oraz cyfry i nie są zapisane obok siebie.
Rozwiązanie
Pokażemy, że liczbie -cyfrowej, która spełnia warunki zadania można przyporządkować dokładnie jedną permutację -elementową utworzoną w pewien szczególny sposób ze wszystkich cyfr danej liczby oraz z elementów równych .
W tym celu najpierw z kolejnych cyfr takiej -cyfrowej liczby naturalnej tworzymy -elementową permutację, do której dopisujemy cztery elementy równe 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 – jeżeli po wykonaniu tego kroku permutacja liczy elementów, to procedurę uzupełniania kończymy, w przeciwnym przypadku jako ostatni, jedenasty element permutacji wstawiamy .
Rozpatrzmy z kolei -elementową permutacjępermutację , w której:
na miejscach o indeksach parzystych rozmieszczamy cyfry ze zbioru (można to zrobić na sposobów),
na wybranych dwóch spośród miejsc o indeksach nieparzystych rozmieszczamy elementy ze zbioru (można to zrobić na sposobów),
na każdym spośród pozostałych miejsc wstawiamy (co można zrobić na sposób).
Korzystając z reguły mnożeniareguły mnożenia stwierdzamy, że wszystkich takich permutacjipermutacji jest .
Zauważmy, że po usunięciu zer z tak otrzymanej permutacjipermutacji dostaniemy -elementową permutacjępermutację, której kolejne elementy tworzą liczbę -cyfrową spełniającą warunki zadania.
Pokazaliśmy w ten sposób, że każdej liczbie -cyfrowej spełniającej warunki zadania odpowiada dokładnie jedna permutacja -elementowa, w której na miejscach o numerach parzystych rozmieszczone są elementy ze zbioru , a na pozostałych miejscach rozmieszczone są: , i cztery zera.
Wynika stąd, że wszystkich -cyfrowych liczb naturalnych, które spełniają warunki zadania jest .
Rozpatrujemy wszystkie permutacjepermutacje siedmioelementowego zbioru . 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 używając do tego elementów .
Postępujemy podobnie, jak w poprzednim przykładzie.
Rozpatrujemy -elementową permutacjępermutację , w której:
na miejscach o indeksach parzystych rozmieszczamy cyfry ze zbioru (można to zrobić na sposoby),
na wybranych trzech spośród miejsc o indeksach nieparzystych rozmieszczamy elementy ze zbioru (można to zrobić na sposobów),
na każdym spośród pozostałych miejsc wstawiamy (co można zrobić na sposób).
Korzystając z reguły mnożeniareguły mnożenia stwierdzamy, że wszystkich takich permutacjipermutacji jest .
Na koniec zauważamy, że każdej permutacjipermutacji spełniającej warunki zadania można wzajemnie jednoznacznie przypisać ciąg -elementowy, który tworzymy w sposób opisany powyżej.
Oznacza to, że jest wszystkich permutacjipermutacji siedmioelementowego zbioru , w których iloczyn każdych dwóch kolejnych elementów jest liczbą parzystą.
Z wyrazów -elementowego zbioru 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 ) nie są zapisane na sąsiednich miejscach.
Uwaga. Przykładowym ciągiem spełniającym warunki zadania jest .
Rozwiązanie
Zauważmy, że permutacja zbioru spełnia warunki zadania wtedy i tylko wtedy, gdy rozdzielimy elementy: , używając do tego elementów: .
Postępujemy podobnie, jak w poprzednich przykładach.
Rozpatrujemy -elementową permutacjępermutację , w której:
na miejscach o indeksach parzystych rozmieszczamy litery ze zbioru (możemy to zrobić na sposobów),
na wybranych czterech spośród miejsc o indeksach nieparzystych rozmieszczamy elementy ze zbioru (można to zrobić na sposobów),
na każdym spośród pozostałych miejsc wstawiamy (co można zrobić na sposób).
Korzystając z reguły mnożeniareguły mnożenia stwierdzamy, że wszystkich tak utworzonych permutacjipermutacji jest .
Ostatecznie zauważamy, że każdemu ciągowi spełniającemu warunki zadania można wzajemnie jednoznacznie przypisać -elementową permutacjępermutację, którą tworzymy w sposób opisany powyżej.
Oznacza to, że jest wszystkich permutacjipermutacji -elementowego zbioru , w których żadne dwie samogłoski nie są zapisane na sąsiednich miejscach.
Grupę osób, wśród których jest dorosłych oraz sześcioro dzieci: Ania, Basia, Czarek, Damian, Ewa i Franek, należy rozsadzić w rzędzie, w którym jest 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ż .
Rozwiązanie
Zauważmy, że rozmieszczenie opisanej w treści zadania grupy osób spełnia warunki zadania wtedy i tylko wtedy, gdy rozdzielimy każde spośród 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 -elementową permutacjępermutację , w której:
na miejscach o indeksach nieparzystych rozmieszczamy wszystkich dorosłych (możemy to zrobić na sposobów),
na wybranych sześciu spośród miejsc o indeksach parzystych rozmieszczamy dzieci (można to zrobić na sposobów),
każde spośród pozostałych miejsc pozostawiamy puste.
Korzystając z reguły mnożeniareguły mnożenia stwierdzamy, że wszystkich tak utworzonych permutacjipermutacji jest
.
Na koniec zauważmy, że jeżeli z rozpatrywanej powyżej permutacjipermutacji -elementowej usuniemy elementy puste, a następnie ponumerujemy od do kolejne elementy tak otrzymanej permutacji -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 wszystkich takich rozmieszczeń omawianej grupy osób, że każde z dzieci będzie siedziało pomiędzy dorosłymi.
Ostatecznie stwierdzamy, że .
W ten sposób zakończyliśmy 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