Matematyka.pl

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ć.

\(\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:


ale to już nieźle wygląda... bo pierwszy składnik sumy po lewej jest ostatnim składnikiem sumy po prawej i vice versa.

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ć?

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:


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:





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: