Problem z tożsamością (symbole Newtona)

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
emperor2
Użytkownik
Użytkownik
Posty: 96
Rejestracja: 12 lis 2008, o 15:22
Płeć: Mężczyzna
Podziękował: 36 razy

Problem z tożsamością (symbole Newtona)

Post autor: emperor2 »

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.
Użytkownik
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)

Post autor: »

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.
emperor2
Użytkownik
Użytkownik
Posty: 96
Rejestracja: 12 lis 2008, o 15:22
Płeć: Mężczyzna
Podziękował: 36 razy

Problem z tożsamością (symbole Newtona)

Post autor: emperor2 »

Jasne, już rozumiem. Dziękuję.
ODPOWIEDZ