Liczba Stirlinga II rodzaju i losowanie ze zwracaniem

Jakiś czas temu rozważałem problem losowania ze zwracaniem dokładnie n-elementów z n-elementowego zbioru (dla uściślenia w zbiorze wyjściowym znajduje się dokładnie n różnych elementów). W wyniku takiej operacji, w wylosowanej próbie, mogą pojawić się duplikaty - załóżmy zatem, że otrzymaliśmy k unikalnych rezultatów (oczywiście 1\leq k\leq n). Naturalnie pojawia się pytanie kombinatoryczne.

Losowanie ze zwracaniem

Ile istnieje sposobów takiego wylosowania (ze zwracaniem) n elementów spośród n-elementowego zbioru, że w wyniku otrzymamy dokładnie k unikalnych rezultatów?

Liczba sposobów otrzymania k-unikalnych rezultatów

Liczbę takich sposobów oznaczmy przez B_n^k.

"Kombinowanie" czas start! Początkowo wyszedłem od losowania k różnych elementów, w kolejnym kroku planując losowanie n-k z wylosowanych wcześniej k. 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 k różnych elementów z n zwracając uwagę na kolejność - jest to wariacja bez powtórzeń V_n^k.

V_n^k=\frac{n!}{(n-k)!}

Liczba Stirlinga II rodzaju

Drugi krok - zapominamy, że właśnie wylosowaliśmy k unikalnych i należy jeszcze dolosować n-k (choć to prawda). W zamian ustalamy, że mamy już n, w tym k unikalnych. Trick polega na zauważeniu, że mając k różnych elementów w zbiorze n-elementowym, dokonaliśmy jego podziału na k-podzbiorów.

Podział zbioru

Ile mamy sposobów podziału n-elementowego zbioru na k podzbiorów? Jest to właśnie liczba Stirlinga II rodzaju oznaczona S_2(n,k). Zatem finalnie

B_n^k = V_n^k\cdot S_2(n,k)

S_2(n,k)=\begin{cases}kS_2(n-1,k)+S_2(n-1,k-1)\quad\text{dla}~k<n\\S_2(n,1)=1\\S_2(n,n)=1\\S_2(n,0)=0\\S_2(0,0)=1\\S_2(n,k)=0\quad\text{dla}~k>n\end{cases}

Dlaczego w kroku pierwszym zwracałem uwagę na kolejność? Chętnych zapraszam do komentowania 🙂

Pozdrowienia,

Mariusz Gromada

Views All Time
Views All Time
580
Views Today
Views Today
2

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *