W Pałce / Rucińskim na str. 64 jest przykład, który mnie męczy.
Najpierw jest pokazana tożsamość:
\(\displaystyle{ \sum_{k=0}^{l} {n \choose k}{m \choose l-k} = {n + m \choose l}}\)
Mamy zbiór n mężczyzn i m kobiet, wybieramy z nich podzbiór mocy l, czyli możemy równoważnie przejechać po wszystkich zbiorach mocy l, w których mamy k kobiet i l-k mężczyzn.
Dla n=m=l, czyli mamy n mężczyzn i n kobiet, wybieramy z nich podzbiór mocy n, mamy:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k}{n \choose n-k} = \sum_{k=0}^{n} {n \choose k}{n \choose k} = \sum_{k=0}^{n} {n \choose k}^{2} = {2n \choose n}}\)
Teraz mamy tą tożsamość, której nie rozumiem:
\(\displaystyle{ \sum_{k=1}^{n} k^{2} {n \choose k}^{2} = n^{2}{2n-2 \choose n-1}}\)
Panowie lewą stronę interpretują tak, że wybieramy wszystkie zbiory, w których #kobiet = #mężczyzn i wśród kobiet i mężczyzn wybieramy przywódcę.
OK, to rozumiem, ale dlaczego prawa strona = najpierw wybór przywódców, a następnie dobranie odpowiedniej ilości, po równo kobiet/mężczyzn?
\(\displaystyle{ n^{2}}\) to ci przywódcy, \(\displaystyle{ 2n-2}\), bo ze zbioru n kobiet i n mężczyzn zabraliśmy po 1 osobie. Tylko dlaczego tam na dole jest \(\displaystyle{ n-1}\)?
Nie rozumiem, co my tam właściwie wybieramy.
Problem z tożsamością (symbole Newtona)
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Problem z tożsamością (symbole Newtona)
Chcemy jeszcze dobrać po \(\displaystyle{ k}\) osób z \(\displaystyle{ n-1}\) mężczyzn i z \(\displaystyle{ n-1}\) kobiet, gdzie \(\displaystyle{ k=0,1,2,\ldots , n-1}\). Możemy to zrobić na:
\(\displaystyle{ \sum_{k=0}^{n-1} {n-1 \choose k} \cdot {n-1 \choose k}}\)
a to na mocy poprzednich wywodów jest równe właśnie \(\displaystyle{ {2n-2 \choose n-1}}\)
Q.
\(\displaystyle{ \sum_{k=0}^{n-1} {n-1 \choose k} \cdot {n-1 \choose k}}\)
a to na mocy poprzednich wywodów jest równe właśnie \(\displaystyle{ {2n-2 \choose n-1}}\)
Q.