Udowodnij kombinatorycznie, że dla każdej liczby naturalnej \(\displaystyle{ n \ge 3}\) zachodzi tożsamość:
\(\displaystyle{ \left\{ n \choose k \right\}= \sum_{k=2}^{n-1} {n-1 \choose k}\left\{ k \choose 2\right\}}\),
gdzie \(\displaystyle{ \left\{( )\}}\) oznaczają liczby Stirlinga 2 rodzaju.
Jak to zrobić?
Udowodnij kombinatorycznie
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Udowodnij kombinatorycznie
Masz konflikt oznaczeń, ponieważ indeks oznaczyłeś przez \(\displaystyle{ k}\), popraw proszę, bez tego jest bez sensu.
-
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Udowodnij kombinatorycznie
\(\displaystyle{ \left\{ n \choose 3 \right\}= \sum_{k=2}^{n-1} {n-1 \choose k}\left\{ k \choose 2\right\}}\),
Ok racja, mój błąd. Teraz już jest dobrze. Więc jak to ruszyć?
Ok racja, mój błąd. Teraz już jest dobrze. Więc jak to ruszyć?
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Udowodnij kombinatorycznie
To nie jest chyba bardzo trudne.
Po lewej masz liczbę podziałów zbioru \(\displaystyle{ n}\)-elementowego na trzy parami rozłączne niepuste podzbiory. Przekonajmy się o tym, że po prawej też:
powiedzmy, że wyróżniłeś jakiś element zbioru \(\displaystyle{ n}\)-elementowego. Na \(\displaystyle{ {n-1 \choose k}}\) sposobów wybierasz \(\displaystyle{ k}\) spośród \(\displaystyle{ n-1}\) elementów, które nie trafią do tego samego podzbioru (\(\displaystyle{ k\ge 2}\), gdyż mają być co najmniej dwa niepuste podzbiory, do których ten element nie należy, czyli co najmniej singletony), co Twój wyróżniony element (pozostałe umieszczasz w jednym podzbiorze z tym wyróżnionym elementem), a następnie na \(\displaystyle{ \left\{k\atop 2\right\}}\) sposobów możesz przedstawić ten podzbiór \(\displaystyle{ k}\)-elementowy w postaci sumy dwóch rozłącznych niepustych podzbiorów. Sumując po \(\displaystyle{ k}\) dostajesz liczbę takich podziałów.
Po lewej masz liczbę podziałów zbioru \(\displaystyle{ n}\)-elementowego na trzy parami rozłączne niepuste podzbiory. Przekonajmy się o tym, że po prawej też:
powiedzmy, że wyróżniłeś jakiś element zbioru \(\displaystyle{ n}\)-elementowego. Na \(\displaystyle{ {n-1 \choose k}}\) sposobów wybierasz \(\displaystyle{ k}\) spośród \(\displaystyle{ n-1}\) elementów, które nie trafią do tego samego podzbioru (\(\displaystyle{ k\ge 2}\), gdyż mają być co najmniej dwa niepuste podzbiory, do których ten element nie należy, czyli co najmniej singletony), co Twój wyróżniony element (pozostałe umieszczasz w jednym podzbiorze z tym wyróżnionym elementem), a następnie na \(\displaystyle{ \left\{k\atop 2\right\}}\) sposobów możesz przedstawić ten podzbiór \(\displaystyle{ k}\)-elementowy w postaci sumy dwóch rozłącznych niepustych podzbiorów. Sumując po \(\displaystyle{ k}\) dostajesz liczbę takich podziałów.