Podać kombinatoryczne uzasadnienie wzoru
a) \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = 2^n}\)
b)\(\displaystyle{ \sum_{k=0}^{l} {n \choose k} {m \choose i-k}= {n+m \choose l}}\)
c)\(\displaystyle{ \sum_{l=0}^{k} {m \choose l} {n \choose k-l}= {n+m \choose k}}\)
d)\(\displaystyle{ \sum_{i=0}^{n-k} {n-i \choose k} = {n+1 \choose k+1}}\)
Co ja mam z tym zrobic?
Nie wiem nawet od czego zacząć.
Proszę o jakieś wskazówki.
Podać kombinatoryczne uzasadnienie wzoru
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Podać kombinatoryczne uzasadnienie wzoru
Przykład pierwszy - zliczaj podzbiory zbioru o \(\displaystyle{ n}\) elementach, osobno puste, osobno jednoelementowe, osobno dwuelementowe itd. Przykład drugi i trzeci to splot Cauchy'ego - możesz o tym doczytać w internecie.
Przykład czwarty - z \(\displaystyle{ n+1}\) osób musisz wybrać \(\displaystyle{ k+1}\). W tym celu ustalasz, że kapitanem drużyny będzie osoba o numerze \(\displaystyle{ n-i+1}\), zaś resztę wybierzesz spośród osób o numerach niższych.
Przykład czwarty - z \(\displaystyle{ n+1}\) osób musisz wybrać \(\displaystyle{ k+1}\). W tym celu ustalasz, że kapitanem drużyny będzie osoba o numerze \(\displaystyle{ n-i+1}\), zaś resztę wybierzesz spośród osób o numerach niższych.