Dowody twierdzeń - metody kombinatoryczne.

[Molas.]

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

[arek1357]

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

[Molas.]

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ę?

[arek1357]

W pierwszym mi się coś zapis nie podoba tam gdzie jest k-i bo w pewnym momencie ta różnica wyjdzie