1. \(\displaystyle{ \sum_{i=0}^{n}{n\choose i}{n-i\choose k-i}=2^{k}{n\choose k}}\)
2. \(\displaystyle{ \sum_{k=0}^{n}{n\choose k}^{2}={2n\choose n}}\)
Mam udowodnić te twierdzenia metodami kombinatorycznymi, ale nie wiem za bardzo jak się za nie zabrać...
Dowody twierdzeń - metody kombinatoryczne.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Dowody twierdzeń - metody kombinatoryczne.
w zadaniu 2 gim jest tak że korzystasz z takiej tożsamości:
\(\displaystyle{ \sum_{k=0}^{l} {n\choose k}{m \choose l-k}={n+m \choose l}}\)
łatwo to udowodnić bo jak masz zbiór n+m elementowy i dzielisz go na dwa podzbiory
po m i n elementow np n białych kul i m czarnych
i wybierasz z niego l kul , jest to równe sumie iloczynow od k=0,1,2,3,...min{k,l}
l elementowych podzbiorów o k elementach czarnych i l-k białych
\(\displaystyle{ {n\choose k}{m \choose l-k}}\)
obkładając to sumą masz wszystkie możliwości sumując po k
a prawa strona to po prostu ilośc kombinacji (wyboru) zbiory l elementowego ze zbioru n+m elementtowego
czyli ok , jeśli weźmiesz teraz n=m=l
otrzymasz:
\(\displaystyle{ \sum_{k=0}^{n} {n\choose k}{n \choose n-k}={2n \choose n}}\)
ale oczywiście:
\(\displaystyle{ {n\choose k} = {n \choose n-k}}\)
i masz całośc
ale z pierwszym jest coś lipnie zapisane coś mi sie nie zgadza
\(\displaystyle{ \sum_{k=0}^{l} {n\choose k}{m \choose l-k}={n+m \choose l}}\)
łatwo to udowodnić bo jak masz zbiór n+m elementowy i dzielisz go na dwa podzbiory
po m i n elementow np n białych kul i m czarnych
i wybierasz z niego l kul , jest to równe sumie iloczynow od k=0,1,2,3,...min{k,l}
l elementowych podzbiorów o k elementach czarnych i l-k białych
\(\displaystyle{ {n\choose k}{m \choose l-k}}\)
obkładając to sumą masz wszystkie możliwości sumując po k
a prawa strona to po prostu ilośc kombinacji (wyboru) zbiory l elementowego ze zbioru n+m elementtowego
czyli ok , jeśli weźmiesz teraz n=m=l
otrzymasz:
\(\displaystyle{ \sum_{k=0}^{n} {n\choose k}{n \choose n-k}={2n \choose n}}\)
ale oczywiście:
\(\displaystyle{ {n\choose k} = {n \choose n-k}}\)
i masz całośc
ale z pierwszym jest coś lipnie zapisane coś mi sie nie zgadza
-
- Użytkownik
- Posty: 61
- Rejestracja: 14 paź 2007, o 15:00
- Płeć: Mężczyzna
- Lokalizacja: Dom wariatów.
Dowody twierdzeń - metody kombinatoryczne.
W pierwszym powinna byc jeszcze podpowiedź, by rozważyć kolorowanie k spośród n obiektów, mając do dyspozycji dwa kolory - nie wiem, czy to w czymś pomoże.
A odnośnie zadania drugiego to tak się zastanawiałem i doszedłem do wniosku, że można to chyba też zrobić tak: lewa strona - biorę z każdej grupy dokładnie k osón, prawa strona - łączę poprzednie grupy i wybieram z nich n osób, z czego wśród tych osób k będzie pochodzić z pierwszej grupy, a (n-k) będą to osoby, których nie wybraliśmy z drugiej grupy...? Dobrze myślę?
A odnośnie zadania drugiego to tak się zastanawiałem i doszedłem do wniosku, że można to chyba też zrobić tak: lewa strona - biorę z każdej grupy dokładnie k osón, prawa strona - łączę poprzednie grupy i wybieram z nich n osób, z czego wśród tych osób k będzie pochodzić z pierwszej grupy, a (n-k) będą to osoby, których nie wybraliśmy z drugiej grupy...? Dobrze myślę?