Przykładowe rozmieszczenie możemy przedstawić symbolicznie
|_oo__|___|_o__|___|___|_o_o_o|
Oznacza ono umieszczenie dwóch kul w pierwszej szufladzie, jedną kulę w trzeciej szufladzie i trzy kule w szóstej szufladzie. Szuflady druga czwarta i piąta są puste.
Powyższy zapis przypomina ciąg binarny złożony z elementów: " |"," o ".
Powstaje pytanie, czy wszystkie elementy tego ciągu są niezbędne do przekazania pełnej informacji o tym rozmieszczeniu ?
Odpowiedź nie, bo pierwsza i ostatnia kreska niczego nie wnoszą - są zbędnymi ozdobnikami.
Odrzucając je i zastępując przegródki szuflad jedynkami, otrzymujemy ciąg binarny
\(\displaystyle{ 00110111000,}\) złożony z sześciu zer i pięciu jedynek.
Ogółniej, przyporządkowując każdemu rozmieszczeniu \(\displaystyle{ k - }\) kul w \(\displaystyle{ n }\) szufladach otrzymujemy ciąg binarny złożony z \(\displaystyle{ k }\) zer i \(\displaystyle{ n-1 }\) jedynek.
Jest to odwzorowanie różnowartościowe i " na".
Ile jest surjekcji ze zbioru \(\displaystyle{ m - }\) elementowego \(\displaystyle{ D }\) na zbiór \(\displaystyle{ R = \{ y_{1}, y_{2},..., y_{n}\} ?}\)
Niech \(\displaystyle{ X = \{ f\in X : D \rightarrow R \} }\) będzie zbiorem wszystkich funkcji ze zboru \(\displaystyle{ D }\) w zbiór \(\displaystyle{ R.}\)
Przyjmijmy \(\displaystyle{ A_{i} = \{ f\in X : y_{i} \neq f(D)\}, \ \ i =1,2,..., n.}\)
Zbiór surjekcji z \(\displaystyle{ D }\) na \(\displaystyle{ R }\) pokrywa się ze zbiorem tych funkcji z \(\displaystyle{ X, }\) które nie należą do żadnego ze zbiorów \(\displaystyle{ A_{1}, A_{2}, ... ,A_{n}. }\)
Mamy \(\displaystyle{ \left| \bigcap_{i\in I} A_{i}\right| = (n -|I|)^{m} }\)
skąd liczba podzbiorów
\(\displaystyle{ S^{(n)}_{k} = {n\choose k}(n-k)^{m} }\)
i ostatecznie
\(\displaystyle{ N(n,k) = \sum_{n=0}^{n}(-1)^{k}S^{(n)}_{k} = \sum_{n=0}^{n} (-1)^{k}(n-k)^{m} = \sum_{k=1}^{n} (-1)^{n-k}{n\choose k}k^{m}.}\)
Licząc ilość rozmieszczeń \(\displaystyle{ 6 }\) nierozróżnialnych kul w \(\displaystyle{ 5 }\) rozróżnialnych szufladach otrzymujemy,
program R
Kod: Zaznacz cały
> S65 = (-1)^4*choose(5,1)*1^6 +(-1)^3*choose(5,2)*2^6+(-1)^2*choose(5,3)*3^6+(-1)^1*choose(5,4)*4^6+(-1)^0*choose(5,5)*5^6
> S65
[1] 1800
Zbigniew Palka Andrzej Ruciński. Wykłady z kombinatoryki. Przeliczenie część 1. WNT Warszawa 1998.
