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

[Szustarol]

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?

[Premislav]

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]

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]

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.