Przeczytaj
Na początek pokażemy przykłady typowych zadań, które odwołują się do elementów zbioru, w czytelny sposób dającego się podzielić na podzbiory dwuelementowe.
Rozpatrujemy ośmiocyfrowe liczby naturalne o różnych cyfrach wybranych ze zbioru . Obliczymy, ile jest wśród nich takich liczb, których zapis spełnia jednocześnie cztery warunki:
cyfra jest zapisana przed cyfrą ,
cyfra jest zapisana przed cyfrą ,
cyfra jest zapisana przed cyfrą ,
cyfra jest zapisana przed cyfrą .
Rozwiązanie
sposób:
Liczbę spełniającą warunki zadania będziemy konstruować w czterech etapach, odpowiadających narzuconym warunkom.
W pierwszym etapie wybierzemy dwa miejsca (spośród ośmiu dostępnych w zapisie dziesiętnym danej liczby) dla cyfr oraz : możemy to zrobić na sposobów. Następnie zapisujemy na tych miejscach cyfry oraz tak, aby cyfra była zapisana przed cyfrą – możemy to zrobić na jeden sposób.
W drugim etapie wybierzemy dwa miejsca (spośród sześciu pozostałych w zapisie dziesiętnym danej liczby) dla cyfr oraz : możemy to zrobić na sposobów. Następnie zapisujemy na tych miejscach cyfry oraz tak, aby cyfra była zapisana przed cyfrą – możemy to zrobić na jeden sposób.
W trzecim etapie wybierzemy dwa miejsca (spośród czterech pozostałych w zapisie dziesiętnym danej liczby) dla cyfr oraz : możemy to zrobić na sposobów. Następnie zapisujemy na tych miejscach cyfry oraz tak, aby cyfra była zapisana przed cyfrą – możemy to zrobić na jeden sposób.
W czwartym etapie na ostatnich dwóch miejscach zapisujemy cyfry oraz tak, aby cyfra była zapisana przed cyfrą – możemy to zrobić na jeden sposób.
Korzystając z reguły mnożeniareguły mnożenia, obliczamy, że liczb spełniających warunki zadania jest .
sposób
Ośmiocyfrową liczbę naturalną o różnych cyfrach wybranych ze zbioru utożsamiamy z permutacją zbioru , skąd dostajemy, że wszystkich rozpatrywanych ośmiocyfrowych liczb naturalnych jest tyle, ile jest wszystkich permutacji zbioru , czyli .
Rozważmy dowolną permutację zbioru . W takim ciągu pewne dwa miejsca zajmują elementy oraz – załóżmy, że i , gdzie i .
Zamieniając miejscami elementy i dostaniemy permutację, w której i . W dokładnie jednym z dwóch omówionych właśnie przypadków element jest zapisany przed elementem .
Zatem – korzystając z reguły równolicznościreguły równoliczności – stwierdzamy, że połowa spośród wszystkich rozpatrywanych liczb spełnia pierwszy warunek: cyfra jest zapisana przed cyfrą . Liczb ośmiocyfrowych spełniających pierwszy warunek jest więc .
Rozważmy teraz taką permutację zbioru , w której element jest zapisany przed elementem . W takim ciągu pewne dwa miejsca zajmują elementy oraz . Rozumując podobnie jak powyżej otrzymujemy następujący wniosek: jeżeli w tej permutacji zamienimy miejscami elementy i , to w jednej z tych dwóch permutacji element jest zapisany przed elementem .
Stwierdzamy więc, ponownie korzystając z reguły równolicznościreguły równoliczności, że połowa spośród rozpatrywanych liczb spełniających pierwszy warunek spełnia również drugi warunek: cyfra jest zapisana przed cyfrą . Stąd liczb spełniających warunki (1) i (2) jest .
Rozważamy z kolei taką permutację zbioru , w której element jest zapisany przed elementem oraz element jest zapisany przed elementem .
Kolejny raz rozumujemy podobnie, jak to było zaprezentowane wcześniej i na tej podstawie stwierdzamy, że połowa spośród rozpatrywanych liczb spełniających warunki (1) i (2) spełnia również trzeci warunek: cyfra jest zapisana przed cyfrą . Oznacza to, że liczb spełniających warunki (1), (2) oraz (3) jest .
Na koniec rozważamy taką permutację zbioru , w której element jest zapisany przed elementem , element jest zapisany przed elementem oraz element jest zapisany przed elementem .
Rozumując podobnie, jak to zaprezentowane było powyżej stwierdzamy, że połowa spośród rozpatrywanych liczb spełniających warunki (1), (2) oraz (3) spełnia też czwarty warunek: cyfra jest zapisana przed cyfrą .
Podsumowując stwierdzamy, że liczb spełniających wszystkie cztery warunki jest .
Uwaga. Wykorzystując rozwiązanie zadania z powyższego przykładu, zauważymy, że ośmiocyfrowych liczb naturalnych, w których zapisie występują dwie jedynki, dwie trójki, dwie piątki i dwie siódemki ( to przykładowa liczba spełniająca te warunki) jest .
Wystarczy w tym celu zauważyć, że:
jeżeli w liczbie spełniającej powyższe warunki zamienimy: drugą jedynkę na dwójkę, drugą trójkę na czwórkę, drugą piątkę na szóstkę oraz drugą siódemkę na ósemkę, to otrzymamy liczbę rozpatrywaną w powyższym przykładzie,
jeżeli w liczbie spełniającej warunki podane w przykładzie zamienimy: dwójkę na jedynkę, czwórkę na trójkę, szóstkę na piątkę oraz ósemkę na siódemkę, to otrzymamy liczbę ośmiocyfrową, w której zapisie występują dwie jedynki, dwie trójki, dwie piątki i dwie siódemki.
Takie wzajemnie jednoznaczne przyporządkowanie pokazuje, że liczb w tych dwóch zbiorach jest tyle samo, a więc liczb spełniających podane warunki jest .
Rozumując podobnie, jak w rozwiązaniu sposobem drugim, można pokazać, że:
ośmioliterowych wyrazów, w których zapisie występują dwie litery ‘a’, dwie litery ‘i’, dwie litery ‘k’ oraz dwie litery ‘t’ (‘tikitaka’ to przykładowy wyraz spełniający te warunki) jest ,
siedmiocyfrowych liczb naturalnych, w których zapisie występują dwie jedynki, dwie trójki oraz trzy piątki jest ,
jest –elementowych permutacji, w których parami różne elementy powtarzają się odpowiednio razy, przy czym .
Uwaga 2. Permutację, w której dopuszczalne są powtórzenia elementów, nazywa się permutacją z powtórzeniami.
Ze zbioru dwudziestu początkowych dodatnich liczb całkowitych losujemy –elementowy podzbiór. Obliczymy, ile spośród wszystkich wyników takiego losowania spełnia warunek: suma największego i najmniejszego elementu wylosowanego podzbioru jest równa .
Rozwiązanie
Zauważmy, że w podanym zbiorze jest par liczb, których suma jest równa :
i , i , i , i , i , i , i , i , i oraz i .
Dla dwóch ostatnich par liczb warunki zadania nie będą spełnione, wobec tego możliwe są następujące rozłączne przypadki:
najmniejszy i największy element to odpowiednio i . Wtedy podzbiór spełniający warunki zadania tworzą, wraz z tymi dwoma elementami, trzy elementy wybrane z –elementowego zbioru . W tym przypadku możliwych podzbiorów jest tyle,ile jest –elementowych kombinacji zbioru –elementowego, czyli ,
najmniejszy i największy element to odpowiednio i . Wtedy podzbiór spełniający warunki zadania tworzą, wraz z tymi dwoma elementami, trzy elementy wybrane z –elementowego zbioru . W tym przypadku możliwych podzbiorów jest tyle, ile jest –elementowych kombinacji zbioru –elementowego, czyli ,
najmniejszy i największy element to odpowiednio i . Wtedy podzbiór spełniający warunki zadania tworzą, wraz z tymi dwoma elementami, trzy elementy wybrane z –elementowego zbioru . W tym przypadku możliwych podzbiorów jest tyle, ile jest –elementowych kombinacji zbioru –elementowego, czyli ,
najmniejszy i największy element to odpowiednio i . Wtedy podzbiór spełniający warunki zadania tworzą, wraz z tymi dwoma elementami, trzy elementy wybrane z –elementowego zbioru . W tym przypadku możliwych podzbiorów jest tyle, ile jest –elementowych kombinacji zbioru –elementowego, czyli ,
najmniejszy i największy element to odpowiednio i . Wtedy podzbiór spełniający warunki zadania tworzą, wraz z tymi dwoma elementami, trzy elementy wybrane z –elementowego zbioru . W tym przypadku możliwych podzbiorów jest tyle, ile jest –elementowych podzbiorów zbioru –elementowego, czyli ,
najmniejszy i największy element to odpowiednio i . Wtedy podzbiór spełniający warunki zadania tworzą, wraz z tymi dwoma elementami, trzy elementy wybrane z –elementowego zbioru . W tym przypadku możliwych podzbiorów jest tyle, ile jest –elementowych kombinacji zbioru –elementowego, czyli ,
najmniejszy i największy element to odpowiednio i . Wtedy podzbiór spełniający warunki zadania tworzą, wraz z tymi dwoma elementami, trzy elementy wybrane z –elementowego zbioru . W tym przypadku możliwych podzbiorów jest tyle, ile jest –elementowych kombinacji zbioru –elementowego, czyli ,
najmniejszy i największy element to odpowiednio i . Wtedy podzbiór spełniający warunki zadania tworzą, wraz z tymi dwoma elementami, trzy elementy wybrane z –elementowego zbioru . W tym przypadku możliwych podzbiorów jest tyle, ile jest –elementowych kombinacji zbioru –elementowego, czyli .
Podsumowując, stwierdzamy, że wszystkich wyników losowania, które spełniają podany warunek jest .
Rozpatrzmy liczby -cyfrowe o różnych cyfrach wybranych ze zbioru .
Obliczymy, ile jest wśród nich takich liczb, w których równe są następujące cztery sumy:
– pierwszej i drugiej cyfry,
– trzeciej i czwartej cyfry,
– piątej i szóstej cyfry,
– siódmej i ósmej cyfry.
Rozwiązanie
Ponieważ suma wszystkich cyfr opisanej liczby -cyfrowej jest równa , więc .
Zauważmy, że zbiór możemy następująco rozbić na cztery dwuelementowe podzbiory tak, żeby suma elementów w każdym podzbiorze była równa :
.
Dalszą część rozwiązania przedstawimy dwoma sposobami.
sposób:
Liczbę spełniającą warunki zadania będziemy konstruować w czterech etapach, odpowiadających narzuconym warunkom.
W pierwszym etapie wybierzemy pierwszą cyfrę, co możemy zrobić na sposobów, a następnie dopiszemy do niej drugą, która - ze względu na wybraną pierwszą cyfrę - jest już wyznaczona jednoznacznie.
W drugim etapie spośród niewybranych jeszcze cyfr wybierzemy trzecią cyfrę, co możemy zrobić na sposobów, a następnie dopiszemy do niej czwartą cyfrę, która po wyborze trzeciej cyfry jest wyznaczona jednoznacznie.
W trzecim etapie spośród cyfr niewybranych w dwóch pierwszych etapach wybierzemy piątą cyfrę, co możemy zrobić na sposoby, a następnie dopiszemy do niej szóstą cyfrę, która po wyborze piątej cyfry jest wyznaczona jednoznacznie.
W czwartym etapie pozostaje nam rozmieścić pozostałe dwie cyfry na ostatnich dwóch miejscach, co możemy zrobić na sposoby.
Korzystając z reguły mnożeniareguły mnożenia, obliczamy, że wszystkich liczb spełniających warunki zadania jest .
sposób:
Ponieważ:
sposobów podziału liczb ze zbioru na cztery sumy jest tyle, ile jest permutacji zbioru –elementowego, czyli ,
w każdej z tak otrzymanych czterech sum ustalimy kolejność składników na sposoby,
więc liczb spełniających warunki zadania jest .
W szufladzie znajduje się par rękawiczek, przy czym każde dwie spośród tych par są w różnych kolorach. Losujemy z tej szuflady rękawiczek. Obliczymy, ile jest takich wyników tego losowania, że:
wśród wylosowanych nie będzie żadnej pary rękawiczek,
wśród wylosowanych będzie dokładnie jedna para rękawiczek,
wśród wylosowanych będą dokładnie dwie pary rękawiczek,
wśród wylosowanych będą dokładnie trzy pary rękawiczek.
Rozwiązanie
Dobieramy w pary, zgodnie z kolorem, rękawiczki znajdujące się w szufladzie, a następnie numerujemy te pary od do . Każdej z tak ponumerowanych par przypisujemy liczbę (gdzie ) rękawiczek wylosowanych z tej pary.
Ponieważ:
z każdej pary możemy wylosować co najwyżej rękawiczki, więc , dla ,
w sumie mamy wylosować rękawiczek, więc .
Zauważmy następnie, że:
wśród wylosowanych nie będzie żadnej pary rękawiczek wtedy i tylko wtedy, gdy w ciągu żaden element nie będzie równy , dokładnie elementów będzie równych (możliwych wyborów jest więc tyle, ile jest –elementowych kombinacji zbioru –elementowego) i pozostałe elementy będą równe . Wszystkich takich ciągów jest zatem ;
wśród wylosowanych będzie dokładnie jedna para rękawiczek wtedy i tylko wtedy, gdy w ciągu dokładnie element będzie równy (można go wybrać na sposobów), dokładnie elementów będzie równych (możliwych wyborów jest więc tyle, ile jest –elementowych kombinacji zbioru –elementowego) i pozostałe elementy będą równe . Oznacza to, że wszystkich takich ciągów jest ;
wśród wylosowanych będą dokładnie dwie pary rękawiczek wtedy i tylko wtedy, gdy w ciągu dokładnie elementy będą równe (możliwych wyborów jest więc tyle, ile jest –elementowych kombinacji zbioru –elementowego), dokładnie elementy będą równe (możliwych wyborów jest więc tyle, ile jest –elementowych kombinacji zbioru –elementowego) i każdy z pozostałych elementów będzie równy . Wobec tego wszystkich takich ciągów jest ;
wśród wylosowanych będą dokładnie trzy pary rękawiczek wtedy i tylko wtedy, gdy w ciągu dokładnie elementy będą równe (możliwych wyborów jest więc tyle, ile jest –elementowych kombinacji zbioru –elementowego), dokładnie element będzie równy (można go wybrać na sposobów) i każdy z pozostałych elementów będzie równy . Stąd wszystkich takich ciągów jest .
Ponieważ jedną rękawiczkę z ustalonej pary możemy wybrać na dwa sposoby, więc ostatecznie otrzymujemy, że:
jest możliwych wyników losowania takich, że wśród wylosowanych nie będzie żadnej pary rękawiczek,
jest możliwych wyników losowania takich, że wśród wylosowanych będzie dokładnie jedna para rękawiczek,
jest możliwych wyników losowania takich, że wśród wylosowanych będą dokładnie dwie pary rękawiczek,
możliwych wyników losowania takich, że wśród wylosowanych będą dokładnie trzy pary rękawiczek.
Dla podsumowania zauważmy, że
.
Rozpatrzmy zbiór . Obliczymy, ile jest takich podzbiorów zbioru , które wśród swoich elementów nie mają pary liczb o sumie równej .
Rozwiązanie
Zauważmy, że w podanym zbiorze jest par liczb, których suma jest równa :
i , i , i , i , i . Bez pary pozostaje element .
Podzbiór spełniający warunki zadania będziemy konstruowali w etapach:
w etapie wybierzemy podzbiór zbioru ; ze wszystkich czterech podzbiorów tego zbioru nie możemy wybrać jedynie całego zbioru , a więc pozostają nam możliwości,
w etapie wybierzemy podzbiór zbioru ; ze wszystkich czterech podzbiorów tego zbioru nie możemy wybrać jedynie całego zbioru , wobec tego pozostają nam możliwości,
w etapie wybierzemy podzbiór zbioru ; ze wszystkich czterech podzbiorów tego zbioru nie możemy wybrać jedynie całego zbioru , co oznacza, że pozostają nam możliwości,
w etapie wybierzemy podzbiór zbioru ; ze wszystkich czterech podzbiorów tego zbioru nie możemy wybrać jedynie całego zbioru , a więc pozostają nam możliwości,
w etapie wybierzemy podzbiór zbioru ; ze wszystkich czterech podzbiorów tego zbioru nie możemy wybrać jedynie całego zbioru , zatem pozostają nam możliwości,
w etapie wybierzemy podzbiór zbioru ; tym razem możemy wybrać każdy podzbiór tego zbioru, wobec tego mamy możliwości.
Korzystając z reguły mnożeniareguły mnożenia, obliczamy, że podzbiorów spełniających warunki zadania jest .
Słownik
każdy –elementowy podzbiór zbioru –elementowego, gdzie , nazywamy –elementową kombinacją tego zbioru –elementowego
liczba wszystkich –elementowych kombinacji zbioru –elementowego, gdzie , 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
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
każdy ciąg utworzony ze wszystkich elementów zbioru –elementowego
liczba wszystkich permutacji zbioru –elementowego jest równa