skąd bierze się wzór

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
JakubCh
Użytkownik
Użytkownik
Posty: 613
Rejestracja: 18 gru 2011, o 11:41
Płeć: Mężczyzna
Lokalizacja: Rzeszów/Kraków
Podziękował: 265 razy
Pomógł: 5 razy

skąd bierze się wzór

Post autor: JakubCh »

Mógłby mi ktoś wyjaśnić, skąd bierze się ten wzór:

\(\displaystyle{ \sum_{k \in Z} {n \choose k} {m \choose p-k} = {n+m \choose p}}\)-- 29 sty 2013, o 15:52 --\(\displaystyle{ n,m \in N}\) i \(\displaystyle{ p \in Z}\)
Awatar użytkownika
zidan3
Użytkownik
Użytkownik
Posty: 694
Rejestracja: 9 kwie 2011, o 10:05
Płeć: Mężczyzna
Lokalizacja: Lbn
Podziękował: 9 razy
Pomógł: 112 razy

skąd bierze się wzór

Post autor: zidan3 »

Wiemy, że \(\displaystyle{ (1+x)^n=\sum_{k=0}^{n} {n \choose k} x^k}\). Zatem oczywistym jest
\(\displaystyle{ (1+x)^{n+m}=(1+x)^n \cdot (1+x)^m=\left( \sum_{k=0}^{n} {n \choose k} x^k\right) \left( \sum_{k=0}^{m} {m \choose k} x^k\right)}\)
Więc mamy równość wielomianów. Porównajmy współczynniki przy \(\displaystyle{ x^k}\) po obu stronach, stąd dostajemy
\(\displaystyle{ {n+m \choose k} x^k=\sum_{i=0}^{k} {m \choose i} x^i \cdot {n \choose k-i}x^{k-i}=\sum_{i=0}^{k} {m \choose i} {n \choose k-i} x^k}\) dzieląc obustronnie przez \(\displaystyle{ x^k}\) otrzymujemy tezę
\(\displaystyle{ \sum_{i=0}^{k} {m \choose i} {n \choose k-i}= {n+m \choose k}}\)

Można również udowodnić to indukcyjnie.
JakubCh
Użytkownik
Użytkownik
Posty: 613
Rejestracja: 18 gru 2011, o 11:41
Płeć: Mężczyzna
Lokalizacja: Rzeszów/Kraków
Podziękował: 265 razy
Pomógł: 5 razy

skąd bierze się wzór

Post autor: JakubCh »

dzięki
ODPOWIEDZ