Jakiś czas temu rozważałem problem losowania ze zwracaniem dokładnie -elementów z
-elementowego zbioru (dla uściślenia w zbiorze wyjściowym znajduje się dokładnie
różnych elementów). W wyniku takiej operacji, w wylosowanej próbie, mogą pojawić się duplikaty - załóżmy zatem, że otrzymaliśmy
unikalnych rezultatów (oczywiście
). Naturalnie pojawia się pytanie kombinatoryczne.
Ile istnieje sposobów takiego wylosowania (ze zwracaniem) elementów spośród
-elementowego zbioru, że w wyniku otrzymamy dokładnie
unikalnych rezultatów?
Liczba sposobów otrzymania k-unikalnych rezultatów
Liczbę takich sposobów oznaczmy przez .
"Kombinowanie" czas start! Początkowo wyszedłem od losowania różnych elementów, w kolejnym kroku planując losowanie
z wylosowanych wcześniej
. Tego typu podejście prowadziło do bardzo skomplikowanych rozważań, szczegóły pominę. Na rozwiązanie wpadłem po około 2 dniach.
Wariacja bez powtórzeń
Pierwszy krok - liczba sposobów wyboru różnych elementów z
zwracając uwagę na kolejność - jest to wariacja bez powtórzeń
.
Liczba Stirlinga II rodzaju
Drugi krok - zapominamy, że właśnie wylosowaliśmy unikalnych i należy jeszcze dolosować
(choć to prawda). W zamian ustalamy, że mamy już
, w tym
unikalnych. Trick polega na zauważeniu, że mając
różnych elementów w zbiorze
-elementowym, dokonaliśmy jego podziału na
-podzbiorów.
Ile mamy sposobów podziału -elementowego zbioru na
podzbiorów? Jest to właśnie liczba Stirlinga II rodzaju oznaczona
. Zatem finalnie
Dlaczego w kroku pierwszym zwracałem uwagę na kolejność? Chętnych zapraszam do komentowania 🙂
Pozdrowienia,
Mariusz Gromada