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 ≤ k ≤ n). Naturalnie pojawiło się pytanie kombinatoryczne.

Liczba sposobów otrzymania k-unikalnych rezultatów

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?

Liczbę takich sposobów oznaczmy przez B(n,k).

No i się zaczęło "kombinowanie", początkowo wychodziłem od losowania k różnych elementów, w kolejnym kroku planując dodanie losowania n-k z wylosowanych wcześniej k. Tego typu rozumowanie prowadziło do bardzo skomplikowanych rozważań, szczegóły pominę. Na rozwiązanie wpadłem po około 2 dniach.

Pierwszy krok - wariacja bez powtórzeń

Ddość standardowy - 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).

Drugi krok - liczba Stirlinga II

przestajemy myśleć, ż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 wylosowanych elementów, w tym k unikalnych. Zabieg myślowy polega teraz na uzmysłowieniu faktu, że mając k różnych elementów w zbiorze n-elementowym, dokonaliśmy jego podziału na k-podzbiorów. Ile mamy sposobów podziału n-elementowego zbioru na k-podzbiorów? Jest to właśnie liczba Stirlinga II rodzaju oznaczona S2(n,k). Zatem finalnie

B(n,k) = V(n,k)*S2(n,k)

Dlaczego w kroku pierwszym zwracaliśmy uwagę na kolejność? Chętnych zapraszam do komentowania 🙂

Pozdrowienia,

Mariusz Gromada