Tożsamość z dwumianem newtona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Gromo
Użytkownik
Użytkownik
Posty: 74
Rejestracja: 20 kwie 2010, o 18:52
Płeć: Mężczyzna
Lokalizacja: P-ków Tryb.
Pomógł: 8 razy

Tożsamość z dwumianem newtona

Post autor: Gromo »

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.
adambak
Użytkownik
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

Post autor: adambak »

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.
norwimaj
Użytkownik
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

Post autor: norwimaj »

adambak pisze:Interpretacja musiałaby być bardzo wyszukana chyba..
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.

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.
ODPOWIEDZ