Przeczytaj
W tej lekcji rozpatrywać będziemy doświadczenia, które polegają na ustawieniu w pewnej kolejności wszystkich wyrazów zbioru –elementowego. Każdy otrzymany w ten sposób ciąg będziemy nazywać permutacją tego zbioru –elementowego.
Zauważmy, że na podstawie reguły mnożenia natychmiast stwierdzimy, że liczba wszystkich permutacji zbioru –elementowego jest równa .
Zauważmy też, że permutacja zbioru –elementowego jest –elementową wariacją bez powtórzeń tego zbioru.
Każdy ciąg utworzony ze wszystkich elementów zbioru –elementowego nazywamy permutacją tego zbioru.
Liczba wszystkich permutacji zbioru -elementowego określona jest wzorem
Dany jest zbiór . Obliczymy, ile jest wszystkich funkcji różnowartościowych o argumentach ze zbioru i wartościach w zbiorze .
Rozwiązanie
Przypuśćmy, że funkcja spełnia warunki zadania i zapiszmy wartości przyporządkowane do każdego z kolejnych, rosnąco zapisywanych argumentów: najpierw , następnie , z kolei i tak dalej aż do . Otrzymany w ten sposób –elementowy ciągciąg jest permutacjąpermutacją zbioru . Zatem wszystkich funkcji, które spełniają warunki zadania jest tyle, ile permutacjipermutacji tego zbioru, czyli
Przeanalizujemy przykład przytoczony przez Juliana Tuwima w jego zbiorku „Cicer cum caule, czyli groch z kapustą” (treść podajemy za wydaniem: Czytelnik, Warszawa 1958–59)
„Za czasów studenckich jadałem „smaczne domowe obiady na maśle” u jakiejś zdeklasowanej bałtyckiej baronessy, bardzo ważnej, sztywnej i pedantycznej damy. Obiady były doprawdy smaczne, więc nasza ekipa – czternaście osób – przez dłuższy czas zasiadała przy podłużnym stole w niezmienionym składzie. I każdy miał swoje wyznaczone miejsce, którego nie wolno było zmieniać.
Jako najmłodszemu, przypadło mi miejsce na szarym końcu, a że służąca, postać również nadęta i pedantyczna, obnosiła półmiski zawsze w tej samej kolejności, zaczynając od jakiegoś b. carskiego huzara, a kończąc na mnie, dostawały mi się zazwyczaj żałosne resztki potraw.
Gdy kiedyś zaproponowałem łagodnie, aby stołownicy przesuwali się co dzień o jedno krzesło naprzód, projekt mój spotkał się z takim zabójczym spojrzeniem baronessy, że co prędzej zamilkłem.
Ale nie dałem za wygraną. Nazajutrz wystąpiłem z nowym, znacznie radykalniejszym projektem rozmieszczenia ludzi przy stole.
Co dzień, powiedziałem, będziemy siadać w innym porządku, aż się wyczerpią wszystkie możliwe kombinacje tych przesiadań.
Ale madame była nieugięta – a pewien starszy pan uśmiechał się tylko i kręcił głową.
Po godzinie okazało się, że pomysł mój był absurdalny, po prostu obłąkany.
Po obiedzie starszy pan zaprosił mnie na kawę do pobliskiej cukierni.
– Więc pan chciałby przesadzać czternaście osób, co dzień w innej kolejności, aż do wyczerpania wszystkich możliwych kombinacji, czy tak?
– Tak jest, proszę pana.
– I co pan sądzi, jak to długo będzie trwało, aż pan te wszystkie możliwe kombinacje wyczerpie?
– No, nie wiem... może nawet parę tygodni... ale musi być sprawiedliwość.
– Owszem, musi być - odrzekł fundator kawy i zaczął coś obliczać ołówkiem na marmurze stolika.
Po paru minutach powiedział:
– Ale będzie to, panie drogi, trwało - niech pan słucha: dwieście trzydzieści osiem milionów osiemset czterdzieści cztery tysiące sześćset trzydzieści trzy lata.
Osłupiałem, myśląc, że mam do czynienia z wariatem.
– Jak to? 14 osób musi się przesiadać blisko 239 milionów lat, aby wyczerpać wszystkie możliwe sąsiedztwa? Pan sobie chyba ze mnie kpi!
Czarnym ołówkiem na białym marmurze dowiódł mi ów pan (nauczyciel matematyki w gimnazjum), że ma rację.”
Na podstawie treści zadania domyślamy się, że ów starszy pan, fundator kawy, przedstawił następujące rachunki:
Wszystkich rozmieszczeń grupy stołowników na dostępnych im różnych miejscach jest , czyli .
Wiemy, że jest ich dokładnie tyle, ponieważ każde takie rozmieszczenie jest –elementową permutacjąpermutacją tego zbioru.
Z przedstawionego w opowiadaniu wniosku wynika, że przyjęto tam dni na rok, skąd właśnie wzięta jest przedstawiona tam liczba: roku.
Gdyby przyjąć trochę dokładniej, że rok trwa dnia, to wynikiem byłoby roku, co nadal jest liczbą, która - zapewne - również zdumiałaby narratora przytoczonego opowiadania.
Tworzymy liczby ośmiocyfrowe o różnych cyfrach, wśród których nie ma cyfr oraz . Obliczymy, ile jest wszystkich takich liczb, w których zapisie dziesiętnym cyfry oraz zapisane są obok siebie.
Rozwiązanie
Zauważmy, że każda liczba ośmiocyfrowa utworzona za pomocą różnych cyfr ze zbioru może być wzajemnie jednoznacznie utożsamiona z ośmioelementowym ciągiem kolejnych cyfr zapisu dziesiętnego tej liczby. Naszym zadaniem jest więc wyznaczenie wszystkich permutacjipermutacji zbioru , w których elementy i sąsiadują ze sobą. Rozwiązanie tego problemu przedstawimy na dwa sposoby.
sposób:
Jeśli w takiej –elementowej permutacjipermutacji ustalimy parę sąsiednich miejsc dla cyfr i , to te dwie liczby możemy na ustalonych miejscach rozmieścić na sposobów, a inne elementów rozmieścimy na pozostałych miejscach na sposobów. Ponieważ możliwe pary sąsiednich miejsc to: i lub i , lub i , lub i , lub i , lub i , lub i , więc jest ich do wyboru . Zatem, korzystając z reguły mnożeniareguły mnożenia, otrzymujemy ostatecznie, że wszystkich liczb spełniających warunki zadania jest
.
sposób:
Rozpatrujemy wszystkie permutacjepermutacje zbioru –elementowego , których jest . Jeżeli w każdej z nich uwzględnimy możliwe permutacjepermutacje elementu , których jest , to w efekcie otrzymamy permutacjępermutację zbioru , w której elementy i sąsiadują ze sobą.
Na podstawie reguły mnożeniareguły mnożenia, otrzymujemy więc, że wszystkich liczb spełniających warunki zadania jest
.
Rozpatrujemy wszystkie sześciocyfrowe liczby naturalne o różnych cyfrach. Obliczymy, ile jest wśród nich takich liczb, których suma wszystkich cyfr jest większa od .
Rozwiązanie
Zauważmy, że największa możliwa suma cyfr liczby sześciocyfrowej o różnych cyfrach jest równa .
Ponadto:
sumę cyfr równą dostaniemy tylko wtedy, gdy cyframi będą , , , , oraz ,
sumę cyfr równą dostaniemy jedynie w dwóch przypadkach: gdy cyframi będą , , , , oraz , a także, gdy cyframi będą , , , , oraz ,
sumę cyfr równą dostaniemy tylko w trzech przypadkach: gdy cyframi będą , , , , oraz lub gdy cyframi będą , , , , oraz , a także, gdy cyframi będą , , , , oraz .
Ponieważ liczbę sześciocyfrową o różnych cyfrach można zapisać za pomocą sześciu różnych cyfr na sposobów, a wszystkich przypadków, w których taka liczba spełnia warunki zadania jest , więc wszystkich sześciocyfrowych liczb naturalnych o różnych cyfrach, których suma wszystkich cyfr jest większa od jest
.
Obliczymy, ile jest wszystkich permutacjipermutacji zbioru , w których pierwszym wyrazem nie jest , a drugim jest .
Rozwiązanie
Niech będzie permutacjąpermutacją zbioru .
Jeżeli taka permutacjapermutacja spełnia warunki zadania, to i .
Ponieważ jest ustalone (mówimy też, że jest punktem stałym tej permutacjipermutacji), więc wystarczy obliczyć, ile jest permutacjipermutacji zbioru , w których .
Rozwiązanie przedstawimy na trzy sposoby.
sposób:
Skorzystamy z reguły mnożeniareguły mnożenia. Ponieważ można wybrać na sposobów (tyle jest możliwości wyboru liczby różnej od spośród dostępnych) oraz przy każdym z dokonanych w ten sposób wyborów pozostałe elementów rozmieszczamy na pozostałych miejscach, więc wszystkich możliwości jest
sposób:
Skorzystamy z reguły dodawania. Wszystkich permutacjipermutacji zbioru jest
Wśród nich wyróżnimy dwie rozłączne grupy:
w pierwszej znajdą się te permutacjepermutacje, w których
w drugiej pozostałe, czyli te, w których .
Ponieważ tych ostatnich jest (po ustaleniu pierwszego wyrazu permutacjipermutacji pozostaje rozmieścić wyrazów na miejscach), więc wszystkich permutacjipermutacji w pierwszej grupie jest .
sposób:
Skorzystamy z reguły równoliczności. Wszystkich permutacjipermutacji zbioru jest
Ze względu na wartość można je podzielić na równolicznych grup, przy czym w przypadkach, tzn. wtedy, gdy spełnione są warunki zadania. A więc wszystkich takich permutacjipermutacji jest
Słownik
Każdy ciąg utworzony ze wszystkich elementów zbioru –elementowego.
funkcja, której dziedziną jest zbiór wszystkich dodatnich liczb całkowitych lub pewien jego podzbiór, a wartościami są liczby rzeczywiste
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