Podaj dowody kombinatoryczne następujących tożsamości.

[Oleszko12]

Nie jestem dobra w wymyślaniu treści do rozwiązania, pierwszą tożsamość zrobiłam chyba dobrze, na drugą nie mam pomysłu.

Podaj dowody kombinatoryczne następujących tożsamości:

1. \(\displaystyle{ {n+m\choose k}=\sum^{n}_{i=0}{n\choose i}{m\choose k-1}}\)


2.\(\displaystyle{ \sum^{n}_{k=0}\left( -1\right)^{k}{n\choose k}=0}\)

1. Mamy k miejsc na studia i wybieramy m-mężczyzn+ n-kobiet = wybieramy \(\displaystyle{ {n\choose i}}\) kobiet oraz \(\displaystyle{ m\choose k-1}\) mężczyzn.

2. ?-- 12 lis 2014, o 23:33 --tzn to \(\displaystyle{ i}\) to jest ile mamy chętnych kobiet

[szw1710]

2. Zauważ, że \(\displaystyle{ 0=(1-1)^n.}\)

[norwimaj]

\(\displaystyle{ {n+m\choose k}=\sum^{n}_{i=0}{n\choose i}{m\choose k-{\red i}}}\)

Literówka była.

wybieramy m-mężczyzn+ n-kobiet

Ja bym tu jeszcze wtrącił jedno słowo: wybieramy spośród \(\displaystyle{ m}\) mężczyzn i \(\displaystyle{ n}\) kobiet.

Do 2. jest też znany dowód z wybieraniem podzbiorów parzystej lub nieparzystej mocy. Jeśli \(\displaystyle{ n}\) jest liczbą nieparzystą, to ten dowód jest prosty, a jeśli nie, to jeszcze trzeba pokombinować (wyróżnić jakiś element zbioru).