Liczby Stirlinga

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
zekori
Użytkownik
Użytkownik
Posty: 25
Rejestracja: 26 sty 2020, o 20:28
Płeć: Mężczyzna
wiek: 21
Podziękował: 8 razy

Liczby Stirlinga

Post autor: zekori »

Uzasadnij następującą zależność:
\(\displaystyle{ S\left( n,k\right)= \frac{1}{k!} \sum_{i=0}^{k} \left( -1\right) ^{k-i} {k \choose i} i^{n}}\)
Całkowicie nie wiem jak się za to zabrać.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Liczby Stirlinga

Post autor: Janusz Tracz »

\(\displaystyle{ 1)}\) Interpretacja \(\displaystyle{ k!S(n,k)}\) jest następująca. Ustalmy jakiś podział zbioru \(\displaystyle{ \left[ n\right] }\) na \(\displaystyle{ k}\) niepustych podzbiorów co czynimy na \(\displaystyle{ S(n,k)}\) sposobów (z definicji) każdy taki podzbiór niech przejdzie na jakiś element z \(\displaystyle{ \left[ k\right] }\) co czynimy na \(\displaystyle{ k!}\) sposobów (bijekcje z podziału na \(\displaystyle{ \left[ k\right] }\)). Tym sposobem policzyliśmy suriekcje z \(\displaystyle{ \left[ n\right] }\) w (na) \(\displaystyle{ \left[ k\right] }\).

\(\displaystyle{ 2)}\) Z zasady włącznie i wyłączeń można pokazać, że suriekcji z \(\displaystyle{ \left[ n\right] }\) w \(\displaystyle{ \left[ k\right] }\) jest \(\displaystyle{ \sum_{i=0}^{k}(-1)^i {k \choose i} \left( k-i\right)^n }\)

Pytanie zatem sprowadziło się do zweryfikowania równości:

\(\displaystyle{ \sum_{i=0}^{k} \left( -1\right) ^{k-i} {k \choose i} i^{n} =\sum_{i=0}^{k}(-1)^i {k \choose i} \left( k-i\right)^n }\)

ale to już nieźle wygląda... bo pierwszy składnik sumy po lewej jest ostatnim składnikiem sumy po prawej i vice versa.
zekori
Użytkownik
Użytkownik
Posty: 25
Rejestracja: 26 sty 2020, o 20:28
Płeć: Mężczyzna
wiek: 21
Podziękował: 8 razy

Re: Liczby Stirlinga

Post autor: zekori »

Janusz Tracz pisze: 8 maja 2020, o 18:31

\(\displaystyle{ 2)}\) Z zasady włącznie i wyłączeń można pokazać, że suriekcji z \(\displaystyle{ \left[ n\right] }\) w \(\displaystyle{ \left[ k\right] }\) jest \(\displaystyle{ \sum_{i=0}^{k}(-1)^i {k \choose i} \left( k-i\right)^n }\)
A jak to pokazać?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Liczby Stirlinga

Post autor: Janusz Tracz »

Z zasady włącznie i wyłączeń
Niech \(\displaystyle{ \mathcal{S}}\) to zbiór suriekcji \(\displaystyle{ \mathcal{S}=\left\{ f| f:[n]\xrightarrow{\text{na}} [k]\right\} }\) wtedy zapisać można:

\(\displaystyle{ \left| \mathcal{S}\right| = \left| \left[ k\right]^{\left[ n\right] } \right|-\left| \bigcup_{i=1}^{k} \mathcal{A}_i\right| }\)

gdzie \(\displaystyle{ \mathcal{A}_i= \left\{ f\in \left[ k\right]^{\left[ n\right]} : \text{ jestem funkcją ale zawiodłam ze względy na wartość } i \text{ i jej nie osiągnęłam} \right\} }\) oczywiście \(\displaystyle{ f}\) która nie jest suriekcją ze względy na wartość \(\displaystyle{ i}\) może nie być też suriekcją ze względy na wartość \(\displaystyle{ j}\) (\(\displaystyle{ j \neq i}\)) zatem istnieją takie funkcje nie-suriekcje \(\displaystyle{ f}\) które należą jednocześnie do \(\displaystyle{ \mathcal{A}_i}\) oraz \(\displaystyle{ \mathcal{A}_j}\) stąd konieczność zastosowania zasady włączeń i wyłączeń do zliczenia \(\displaystyle{ \left| \bigcup_{i=1}^{k} \mathcal{A}_i\right| }\). Zatem:

\(\displaystyle{ \left| \mathcal{S}\right| = \left| \left[ k\right]^{\left[ n\right] } \right|- \sum_{i=1}^{k} \left( -1\right)^{i+1} \sum_{1 \le p_1<... < p_i \le k} \left| \mathcal{A}_{p_1} \cap \mathcal{A}_{p_2} \cap ... \mathcal{A}_{p_i}\right| }\)

\(\displaystyle{ \left| \mathcal{S}\right| = k^n+ \sum_{i=1}^{k} \left( -1\right)^{i} \sum_{1 \le p_1<... < p_i \le k} \left| \mathcal{A}_{p_1} \cap \mathcal{A}_{p_2} \cap ... \mathcal{A}_{p_i}\right| }\)

\(\displaystyle{ \left| \mathcal{S}\right| = k^n+ \sum_{i=1}^{k} \left( -1\right)^{i} {k \choose i} \cdot \left|\left( \left[ k\right] \setminus \left\{ p_1,...,p_i\right\}\right) ^{\left[ n\right] }\right| }\)

\(\displaystyle{ \left| \mathcal{S}\right| = k^n+ \sum_{i=1}^{k} \left( -1\right)^{i} {k \choose i} \cdot \left( k-i\right)^n }\)

Zauważaj, że \(\displaystyle{ k^n}\) pasuje do wzoru \(\displaystyle{ \left( -1\right)^{i} {k \choose i} \cdot \left( k-i\right)^n}\) przy \(\displaystyle{ i=0}\) mamy ostatecznie:

\(\displaystyle{ \left| \mathcal{S}\right| = \sum_{i=0}^{k} \left( -1\right)^{i} {k \choose i} \cdot \left( k-i\right)^n }\)
ODPOWIEDZ