nierozróżnialne kule i rozróżnialne szuflady
: 20 lut 2021, o 19:16
Dzień dobry,
Treść zadania jak i odpowiedź do niego pochodzi z innego forum. Tutaj link do tematu:
[ciach]
Treść zadania: "Rozmieszczono \(\displaystyle{ k}\) nierozróżnialnych kul w \(\displaystyle{ n}\) ponumerowanych szufladach. Obliczyć liczbę możliwych sposobów rozmieszczenia, jeśli każda szuflada może pomieścić nieograniczoną liczbę kul."
Odpowiedź jak i wyjaśnienie do zadania:
Niektóre szuflady mogą być puste. Dorzućmy jeszcze \(\displaystyle{ n}\) kul, żeby w każdej szufladzie była co najmniej jedna kula.
Wyobraźmy sobie coś takiego:
te \(\displaystyle{ k+n}\) kul układamy w jednym szeregu (tak by kule nie stykały się)
między kulami jest \(\displaystyle{ k+n-1}\) przerw
żeby podzielić ten szereg na dwie grupy musimy wstawić w dowolną przerwę jedną przegródkę
żeby podzieli ten szereg na \(\displaystyle{ n}\) grup (\(\displaystyle{ n}\) szuflad) musimy wstawić \(\displaystyle{ n-1}\) przegródek
możliwości wstawienia \(\displaystyle{ n-1}\) przegródek w \(\displaystyle{ k+n-1}\) miejsc to kombinacje, więc
\(\displaystyle{ m={k+n-1\choose n-1}=\frac{(k+n-1)!}{(n-1)!k!}}\)
Część ode mnie:
Załóżmy, że mam \(\displaystyle{ 7}\) szuflad i \(\displaystyle{ 5}\) kul. W takim razie po dołożeniu \(\displaystyle{ 7}\) kul będę miał ich \(\displaystyle{ 12}\), a także będę posiadał \(\displaystyle{ 6}\) przegródek. Podejrzewam, że teraz wkładając odpowiednio przegródki mogę otrzymać w kolejnych szufladkach ilości kul równe np. : \(\displaystyle{ 1,1,2,1,4,2,1}\). Co jednak jeśli będę chciał mieć w kolejnych szufladach ilości kul równe: \(\displaystyle{ 12,0,0,0,0,0,0}\) ? Przegródki mogę wkładać tylko między kule, a więc wkładając przegródkę w dowolnym miejscu zawsze podzielę szereg tak, że w obu częściach będzie więcej niż zero kul. Jedyna opcja to włożenie przegródki między ostatnią kulę, a wolną przestrzeń, ale to jest niedozwolone...
Poza tym jest też problem z tym, że gdybym chciał przykładowo stworzyć \(\displaystyle{ 11,0,0,0,0,0,1}\) to musiałbym wszystkie przegródki włożyć pomiędzy jedenastką, a dwunastą kulę, a chyba nie mogę wstawić więcej niż jednej przegródki w dane miejsce.
Poprosiłbym o wyjaśnienie wyjaśnienia
Pozdrawiam
Treść zadania jak i odpowiedź do niego pochodzi z innego forum. Tutaj link do tematu:
[ciach]
Treść zadania: "Rozmieszczono \(\displaystyle{ k}\) nierozróżnialnych kul w \(\displaystyle{ n}\) ponumerowanych szufladach. Obliczyć liczbę możliwych sposobów rozmieszczenia, jeśli każda szuflada może pomieścić nieograniczoną liczbę kul."
Odpowiedź jak i wyjaśnienie do zadania:
Niektóre szuflady mogą być puste. Dorzućmy jeszcze \(\displaystyle{ n}\) kul, żeby w każdej szufladzie była co najmniej jedna kula.
Wyobraźmy sobie coś takiego:
te \(\displaystyle{ k+n}\) kul układamy w jednym szeregu (tak by kule nie stykały się)
między kulami jest \(\displaystyle{ k+n-1}\) przerw
żeby podzielić ten szereg na dwie grupy musimy wstawić w dowolną przerwę jedną przegródkę
żeby podzieli ten szereg na \(\displaystyle{ n}\) grup (\(\displaystyle{ n}\) szuflad) musimy wstawić \(\displaystyle{ n-1}\) przegródek
możliwości wstawienia \(\displaystyle{ n-1}\) przegródek w \(\displaystyle{ k+n-1}\) miejsc to kombinacje, więc
\(\displaystyle{ m={k+n-1\choose n-1}=\frac{(k+n-1)!}{(n-1)!k!}}\)
Część ode mnie:
Załóżmy, że mam \(\displaystyle{ 7}\) szuflad i \(\displaystyle{ 5}\) kul. W takim razie po dołożeniu \(\displaystyle{ 7}\) kul będę miał ich \(\displaystyle{ 12}\), a także będę posiadał \(\displaystyle{ 6}\) przegródek. Podejrzewam, że teraz wkładając odpowiednio przegródki mogę otrzymać w kolejnych szufladkach ilości kul równe np. : \(\displaystyle{ 1,1,2,1,4,2,1}\). Co jednak jeśli będę chciał mieć w kolejnych szufladach ilości kul równe: \(\displaystyle{ 12,0,0,0,0,0,0}\) ? Przegródki mogę wkładać tylko między kule, a więc wkładając przegródkę w dowolnym miejscu zawsze podzielę szereg tak, że w obu częściach będzie więcej niż zero kul. Jedyna opcja to włożenie przegródki między ostatnią kulę, a wolną przestrzeń, ale to jest niedozwolone...
Poza tym jest też problem z tym, że gdybym chciał przykładowo stworzyć \(\displaystyle{ 11,0,0,0,0,0,1}\) to musiałbym wszystkie przegródki włożyć pomiędzy jedenastką, a dwunastą kulę, a chyba nie mogę wstawić więcej niż jednej przegródki w dane miejsce.
Poprosiłbym o wyjaśnienie wyjaśnienia
Pozdrawiam