Tożsamości z liczbami Stirlinga I i II rodzaju

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Gofer33
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 26 sty 2017, o 21:49
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 5 razy

Tożsamości z liczbami Stirlinga I i II rodzaju

Post autor: Gofer33 »

Cześć, potrzebuję pomocy, żeby dowieść kilka tożsamości z liczbami Stirlinga pierwszego i drugiego rodzaju. Zrobiłem kilka przykładów lecz kilka jest takich, że w pewnym momencie się zatrzymuje i nie wiem co dalej ruszyc. Tutaj kilka z nich:

1. \(\displaystyle{ x^{\overline{n}} = \sum_{k=0}^{n} \left[ \begin{matrix} n \\ k\end{matrix} \right] x^{k}}\)

2. \(\displaystyle{ \sum_{k=0}^{n} \left\{ {k}\atop{2}\right\} \left( {n}\atop{k}\right) = \left\{ {n+1}\atop{3}\right\}}\)

3. \(\displaystyle{ \sum_{k=0}^{n} k \left[\begin{matrix} n+1 \\ k\end{matrix} \right] =\left[\begin{matrix} n+2 \\ 2\end{matrix} \right]}\)

4. \(\displaystyle{ \sum_{k=m}^{n} \left\{ {k}\atop{m}\right\} \left( {n}\atop{k}\right) = \left\{ {n+1}\atop{m+1}\right\}}\)

5. \(\displaystyle{ \sum_{k=0}^{n} \left[\begin{matrix} n \\ k\end{matrix} \right] 2^{k} =(n+1)!}\)

6. \(\displaystyle{ \sum_{k=1}^{n}k\left[\begin{matrix} n \\ k\end{matrix} \right]=\left[\begin{matrix} n+1 \\ 2\end{matrix} \right]}\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Tożsamości z liczbami Stirlinga I i II rodzaju

Post autor: Premislav »

Zauważ, że zadanie 2. to tak naprawdę zakamuflowany szczególny przypadek zadania 4. gdzie
\(\displaystyle{ m=2}\), a to dlatego, że
\(\displaystyle{ \left\{ {0}\atop{2}\right\}= \left\{ {1}\atop{2}\right\}=0}\), więc tak naprawdę suma w 2. równie dobrze mogłaby się zaczynać od \(\displaystyle{ k=2}\)

Interpretacja kombinatoryczna do zadania 4.
Chcemy podzielić zbiór o \(\displaystyle{ n+1}\) elementach na \(\displaystyle{ m+1}\) niepustych podzbiorów.
Z jednej strony możemy to uczynić na \(\displaystyle{ \left\{ {n+1}\atop{m+1}\right\}}\) sposobów (definicja liczb Stirlinga II rodzaju). Z drugiej strony możemy na to spojrzeć tak:
wyróżniamy pewien element w tym zbiorze \(\displaystyle{ n+1}\)-elementowym, pozostałych elementów jest oczywiście \(\displaystyle{ n}\). Wybieramy na \(\displaystyle{ {n \choose k}}\) sposobów \(\displaystyle{ k}\) elementów (spośród tych \(\displaystyle{ n}\) pozostałych), gdzie \(\displaystyle{ k\ge m}\) i dzielimy powstały podzbiór k-elementowy na \(\displaystyle{ m}\) niepustych podzbiorów na \(\displaystyle{ \left\{ {k}\atop{m}\right\}}\) sposobów. Pozostałe \(\displaystyle{ n-k}\) elementów ląduje w tym samym zbiorze, co nasz wyróżniony element - łącznie otrzymujemy w ten sposób dowolny podział na \(\displaystyle{ m+1}\) niepustych podzbiorów.
ODPOWIEDZ