Przeczytaj
W poprzednich materiałach z kombinatoryki pojawiały się przykłady i zadania dotyczące np. liczb naturalnych o ustalonej sumie cyfr. Proponowane rozwiązania zadań tego typu oparte były na rozpatrywaniu przypadków (z zasady: rozłącznych) i stosowaniu podstawowych reguł kombinatorycznych: reguły dodawaniareguły dodawania oraz reguły mnożeniareguły mnożenia.
Pokażemy, że w pewnych przykładach postawiony w zadaniu problem możemy zinterpretować za pomocą tzw. modelu przegródkowego.
W pierwszym przykładzie omówimy konstrukcję tego modelu w szczególnym przypadku: liczb o sumie cyfr równej .
Rozpatrujemy wszystkie –cyfrowe liczby naturalne o sumie cyfr równej .
Ile jest wśród nich takich liczb, które w zapisie dziesiętnym mają wyłącznie cyfry parzyste?
Rozwiązanie
Rozpatrzmy równanie
,
w którym każda z liczb jest nieujemną liczbą całkowitą.
Wówczas:
liczba spełnia warunek ,
każda z liczb spełnia warunek , gdzie .
Wtedy liczba, której kolejnymi cyframi są jest –cyfrowa i spełnia warunki zadania.
Oznacza to, że każdej rozpatrywanej liczbie, w której zapisie występują jedynie cyfry parzyste można wzajemnie jednoznacznie przypisać –elementowy ciąg liczb nieujemnych.
Równanie, które spełniają te liczby
przekształcamy jak poniżej
.
Stąd otrzymujemy, że wszystkich rozpatrywanych liczb jest tyle, ile jest rozwiązań równania
w nieujemnych liczbach całkowitych .
Każde poszczególne rozwiązanie powyższego równania, a więc jednocześnie: każdą liczbę –cyfrową o cyfrach parzystych i sumie cyfr równej , możemy przedstawić jako rozmieszczenie nierozróżnialnych obiektów w ponumerowanych pudełkach.
Takie rozmieszczenie zilustrujemy graficznie, używając przegródek '' do pokazania zawartości kolejnych pudełek, w których rozmieszczamy dwa obiekty przedstawione za pomocą symbolu kropki ‘’.
Np. rozwiązanie, w którym
(jest to przedstawienie liczby ) ma następującą ilustrację graficzną
,
natomiast ilustracja
przedstawia rozwiązanie równania, w którym (jest to przedstawienie liczby ).
Zauważmy, że dla jednoznacznego przedstawienia rozdziału obiektów '' w ponumerowanych pudełkach można pominąć obie skrajne przegródki.
Wtedy ilustrację rozwiązania, w którym
przedstawimy jako –elementowy ciąg
,
a –elementowy ciąg
przedstawia rozwiązanie równania, w którym
.
Rozpatrzmy więc dowolny –elementowy ciąg, składający się z przegródek () oraz dwóch kropek ().
Przyjmujemy oznaczenia:
to liczba kropek () ustawionych przed pierwszą (patrząc od lewej) przegródką,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer .
Wtedy każdemu rozmieszczeniu elementów ciągu składającego się z przegródek i kropek odpowiada wzajemnie jednoznacznie ciąg nieujemnych liczb całkowitych, które spełniają równanie .
Ponieważ wszystkich –elementowych ciągów składającego się z przegródek i kropek jest tyle, ile jest –elementowych kombinacji zbioru –elementowego, czyli , więc dokładnie tyle jest wszystkich –cyfrowych liczb naturalnych o sumie cyfr równej .
Obliczymy, ile jest wszystkich wyników dziesięciokrotnego rzutu kostką sześcienną, w których suma liczb wyrzuconych oczek jest równa .
Rozwiązanie
Rozpatrzmy równanie
,
w którym każda z liczb jest nieujemną liczbą całkowitą.
Po przekształceniu tego równania do postaci
stwierdzamy, że każda z liczb może przyjmować wyłącznie wartości ze zbioru .
Zatem każdemu wynikowi dziesięciokrotnego rzutu kostką spełniającemu warunki zadania można wzajemnie jednoznacznie przypisać –elementowy ciąg nieujemnych liczb całkowitych.
Oznacza to, że wszystkich wyników rozpatrywanego rzutu kostką jest tyle, ile jest rozwiązań równania
w nieujemnych liczbach całkowitych .
Każde poszczególne rozwiązanie powyższego równania możemy przedstawić jako rozmieszczenie nierozróżnialnych obiektów w ponumerowanych pudełkach, co można zilustrować graficznie, używając przegródek '' do pokazania zawartości kolejnych pudełek, w których rozmieszczamy pięć obiektów przedstawionych za pomocą symbolu kropki ‘’.
Rozumując podobnie jak w poprzednim przykładzie zauważamy, że do jednoznacznego przedstawienia rozdziału obiektów '' w ponumerowanych pudełkach wystarczy użyć przegródek.
Wtedy ilustrację rozwiązania, w którym
(w ten sposób opisaliśmy –krotny rzut kostką, w którym kolejne uzyskane liczby oczek to ) przedstawimy jako –elementowy ciąg
,
a –elementowy ciąg
przedstawia rozwiązanie równania, w którym
(w ten sposób opisaliśmy –krotny rzut kostką, w którym kolejne uzyskane liczby oczek to ).
Rozpatrzmy więc dowolny –elementowy ciąg, składający się z przegródek () oraz elementów ().
Przyjmujemy oznaczenia:
to liczba kropek () ustawionych przed pierwszą (patrząc od lewej) przegródką,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer i przed przegródką numer ,
to liczba kropek ustawionych za przegródką numer .
Wtedy każdemu rozmieszczeniu elementów ciągu składającego się z przegródek i kropek odpowiada wzajemnie jednoznacznie ciąg nieujemnych liczb całkowitych, które spełniają równanie .
Ponieważ wszystkich –elementowych ciągów składających się z przegródek i kropek jest tyle, ile jest -elementowych kombinacji zbioru -elementowego-elementowych kombinacji zbioru -elementowego, czyli , więc dokładnie tyle jest wszystkich wyników dziesięciokrotnego rzutu kostką sześcienną, w których suma liczb wyrzuconych oczek jest równa .
Zauważmy, że w obu powyższych przykładach postawiony problem sprowadziliśmy do ustalenia, ile jest rozwiązań równania
w nieujemnych liczbach całkowitych , gdzie oraz to ustalone dodatnie liczby całkowite.
Rozumując analogicznie jak w powyższych dwóch przykładach pokażemy, że rozwiązań tego równania jest .
Rozpatrzmy w tym celu ciąg, który ma elementów i składający się z przegródek (oznaczymy każdą z nich symbolem ‘’) oraz elementów oznaczonych symbolem kropki ‘’.
Oznaczmy przez:
– liczbę kropek () ustawionych przed pierwszą (patrząc od lewej) przegródką,
– liczbę kropek ustawionych za przegródką numer i przed przegródką numer , dla ,
– liczbę kropek ustawionych za przegródką numer .
Zauważmy, że każdemu rozmieszczeniu wszystkich elementów tego ciągu składającego się z przegródek ‘’ i kropek odpowiada wzajemnie jednoznacznie ciąg nieujemnych liczb całkowitych, które spełniają równanie .
Ponieważ wszystkich ()–elementowych ciągów składającego się z przegródek i kropek jest tyle, ile jest –elementowych kombinacjikombinacji zbioru ()–elementowego, czyli , więc dokładnie tyle jest wszystkich rozwiązań równania
w nieujemnych liczbach całkowitych , gdzie oraz to ustalone dodatnie liczby całkowite.
Liczba wszystkich rozwiązań równania
w nieujemnych liczbach całkowitych , gdzie oraz to ustalone dodatnie liczby całkowite, jest równa
a) Obliczymy, ile jest wszystkich –cyfrowych liczb naturalnych o wszystkich cyfrach nieparzystych, których suma cyfr jest równa .
Rozwiązanie
Rozpatrzmy równanie
, w którym każda z liczb jest nieujemną liczbą całkowitą.
Przekształcamy to równanie do postaci
,
skąd otrzymujemy
.
Oznacza to, że dla , a więc każda z liczb jest dodatnią liczbą naturalną, która jest nieparzysta i nie jest większa od .
Wynika stąd, że ogółem –cyfrowych liczb naturalnych o wszystkich cyfrach nieparzystych i sumie cyfr równej jest dokładnie tyle, ile jest rozwiązań równania
w nieujemnych liczbach całkowitych .
Ponieważ wszystkich rozwiązań powyższego równania jest ,
więc ogółem –cyfrowych liczb naturalnych o wszystkich cyfrach nieparzystych i sumie cyfr równej jest .
b) Obliczymy, ile jest wszystkich –cyfrowych liczb naturalnych o wszystkich cyfrach nieparzystych i sumie cyfr równej .
Rozwiązanie
Zauważmy, że suma dwóch liczb nieparzystych jest liczbą parzystą, zatem suma cyfr liczby –cyfrowej której wszystkie cyfry są nieparzyste da się zapisać jako suma liczb parzystych – aby to zauważyć wystarczy np. łączyć kolejne cyfry w pary.
Oznacza to, że suma cyfr dowolnej liczby –cyfrowej o wszystkich cyfrach nieparzystych jest parzysta, a więc nie może być równa . Zatem nie ma liczb, które spełniałyby podane w zadaniu warunki.
Obliczymy, ile jest rozwiązań równania
w liczbach całkowitych spełniających warunki .
Rozwiązanie
Podstawmy , , i rozpatrzmy równanie
,
w którym każda z liczb jest nieujemną liczbą całkowitą.
Przekształcamy to równanie do postaci
.
Ponieważ wszystkich rozwiązań powyższego równania w nieujemnych liczbach całkowitych jest ,
więc wszystkich rozwiązań równania
w liczbach całkowitych spełniających warunki jest także .
a) W pudełku znajduje się kartek ponumerowanych od do . Z tego pudełka losujemy razy po jednej kartce, przy czym po każdym losowaniu wrzucamy wylosowaną kartkę z powrotem do pudełka.
Obliczymy, ile jest wszystkich wyników losowania, w których suma wszystkich liczb na wylosowanych z tego pudełka kartkach nie przekracza .
Rozwiązanie
Rozpatrzmy nierówność
,
w której każda z liczb jest nieujemną liczbą całkowitą.
Po przekształceniu tej nierówności do postaci
stwierdzamy, że każda z liczb , gdzie , spełnia warunek .
Zatem każdemu spełniającemu warunki zadania wynikowi ośmiokrotnego losowania kartek z rozpatrywanego pudełka można wzajemnie jednoznacznie przypisać ośmioelementowy ciąg liczb nieujemnych spełniających powyższą nierówność.
Ponadto liczba także jest nieujemna - oznaczmy ją przez .
Wtedy , skąd otrzymujemy równanie
w nieujemnych liczbach całkowitych , gdzie dla .
Ponieważ wszystkich rozwiązań tego równania jest , więc ogółem jest wyników losowania kartek z rozpatrywanego pudełka, w których suma wszystkich liczb na wylosowanych kartkach nie przekracza .
b) Obliczymy, ile jest wszystkich takich wyników ośmiokrotnego rzutu kostką sześcienna do gry, których suma liczb wyrzuconych oczek jest równa co najmniej .
Rozwiązanie
Wynik ośmiokrotnego rzutu kostką sześcienną zapiszemy jako ośmioelementowy ciąg , gdzie to liczba oczek otrzymanych w -tym rzucie, dla .
Zatem warunki zadania są spełnione, gdy
.
Zauważmy, że każdemu , opisującemu liczbę oczek otrzymanych w wybranym spośród rozpatrywanych rzutów kostką, można wzajemnie jednoznacznie przyporządkować inną liczbę oczek takiego rzutu, określoną wzorem .
Na podstawie reguły równolicznościreguły równoliczności stwierdzamy więc, że wyników ośmiokrotnego rzutu kostką sześcienną, dla których spełniony jest warunek
jest tyle samo, co wyników
ośmiokrotnego rzutu kostką sześcienną, dla których spełniony jest warunek
.
Przekształcając powyższą nierówność otrzymujemy
skąd
.
Oznacza to, że wszystkich takich wyników ośmiokrotnego rzutu kostką, których suma liczb wyrzuconych oczek jest równa co najmniej jest tyle samo, co wszystkich takich wyników ośmiokrotnego rzutu kostką, których suma liczb wyrzuconych oczek nie przekracza wartości .
Rozpatrzmy więc nierówność
,
w której każda z liczb jest nieujemną liczbą całkowitą.
Po przekształceniu tej nierówności do postaci
stwierdzamy, że każda z liczb , gdzie , spełnia warunek .
Zatem każdemu wynikowi -krotnego rzutu kostką, w którym suma liczb wyrzuconych oczek nie przekracza wartości można wzajemnie jednoznacznie przypisać –elementowy ciąg liczb nieujemnych spełniających powyższą nierówność.
Jak wiemy z rozwiązania w poprzednim podpunkcie wszystkich rozwiązań tej nierówności w nieujemnych liczbach całkowitych jest . Zatem dokładnie tyle jest też wszystkich takich wyników ośmiokrotnego rzutu kostką, których suma liczb wyrzuconych oczek nie przekracza .
Co za tym idzie, jest wszystkich takich wyników ośmiokrotnego rzutu kostką, których suma liczb wyrzuconych oczek jest równa co najmniej .
c) Obliczymy, ile jest wszystkich ośmiocyfrowych liczb naturalnych, których suma cyfr jest mniejsza od .
Rozwiązanie
Rozpatrzmy nierówność
,
w której każda z liczb jest nieujemną liczbą całkowitą.
Jest ona równoważna nierówności
,
a więc nieujemne liczby całkowite spełniają nierówność
.
Zatem liczba, której kolejnymi cyframi są spełnia warunki zadania.
Ponadto liczba również jest nieujemna – oznaczmy ją przez .
Wtedy , skąd otrzymujemy równanie
w nieujemnych liczbach całkowitych , gdzie dla oraz .
Ponieważ wszystkich rozwiązań tego równania jest , więc ogółem jest liczb naturalnych ośmiocyfrowych, których suma cyfr jest mniejsza od .
Na zakończenie podsumujemy spostrzeżenia poczynione w obu podpunktach powyższego przykładu.
Liczba wszystkich rozwiązań nierówności
w nieujemnych liczbach całkowitych , gdzie oraz to ustalone dodatnie liczby całkowite, jest równa
Dla dowodu rozpatrzmy liczbę .
Z nierówności otrzymujemy , zatem liczba jest nieujemna.
Oznacza to, że rozwiązań danej nierówności w nieujemnych liczbach całkowitych jest dokładnie tyle, ile jest rozwiązań równania
w nieujemnych liczbach całkowitych .
Liczba rozwiązań tak otrzymanego równania jest równa
zatem również tyle jest rozwiązań nierówności
w nieujemnych liczbach całkowitych , gdzie oraz to ustalone dodatnie liczby całkowite.
Koniec dowodu.
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
jeżeli wybór polega na podjęciu jednej z decyzji , przy czym pierwszą z nich można podjąć na sposobów, drugą na sposobów, , – tą na sposobów, to takiego wyboru można dokonać na sposobów
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