Udowodnij kombinatorycznie

[max123321]

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

[Premislav]

Masz konflikt oznaczeń, ponieważ indeks oznaczyłeś przez \(\displaystyle{ k}\), popraw proszę, bez tego jest bez sensu.

[max123321]

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

[Premislav]

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.