Cześć, mam problem z jednym zadaniem z matematyki dyskretnej. Przyznam, że ten typ sprawia mi spore trudności. Prezentuję je poniżej:
\(\sum_{k=0}^{n} \binom{n}{k}\binom{n-k}{m-k}=2^{m}\binom{n}{m}\)
Chyba wiem, z jakich zależności mam skorzystać. Oto one:
\(k\binom{n}{k} =n \binom{n-1}{k-1} oraz \sum_{k=0}^{n} \binom{n}{k} = 2^{n}\)
Niestety nie umiem zastosować ich tak, by doprowadziły mnie do rozwiązania. Czy mogę prosić o pomoc, lub chociaż jakąś wskazówkę? Z góry dziękuję!
Jak udowodnić taką zależność?
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
- panb
- Expert
- Posty: 5122
- Rejestracja: 26 kwie 2010, 22:54
- Lokalizacja: Nowiny Wielkie
- Podziękowania: 19 razy
- Otrzymane podziękowania: 2053 razy
- Płeć:
Re: Jak udowodnić taką zależność?
Spoiler
Takiej udowodnić się nie da.
\(\sum_{k=0}^{m} \binom{n}{k}\binom{n-k}{m-k}=\sum_{k=0}^{m} \left[ \frac{n!}{k!(n-k)!} \cdot \frac{(n-k)!}{(m-k)!(n-m)!}\right]=\sum_{k=0}^{m}\left[ \frac{n!}{m!(n-m)!} \cdot \frac{m!}{k!(m-k)!} \right]=\\=\sum_{k=0}^{m}{n\choose m} \cdot {m\choose k}={n\choose m}\sum_{k=0}^{m}{m\choose k}=2^m{n \choose m}\)
-
- Dopiero zaczynam
- Posty: 28
- Rejestracja: 28 lut 2019, 21:54
- Lokalizacja: Warszawa
- Podziękowania: 19 razy
- Płeć:
Re: Jak udowodnić taką zależność?
Podane miałem z n w zadaniach. Może w takim razie dlatego nie szło. Dzięki wielkie za pomoc, przeczytałem sobie Twoje rozwiązanie i nareszcie zrozumiałem, co powinno się zrobić.