Rozmieszczenie w pudełkach, przy założeniu, że żadne nie jest puste.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Szustarol
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 10 mar 2018, o 18:11
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 10 razy

Rozmieszczenie w pudełkach, przy założeniu, że żadne nie jest puste.

Post autor: Szustarol » 5 paź 2019, o 20:01

Witam.
Treść zadania brzmi tak:
Na ile sposobów można rozmieścić \(\displaystyle{ k}\) rozróżnialnych kul w \(\displaystyle{ n}\) oznaczonych pudełkach przy założeniu, że żadne pudełko nie jest puste?

Były juz takie zadania na internecie, ale bez generalizacji na \(\displaystyle{ k}\) i \(\displaystyle{ n}\), oraz zazwyczaj posty są bez odpowiedzi.
Moje podejście do tematu:
Najpierw wybieramy \(\displaystyle{ n}\) kul, po jednej do każdego pudełka, aby żadne nie było puste:

\(\displaystyle{ k \choose n }\)

Kule w pudełkach mozemy zamieniać miejscami na \(\displaystyle{ n!}\) sposobów.

Po tym kroku w każdym pudełku znajduje się jedna kula, a do dystrybucji pozostało jeszcze \(\displaystyle{ k-n}\) kul.
Każdą z \(\displaystyle{ k-n}\) kul możemy włożyć do dowolnego pojemnika - na \(\displaystyle{ n}\) sposobów:

\(\displaystyle{ (k-n)^{n} }\)

Koniec końców, liczba takich kombinacji wynosi:

\(\displaystyle{ {k \choose n} \cdot n! \cdot (k-n)^{n}}\)

Czy jest to poprawna odpowiedź? Jeśli nie, gdzie jest bląd w moim rozumowaniu?
Ostatnio zmieniony 5 paź 2019, o 20:17 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa także do pojedynczych symboli.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 14480
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 88 razy
Pomógł: 4764 razy

Re: Rozmieszczenie w pudełkach, przy założeniu, że żadne nie jest puste.

Post autor: Premislav » 5 paź 2019, o 20:34

Liczysz wielokrotnie pewne układy, np. moja lewa kula (if you know what I mean) została wybrana do pierwszego pudełka, a prawa dorzucona do pierwszego pudełka w procesie dokładania pozostałych \(\displaystyle{ k-n}\) albo na odwrót – te dwa przypadki zliczyłeś oddzielnie.
To, co jest Ci potrzebne, to liczba surjekcji ze zbioru \(\displaystyle{ k}\)-elementowego na zbiór \(\displaystyle{ n}\)-elementowy (\(\displaystyle{ k\ge n}\) oczywiście) i jest na to gotowa formuła (korzystająca z liczb Stirlinga II rodzaju), która tak się przedstawia:
\(\displaystyle{ \left\{ k \atop n\right\} n!}\).
Interpretacja tego jest prosta: na \(\displaystyle{ \left\{k \atop n\right\}}\) sposobów dzielimy zbiór \(\displaystyle{ k}\) kul na \(\displaystyle{ n}\) niepustych, parami rozłącznych podzbiorów, po czym na \(\displaystyle{ n!}\) sposobów przydzielamy te niepuste zbiory kul do odpowiednich pudełek (bo pudełek jest \(\displaystyle{ n}\)).

Szustarol
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 10 mar 2018, o 18:11
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 10 razy

Re: Rozmieszczenie w pudełkach, przy założeniu, że żadne nie jest puste.

Post autor: Szustarol » 5 paź 2019, o 21:11

Dziękuję za podzielenie się tym wzorem. Nie był on dla mnie znany, ale czy da się poprowadzić moje rozumowanie tak, aby doprowadzić do prawidłowego wyniku za pomocą podstawowych wzorów kombinatorycznych? Interesuje mnie tok rozumowania w tego typu problemie, a niekoniecznie gotowy wzór.
Oczywiście przykład zrozumiałem, wiem już na czym polega problem, ale nie za bardzo wiem jak go rozwiązać.

Edit.
Jeśli każda z kul jest wliczana dwa razy, a mamy k kul, to czy rozwiązaniem nie jest podzielenie mojego wzoru przez \(\displaystyle{ 2^k}\)?

janusz47
Użytkownik
Użytkownik
Posty: 5464
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 8 razy
Pomógł: 1195 razy

Re: Rozmieszczenie w pudełkach, przy założeniu, że żadne nie jest puste.

Post autor: janusz47 » 5 paź 2019, o 22:20

W odpowiedzi Pana Premislava występują dwa pojęcia, między którymi występuje ścisły związek:

- liczbą bijekcji \(\displaystyle{ s_{kn} }\) zbioru \(\displaystyle{ k }\) elementowego na zbiór \(\displaystyle{ n }\) elementowy;

- liczbą Stirlinga drugiego rodzaju \(\displaystyle{ S_{kn} }\),

bez znajomości tych pojęć i konstrukcji kombinatorycznej związku między nimi - trudno jest zrozumieć doświadczenie, polegające na losowym podziale zbioru \(\displaystyle{ k }\) elementowego na \(\displaystyle{ n, \ \ k\geq n }\) bloków.

Zapoznaj się na przykład

z rozdziałem pierwszym książki Witolda Lipskiego i Wiktora Marka Analiza Kombinatoryczna PWN Warszawa 1986,
lub
Kombinatoryką dla Programistów PWN Warszawa 1982, Witolda Lipskiego.
czy
Wykładami z Kombinatoryki prof. Wojciecha Guzickiego z UW.

Dodano po 49 minutach 40 sekundach:
Z ciekawymi, pełnymi zastosowań wykładami dr Chlebusa z UW.

ODPOWIEDZ