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
1300
Views Today
Views Today
3

Dodaj komentarz

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