Witam, mam pewne równanie, które muszę udowodnić kombinatorycznie, jednak nie mam pojęcia jak się do tego zabrać, prosiłbym o jakąś wskazówkę.
\(\displaystyle{ \sum_{k=1}^{n} k^{2} {n\choose k}^2= n^2 {2n-2\choose n-1}}\)
Dowód kombinatoryczny
-
Mortify
- Użytkownik
- Posty: 768
- Rejestracja: 22 lis 2007, o 22:39
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / MIMUW
- Podziękował: 27 razy
- Pomógł: 164 razy
Dowód kombinatoryczny
Mamy \(\displaystyle{ n}\) kobiet i \(\displaystyle{ n}\) mężczyzn. Będziemy się starali wybrać lidera męskiego i żeńskiego oraz podzielić pozostałe osoby na dwie grupy.
Możemy zrobić to na dwa sposoby. Pierwszy (prawa strona równania) to taki, że wybieramy jednego mężczyznę i jedną kobietę \(\displaystyle{ n \cdot n}\) sposobów. Pozostałe osoby mieszamy ze sobą \(\displaystyle{ 2n-2}\) osoby i wybieramy grupę \(\displaystyle{ n-1}\) osobową, a pozostałe tworzą drugą grupę. Stąd mamy \(\displaystyle{ n^2 {2n-2\choose n-1}}\)
Z drugiej jednak strony, możemy najpierw wybierać \(\displaystyle{ k}\) mężczyzn (\(\displaystyle{ {n\choose k}}\) sposobów) i spośród nich lidera (\(\displaystyle{ k}\) sposobów), pozostałe \(\displaystyle{ k-1}\) mężczyzn wrzucamy do pierwszej grupy \(\displaystyle{ n-1}\) osobowej, a pozostałe \(\displaystyle{ n-k}\) mężczyzn wrzucamy do drugiej grupy. Następnie wybieramy \(\displaystyle{ n-k}\) kobiet spośród \(\displaystyle{ n}\) (\(\displaystyle{ {n\choose k}}\) sposobów) i wrzucamy do pierwszej grupy (razem jest \(\displaystyle{ n-k+k-1 = n-1}\) osób) a z pozostałych \(\displaystyle{ k}\) kobiet losujemy liderkę (\(\displaystyle{ k}\) sposobów). Pozostało jeszcze \(\displaystyle{ k-1}\) kobiet, które wrzucamy do drugiej grupy. W ten sposób otrzymaliśmy lewą stronę.
Oba losowania są równoważne, zatem to pokazuje równość.
Możemy zrobić to na dwa sposoby. Pierwszy (prawa strona równania) to taki, że wybieramy jednego mężczyznę i jedną kobietę \(\displaystyle{ n \cdot n}\) sposobów. Pozostałe osoby mieszamy ze sobą \(\displaystyle{ 2n-2}\) osoby i wybieramy grupę \(\displaystyle{ n-1}\) osobową, a pozostałe tworzą drugą grupę. Stąd mamy \(\displaystyle{ n^2 {2n-2\choose n-1}}\)
Z drugiej jednak strony, możemy najpierw wybierać \(\displaystyle{ k}\) mężczyzn (\(\displaystyle{ {n\choose k}}\) sposobów) i spośród nich lidera (\(\displaystyle{ k}\) sposobów), pozostałe \(\displaystyle{ k-1}\) mężczyzn wrzucamy do pierwszej grupy \(\displaystyle{ n-1}\) osobowej, a pozostałe \(\displaystyle{ n-k}\) mężczyzn wrzucamy do drugiej grupy. Następnie wybieramy \(\displaystyle{ n-k}\) kobiet spośród \(\displaystyle{ n}\) (\(\displaystyle{ {n\choose k}}\) sposobów) i wrzucamy do pierwszej grupy (razem jest \(\displaystyle{ n-k+k-1 = n-1}\) osób) a z pozostałych \(\displaystyle{ k}\) kobiet losujemy liderkę (\(\displaystyle{ k}\) sposobów). Pozostało jeszcze \(\displaystyle{ k-1}\) kobiet, które wrzucamy do drugiej grupy. W ten sposób otrzymaliśmy lewą stronę.
Oba losowania są równoważne, zatem to pokazuje równość.
-
vpprof
- Użytkownik
- Posty: 492
- Rejestracja: 11 paź 2012, o 11:20
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 26 razy
- Pomógł: 64 razy
Dowód kombinatoryczny
Mortify, bardzo ładny przykład, ale nie za bardzo widzę, w jaki sposób dochodzisz do sumy z lewej strony nierówności. Tzn. nie widzę gdzie jest u ciebie \(\displaystyle{ {n \choose 1}, {n \choose 2}}\) itd.
Ja też się zastanawiałem, z tym że wyszedłem od lewej strony i wymyśliłem coś takiego.
Mamy hodowlę np. psów, \(\displaystyle{ n}\) samców i \(\displaystyle{ n}\) samic. Mamy wybrać kilka par, które są wartościowe. Wśród tych par, jedna para pojedzie na konkurs.
Lewa strona równania. \(\displaystyle{ k}\) określa, ile par uznamy za wartościowe; możemy uznać od jednej do wszystkich par (bo takie mamy granice sumowania). Na przykład mamy \(\displaystyle{ n=6}\) osobników każdej płci, uznajemy za wartościowe \(\displaystyle{ k=2}\) samce i tyleż samic (czyli \(\displaystyle{ {n \choose k}}\) dla samców i \(\displaystyle{ {n \choose k}}\) dla samic, czyli \(\displaystyle{ {n \choose k}^2}\)) i spośród nich wybieramy po jednym osobniku każdej płci, który ma pojechać na konkurs (możemy to zrobić na \(\displaystyle{ k^2}\) sposobów), czyli \(\displaystyle{ k^2 {n \choose k}^2}\). Wybranych musi być tyle samo samców ile samic.
Oczywiste jest, że w każdej sytuacji możemy przypisać naszemu wyborowi tylko jedną liczbę wybranych par, np. jeśli wybraliśmy \(\displaystyle{ 3}\) pary, to nie wybraliśmy jednocześnie \(\displaystyle{ 4}\) par. Stąd też mamy sumę. Gdybyśmy mogli przypisać kilka różnych liczb par do danej sytuacji (np. gdybyśmy mieli kilka hodowli i w każdej mogli wybrać inną liczbę par), wtedy mielibyśmy iloczyn.
Teraz strona prawa. Wybieramy samca i samicę, które mają pojechać na konkurs (\(\displaystyle{ n^2}\) sposobów). Następnie spośród pozostałych \(\displaystyle{ 2n-2}\) osobników wybieramy połowę, czyli \(\displaystyle{ n-1}\). W przypadku samców wybór oznacza że są wartościowe, zaś w przypadku samic, że nie są wartościowe.
Można zapytać, dlaczego tak. Otóż po pierwsze, tak po prostu pasuje a jak historyjka pasuje, to jest OK. Po drugie, zauważmy, że jeśli mamy dwa równoliczne zbiory (samców i samic) i wybieramy połowę osobników, to obojętnie jaka będzie proporcja wybranych samców do samic, jeśli odwrócimy wybór w jednej płci, liczba wybranych samców i samic będzie równa.
Prosto to pokazać: mamy \(\displaystyle{ x}\) wybranych samców i \(\displaystyle{ y}\) wybranych samic. Liczba sumuje się do \(\displaystyle{ x+y=n}\), a wszystkich osobników jest \(\displaystyle{ 2n}\), więc odwracając wybór u samic, dostaniemy \(\displaystyle{ x}\) samców i \(\displaystyle{ n-y=n-(n-x)=x}\) samic.
Ja też się zastanawiałem, z tym że wyszedłem od lewej strony i wymyśliłem coś takiego.
Mamy hodowlę np. psów, \(\displaystyle{ n}\) samców i \(\displaystyle{ n}\) samic. Mamy wybrać kilka par, które są wartościowe. Wśród tych par, jedna para pojedzie na konkurs.
Lewa strona równania. \(\displaystyle{ k}\) określa, ile par uznamy za wartościowe; możemy uznać od jednej do wszystkich par (bo takie mamy granice sumowania). Na przykład mamy \(\displaystyle{ n=6}\) osobników każdej płci, uznajemy za wartościowe \(\displaystyle{ k=2}\) samce i tyleż samic (czyli \(\displaystyle{ {n \choose k}}\) dla samców i \(\displaystyle{ {n \choose k}}\) dla samic, czyli \(\displaystyle{ {n \choose k}^2}\)) i spośród nich wybieramy po jednym osobniku każdej płci, który ma pojechać na konkurs (możemy to zrobić na \(\displaystyle{ k^2}\) sposobów), czyli \(\displaystyle{ k^2 {n \choose k}^2}\). Wybranych musi być tyle samo samców ile samic.
Oczywiste jest, że w każdej sytuacji możemy przypisać naszemu wyborowi tylko jedną liczbę wybranych par, np. jeśli wybraliśmy \(\displaystyle{ 3}\) pary, to nie wybraliśmy jednocześnie \(\displaystyle{ 4}\) par. Stąd też mamy sumę. Gdybyśmy mogli przypisać kilka różnych liczb par do danej sytuacji (np. gdybyśmy mieli kilka hodowli i w każdej mogli wybrać inną liczbę par), wtedy mielibyśmy iloczyn.
Teraz strona prawa. Wybieramy samca i samicę, które mają pojechać na konkurs (\(\displaystyle{ n^2}\) sposobów). Następnie spośród pozostałych \(\displaystyle{ 2n-2}\) osobników wybieramy połowę, czyli \(\displaystyle{ n-1}\). W przypadku samców wybór oznacza że są wartościowe, zaś w przypadku samic, że nie są wartościowe.
Można zapytać, dlaczego tak. Otóż po pierwsze, tak po prostu pasuje a jak historyjka pasuje, to jest OK. Po drugie, zauważmy, że jeśli mamy dwa równoliczne zbiory (samców i samic) i wybieramy połowę osobników, to obojętnie jaka będzie proporcja wybranych samców do samic, jeśli odwrócimy wybór w jednej płci, liczba wybranych samców i samic będzie równa.
Prosto to pokazać: mamy \(\displaystyle{ x}\) wybranych samców i \(\displaystyle{ y}\) wybranych samic. Liczba sumuje się do \(\displaystyle{ x+y=n}\), a wszystkich osobników jest \(\displaystyle{ 2n}\), więc odwracając wybór u samic, dostaniemy \(\displaystyle{ x}\) samców i \(\displaystyle{ n-y=n-(n-x)=x}\) samic.