Witam, mógłby ktoś podrzucić ideę na tę tożsamość:
\(\displaystyle{ \sum_{j=0}^{k} {n \choose j} = \sum_{j=0}^{k} {n-j-1 \choose k-j} \cdot 2^{j}}\), \(\displaystyle{ 0 \le k \le n - 1}\)
Siedzę juz troche nad tym i nie moge wymyslic. Najlepiej by bylo gdyby ktos podrzucil pomysl na interpretacje kombinatoryczna.
Tożsamość z dwumianem newtona
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
Tożsamość z dwumianem newtona
Interpretacja musiałaby być bardzo wyszukana chyba.. Indukcja po \(\displaystyle{ n}\) i wychodzi bardzo ładnie - założenie jest takie, że dla danego \(\displaystyle{ n}\) i dowolnego (spełniającego założenia) \(\displaystyle{ k}\) równość zachodzi.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Tożsamość z dwumianem newtona
Są takie metody z przesuwaniem i rozmnażaniem pionków na szachownicy w kształcie trójkąta Pascala. Może nie różni się to bardzo od indukcji, ale chyba jest uznawane jako interpretacja kombinatoryczna.adambak pisze:Interpretacja musiałaby być bardzo wyszukana chyba..
Wymyśliłem też jakąś uczciwszą interpretację, ale jest trochę udziwniona i okrutna. Załóżmy że mam \(\displaystyle{ n}\) dzieci. Co mogę zrobić z \(\displaystyle{ k}\) cukierkami, jeśli \(\displaystyle{ k<n}\)? Oczywiście mogę ich zjeść tyle, żeby się całkiem zasłodzić, a jeśli zostanie jeszcze \(\displaystyle{ j}\), to rozdam je dzieciom, każdemu po co najwyżej jednym. Zbiór obdarowanych dzieci mogę wybrać na \(\displaystyle{ \binom nj}\) sposobów.
Ale mogę też zrobić inaczej. Przywołuję po kolei dzieci. Jeśli przywołane dziecko odgadnie zagadkę, to dostaje cukierka (gdy już nie mam cukierków to jako zagadkę daję dowód jakiegoś otwartego problemu). Niech \(\displaystyle{ j}\) będzie najmniejszą taką liczbą, że gdy zostało mi jeszcze \(\displaystyle{ j}\) dzieci, to wiedziałem że mogę już zadawać same łatwe zagadki. Przy ustalonym \(\displaystyle{ j}\) liczba możliwych zbiorów obdarowanych dzieci jest równa \(\displaystyle{ \binom{n-j-1}{k-j} \cdot 2^{j}}\), bo pierwszym \(\displaystyle{ n-j-1}\) dzieciom dałem \(\displaystyle{ k-j}\) cukierków, dziecko \(\displaystyle{ n-j}\) nie dostało cukierka, a każde następne mogło dostać albo nie.