Na ile sposobów mogę rozmieścić 7 więźniów w 7 celach

[s147698]

Na ile sposobów mogę rozmieścić 7 więźniów w 7 celach jeżeli:
a)Co najmniej jedna cela powinna zostać pusta
b)Dokładnie jedna cela powinna zostać pusta

[Premislav]

a) wybieramy na siedem sposobów celę która ma być pusta i dalej rozdzielamy więźniów jakkolwiek do sześciu pozostałych, czyli mamy \(\displaystyle{ 7\cdot 6^7}\) sposobów rozmieszczenia (dla każdego z siedmiu więźniów mamy do wyboru sześć cel).

Co do b): czy możesz korzystać z liczb Stirlinga II rodzaju? Bo nie chce mi się tego liczyć "na piechotę".

[Benny01]

a) wybieramy na siedem sposobów celę która ma być pusta i dalej rozdzielamy więźniów jakkolwiek do sześciu pozostałych, czyli mamy \(\displaystyle{ 7\cdot 6^7}\) sposobów rozmieszczenia (dla każdego z siedmiu więźniów mamy do wyboru sześć cel).

Czy aby na pewno? Co jeśli 2 będą puste?

[Premislav]

Przecież w podpunkcie a) co najmniej jedna cela ma zostać pusta, więc nie boli nas to, że np. dwie zostaną puste. Chyba że nie zrozumiałem Twojego zastrzeżenia.

[Benny01]

Dobra ja coś sobie w głowie wymyśliłem, źle przeczytałem, sorry

[s147698]

a) wybieramy na siedem sposobów celę która ma być pusta i dalej rozdzielamy więźniów jakkolwiek do sześciu pozostałych, czyli mamy \(\displaystyle{ 7\cdot 6^7}\) sposobów rozmieszczenia (dla każdego z siedmiu więźniów mamy do wyboru sześć cel).

Co do b): czy możesz korzystać z liczb Stirlinga II rodzaju? Bo nie chce mi się tego liczyć "na piechotę".

Na pierwszy rzut oka twoje rozwiązanie wydaje się sensowne.
Jednak gdy rozwiązuję je innym sposobem wychodzi inny wynik(może mój sposób jest zły).
Wygląda następująco:
1) Obliczam ilość wszystkich możliwości umieszczenia \(\displaystyle{ 7}\) więźniów w \(\displaystyle{ 7}\) celach: \(\displaystyle{ 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7=823543}\)
2) Obliczam liczbę możliwości gdzie każda cela jest zajęta: \(\displaystyle{ 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1= 5040}\)
3) Odejmuję od liczby wszystkich możliwości liczbę możliwości gdzie każda cela jest zajęta \(\displaystyle{ 823543-5040=818503}\)

Zostają możliwości gdzie co najmniej jedna cela jest pusta.

Czy dobrze rozumuję? Jeżeli nie to gdzie popełniłem błąd?

[Premislav]

Twój sposób jest poprawny, a mój nie, przepraszam (jak ja nienawidzę tej szkolnej kombinatoryki, nawet chyba w szkole dostałem z tego 4+ ze sprawdzianu). Policzyłem wielokrotnie te same ustawienia.

[s147698]

Twój sposób jest poprawny, a mój nie, przepraszam (jak ja nienawidzę tej szkolnej kombinatoryki, nawet chyba w szkole dostałem z tego 4+ ze sprawdzianu). Policzyłem wielokrotnie te same ustawienia.

Dzięki za potwierdzenie. Jak w takim razie rozwiązać podpunkt b)?

[Premislav]

Takie niepoprawne rozumowanie, jak moje poprzednie do podpunktu a) chyba nawet jest przedstawione w książce Jakubowskiego i Sztencla Wstęp do rachunku prawdopodobieństwa (drugi rozdział zawiera też trochę elementarnej kombinatoryki), w paragrafie "najczęstsze błędy".

Co do podpunktu b).
Można użyć wspomnianych liczb Stirlinga II rodzaju, ale to niejawna postać i nie wiem, czy zostałaby zaakceptowana. Na \(\displaystyle{ 7}\) sposobów wybieramy pustą celę, dzielimy więźniów na sześć niepustych podgrup (podzbiorów) na \(\displaystyle{ \left\{7\atop 6\right\}}\) sposobów i uwzględniamy jeszcze to, że cele są rozróżnialne, więc mnożymy przez \(\displaystyle{ 6!}\). Przy takim podejściu uzyksujemy wynik do b) w postaci \(\displaystyle{ 7! \cdot \left\{7\atop 6\right\}}\)
Akurat tu to nie jest problem, bo \(\displaystyle{ \left\{7\atop 6\right\}={7\choose 2}}\), ogólnie \(\displaystyle{ \left\{n \atop n-1\right\}={n \choose 2}}\).

Choć może da się i bez liczb Stirlinga II rodzaju:
jak poprzednio, na \(\displaystyle{ 7}\) sposobów wybieramy celę, która ma być pusta. Następnie rozmieszczamy siedmiu więźniów w sześciu celach tak, aby żadna z tych sześciu nie była pusta. Na \(\displaystyle{ {7 \choose 2}}\) sposobów wybieramy dwóch spośród siedmiu więźniów, którzy będą siedzieć w tej samej celi (skoro wszystkich sześć pozostałych cel należy zapełnić, to będzie tylko jedna taka para). Niejako sklejamy wówczas tę parę i traktujemy dalej jak jednego multiwięźnia (fajny neologizm), do \(\displaystyle{ 6}\) miejsc może trafić nasz "multiwięzień", a pozostałych pięciu rozmieszczamy w pozostałych pięciu celach na \(\displaystyle{ 5!}\) sposobów. To daje nam taką odpowiedź do podpunktu b): \(\displaystyle{ 7\cdot {7\choose 2}\cdot 6!=7!{7\choose 2}=7!\cdot 21}\)
Czy jest to zrozumiałe?

[s147698]

Sposób bez liczb stringa bardzo dobrze objaśniony. Dzięki wielkie za pomoc ))