Jednakowe przedmioty i pudełka

[FaloZ]

Prosiłbym o sprawdzenie mojego toku myślenia i ewentualne wskazówki. Zadanie brzmi następująco:

a) Na ile sposobów można rozmieścić \(\displaystyle{ 14}\) jednakowych przedmiotów w \(\displaystyle{ 3}\)
pudełkach tak, aby w jednym z pudełek znalazło się co najmniej \(\displaystyle{ 8}\) przedmiotów?
b) Na ile sposobów można rozmieścić \(\displaystyle{ 14}\) jednakowych przedmiotów w \(\displaystyle{ 3}\) pudełkach tak, aby w każdym z pudełek nie znalazło się więcej niż \(\displaystyle{ 7}\) przedmiotów?

Rozw.
a) Otrzymany wynik na ćwiczeniach to \(\displaystyle{ 3 \cdot {8 \choose 6} = 84}\). Domyślam się skąd się to wzięło, ale nie do końca. Moje rozumowanie wyglądało następująco. Wynik ten sam, jednak rozumowanie bardzo na około.

Skoro w jednym z pudełek ma znaleźć się co najmniej \(\displaystyle{ 8}\) przedmiotów, to mamy do czynienia z przypadkami ze zbioru \(\displaystyle{ \{8,...,14\}}\), tzn. załóżmy, że w pierwszym przypadku w pierwszym pudełku mamy \(\displaystyle{ 8}\) przedmiotów, w drugim przypadku, że w pierwszym pudełku jest \(\displaystyle{ 9}\) przedmiotów itd. W pierwszym przypadku, gdy w pierwszym pudełku jest dokładnie \(\displaystyle{ 8}\) przedmiotów, to w którymś z pozostałych dwóch pudełek przedmiotów może być maksymalnie \(\displaystyle{ 6}\). Tzn możemy mieć sytuację np \(\displaystyle{ 8|6|0}\), gdzie \(\displaystyle{ |}\) to "odstęp" między pudełkami. W takim razie, możemy wybrać sześcioelementowe kombinacje ze zbioru dwu elementowego. Jednak należy uwzględnić następujący przypadek, np. \(\displaystyle{ 8|3|3}\). Zatem będą to kombinacje z powtórzeniami. Uzyskuję następujące wyrażenie, dla pierwszego przypadku:

\(\displaystyle{ {2 + 6 - 1 \choose 6} = {7 \choose 6} = 7}\)

Teoretycznie się zgadza, bo na palcach jednej ręki można policzyć przypadki (\(\displaystyle{ 8|6|0 , 8|0|6 , 8|5|1 , 8|1|5 , 8|4|2 , 8|2|4 , 8|3|3}\)). Jednak czy to na pewno będą kombinacje z powtórzeniami? Przecież w tym przypadku kolejność elementów ma znaczenie (\(\displaystyle{ 8|6|0 , 8|0|6}\)), zatem nie szukamy konkretnego podzbioru, tylko ciągu elementów (?). Proszę rozwiać moje wątpliwości i wyjaśnić w którym miejscu głupieje

Dla przypadku drugiego, gdzie w pierwszym pudełku znajduje się \(\displaystyle{ 9}\) przedmiotów, do jednego z pozostałych dwóch pudełek możemy włożyć maksymalnie \(\displaystyle{ 5}\) przedmiotów. Ponieważ mamy nieparzystą liczbę przedmiotów do rozmieszczenia w parzystej ilości pudełkach, to nie zachodzi taka sytuacja, że elementy mogą się powtórzyć. Mamy zatem kombinacje bez powtórzeń (?). Mam problem z zapisaniem tego faktu za pomocą dwumianu Newtona, jednak na palcach jednej ręki jestem w stanie policzyć przypadki, których będzie \(\displaystyle{ 6}\). (\(\displaystyle{ 9|5|0 , 9|0|5 , 9|4|1 , 9|1|4 , 9|2|3 , 9|3|2}\)).

Dla przypadku trzeciego, czyli dla \(\displaystyle{ 10}\) przedmiotów w pierwszym pudełku znowu wracamy do przypadku, gdzie będziemy mieli powtórzenia, ponieważ w jednym z pudełek mogą być maksymalnie \(\displaystyle{ 4}\) przedmioty. Otrzymujemy \(\displaystyle{ n=2}\) oraz \(\displaystyle{ k=4}\), zatem:

\(\displaystyle{ {2 + 4 - 1 \choose 4} = {5 \choose 4} = 5}\)

