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]}\)
Tożsamości z liczbami Stirlinga I i II rodzaju
- Premislav
- 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
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.
\(\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.