Czy da radę udowodnić poprzez indukcję, albo kombinatorycznie następujący fakt:
\(\displaystyle{ \begin{Bmatrix} n+1 \\ m+1 \end{Bmatrix} = \sum_{k=0}^{n} {n \choose k} \begin{Bmatrix} k \\ m \end{Bmatrix}}\)
\(\displaystyle{ n, m \ge 0}\)
Za wszelkie wskazówki z góry dziękuję.
dowód tożsamości kombinatorycznej - liczby Stirlinga
dowód tożsamości kombinatorycznej - liczby Stirlinga
Ostatnio zmieniony 9 gru 2012, o 23:12 przez Qń, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
dowód tożsamości kombinatorycznej - liczby Stirlinga
Z lewej strony mamy oczywiście liczbę podziałów zbioru \(\displaystyle{ n+1}\) na \(\displaystyle{ m+1}\) części.
Możemy je zliczać także w inny sposób: zacznijmy od ustalenia jednego elementu. Następnie wybierzmy \(\displaystyle{ k}\) spośród pozostałych \(\displaystyle{ n}\) elementów, które nie będą z nim w jednym zbiorze (oczywiście \(\displaystyle{ k}\) może się zmieniać od \(\displaystyle{ 0}\) - gdy wszystko jest razem z ustalonym elementem, do \(\displaystyle{ n}\) - gdy ustalony element jest w podzbiorze jednoelementowym). Mamy więc już jeden podzbiór \(\displaystyle{ 1+n-k}\)-elementowy. Pozostaje więc pozostałych \(\displaystyle{ k}\) elementów umieścić w \(\displaystyle{ m}\) podzbiorach, a to oczywiście można zrobić na \(\displaystyle{ \begin{Bmatrix} k \\ m \end{Bmatrix}}\) sposobów.
Q.
Możemy je zliczać także w inny sposób: zacznijmy od ustalenia jednego elementu. Następnie wybierzmy \(\displaystyle{ k}\) spośród pozostałych \(\displaystyle{ n}\) elementów, które nie będą z nim w jednym zbiorze (oczywiście \(\displaystyle{ k}\) może się zmieniać od \(\displaystyle{ 0}\) - gdy wszystko jest razem z ustalonym elementem, do \(\displaystyle{ n}\) - gdy ustalony element jest w podzbiorze jednoelementowym). Mamy więc już jeden podzbiór \(\displaystyle{ 1+n-k}\)-elementowy. Pozostaje więc pozostałych \(\displaystyle{ k}\) elementów umieścić w \(\displaystyle{ m}\) podzbiorach, a to oczywiście można zrobić na \(\displaystyle{ \begin{Bmatrix} k \\ m \end{Bmatrix}}\) sposobów.
Q.