Co zgadza się z paluszkami (\(\displaystyle{ 10|4|0 , 10|0|4, 10|3|1|, 10|1|3 , 10|2|2}\) ). Widać pewną analogię, ponieważ z każdą liczbą parzystą większą od \(\displaystyle{ 8}\) w pierwszym pudełku liczba przypadków maleje o \(\displaystyle{ 2}\). Podobną analogię można zauważyć dla liczb nieparzystych. Dla czwartego przypadku, gdzie w pierwszym pudełku mamy \(\displaystyle{ 11}\) przedmiotów widać, że będą \(\displaystyle{ 3}\) przypadki.

Koniec końców otrzymuję (oczywiście każdy przypadek sumuję):

\(\displaystyle{ {7 \choose 6} + 6 + {5 \choose 4} + 4 + {3 \choose 2} + 2 + {1 \choose 0} = 7+6+5+4+3+2+1 = 28}\)

Oczywiście to nie koniec, bo przypadek wcześniej wymieniony należy poddać procesowi permutacji (:P), zatem otrzymany wynik \(\displaystyle{ 28}\) należy pomnożyć przez \(\displaystyle{ 3}\). Otrzymujemy wynik \(\displaystyle{ 84}\).

Prosiłbym jednak o wytłumaczenie tego zapisu \(\displaystyle{ 3 \cdot {8 \choose 6} = 84}\), który jak widać zdecydowanie przyspiesza cały proces.

b) W tym przypadku wystarczy policzyć wszystkie możliwości i po prostu odjąć od wyniku z podpunktu a, ponieważ ten przypadek jest zaprzeczeniem przypadku a). Niestety, na ćwiczeniach otrzymaliśmy kompletną moim zdaniem bzdurę, ponieważ wyszło coś takiego: (Chyba, że ja źle przepisałem i nie rozczytałem z tablicy)

Mam zapisane, że wszystkich przypadków jest:

\(\displaystyle{ {11 \choose 14}}\)

Mniejsza o prawdopoodobnie moje błędy, przedstawię mój tok myślenia:

Wydaję mi się, że powinny być tutaj kombinacje z powtórzeniami. Elementy oczywiście mogą się powtarzać, a kolejność ustawienia każdego elementu w pudełku jest nieistotna. Otrzymujemy zatem liczbę \(\displaystyle{ 14}\)-elementowych kombinacji z powtórzeniami zbioru trzyelementowego. Zatem:

\(\displaystyle{ {3+14-1 \choose 14} = {16 \choose 14}}\)

Podsumowując, odpowiedź do tego zadania wyglądałaby następująco:

\(\displaystyle{ {16 \choose 14} - 84 = 120 + 84 = 204}\)

[MrCommando]

Co do podpunktu a), to zadanie sprowadza się do wyznaczenia liczby rozwiązań równania \(\displaystyle{ a+b+c=14}\) w liczbach naturalnych, przy założeniu, że jedna ze zmiennych jest nie mniejsza od \(\displaystyle{ 8}\). Przypuśćmy, że \(\displaystyle{ a\geq 8}\). Dokonajmy podstawienia \(\displaystyle{ d=a-8}\). Wtedy otrzymujemy równanie \(\displaystyle{ b+c+d=6}\). Należy wyznaczyć liczbę jego rozwiązań w liczbach naturalnych. W którymś poście wyjaśniałem Ci jak się to robi, więc teraz skorzystamy z gotowego wzoru. Mamy \(\displaystyle{ {6+3-1 \choose 3-1} = {8 \choose 2}}\). Teraz uwzględnijmy przypadki, gdy \(\displaystyle{ b\geq 8}\) lub \(\displaystyle{ c\geq 8}\). Oczywiście w obydwu przypadkach otrzymamy ten sam wynik, więc ostatecznie mamy \(\displaystyle{ 3\cdot{8 \choose 2}}\).

Podpunkt b).

b) W tym przypadku wystarczy policzyć wszystkie możliwości i po prostu odjąć od wyniku z podpunktu a, ponieważ ten przypadek jest zaprzeczeniem przypadku a).

Nie jest zaprzeczeniem poprzedniego przypadku. W pierwszym przypadku w DOKŁADNIE jednym pudełku było nie więcej niż \(\displaystyle{ 8}\) przedmiotów.

Zagadnienie sprowadza się do wyznaczenia liczby naturalnych rozwiązań równania \(\displaystyle{ x_1+x_2+x_3=14}\), gdzie \(\displaystyle{ x_i\leq 7}\) dla \(\displaystyle{ 1\leq i \leq 3}\). Spróbuj teraz zrobić to sam, pokazałem jak.