Jak policzyć zwartą postać takiej sumy? \(\displaystyle{ \sum_{i=0}^{n}i^2\binom{n}{i}^2}\)
Aż chciałoby się przez jakąś interpretację kombinatoryczną, ale niestety nie mogę wymyślić odpowiedniej.-- 28 sierpnia 2011, 23:34 --Chyba już mam. \(\displaystyle{ \sum_{i=0}^{n}i^2\binom{n}{i}^2= \sum_{i=0}^{n}i^2\binom{n}{i}\binom{n}{n-i}}\)
Teraz jak mamy taką sumę, to weźmy sobie dwa zbiory kulek nierozróżnialnych, w każdym po n kulek. Ta suma mówi nam tyle, że z każdego z tych zbiorów wybieramy po i kulek, a później z każdych i kulek wybieramy tę najlepszą.
Z drugiej strony skoro te kulki są nierozróżnialne, to od razu możemy wybrać 2 najlepsze kulki (po jednej z każdego zbioru), a później dobrać do nich pozostałe n-2 już ze zbiorów połączonych (suma po prawej to mówi).
Zatem wynikiem powinno być: \(\displaystyle{ n^2\binom{2n-2}{n-2}}\). Czy to jest dobrze?
Rozważmy liczbę czwórek \(\displaystyle{ (X,Y,a,b)}\) takich, że \(\displaystyle{ X \subset \{1,...,n\}}\), \(\displaystyle{ Y \subset \{n+1, ..., 2n\}}\), \(\displaystyle{ |X|+|Y|=n}\), \(\displaystyle{ a \in X}\), \(\displaystyle{ b \in \{n+1, ... , 2n\}-Y}\).
Zinterpretujmy lewą stronę, ustalmy \(\displaystyle{ |X|=i}\), przesumujemy po wszystkich \(\displaystyle{ i}\), wybieramy \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) na odpowiednio \(\displaystyle{ {n \choose i}}\) i \(\displaystyle{ {n \choose n-i}}\) sposobów, następnie \(\displaystyle{ a}\) i \(\displaystyle{ b}\) na odpowiednio \(\displaystyle{ i}\) i \(\displaystyle{ (n-(n-i))=i}\) sposobów, łącznie na \(\displaystyle{ i^2 {n \choose i}^2}\) sposobów.
Z drugiej strony wybieramy najpierw \(\displaystyle{ a}\) i \(\displaystyle{ b}\) na odpowiednio \(\displaystyle{ n}\) i \(\displaystyle{ n}\) sposobów, następnie pamiętając, że \(\displaystyle{ a \in X}\) i \(\displaystyle{ b \not \in Y}\) podzbiór \(\displaystyle{ n-1}\) elementowy z \(\displaystyle{ \{1,...,2n\} - \{a,b\}}\), który determinuje \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), możemy to uczynić na \(\displaystyle{ {2n-2 \choose n-1}}\) sposobów, łącznie na \(\displaystyle{ n^2 {2n-2 \choose n-1}}\) sposobów.
