Zwarta postać sumy

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
aolo23
Użytkownik
Użytkownik
Posty: 307
Rejestracja: 5 sty 2016, o 13:01
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 118 razy
Pomógł: 2 razy

Zwarta postać sumy

Post autor: aolo23 »

Cześć
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2}}\)

przedstawić w zwartej postaci sumy, mam skorzystać z :
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k=n \cdot 2^{n-1}}\)

Niezbyt mam chęć na korzystanie z owej podpowiedzi i chciałbym się zapytać czy wynikiem będzie:

\(\displaystyle{ \sum_{k=1}^{n} {n \choose k}k^{2} = \frac{(n+1)n(2n+1)}{6} \cdot 2^{n}}\)
Ostatnio zmieniony 5 mar 2018, o 22:13 przez aolo23, łącznie zmieniany 1 raz.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Zwarta postać sumy

Post autor: Premislav »

Interpretacja kombinatoryczna: wybieramy spośród \(\displaystyle{ n}\) osób zarząd (o nieustalonej liczbie członków) Komitetu Wsparcia Jarosława Kaczyńskiego, przy czym spośród wybranych członków dokonujemy wyboru przewodniczącego i skarbnika i przyjmujemy, że funkcje te można łączyć.
Z jednej strony wybieramy \(\displaystyle{ k}\) osób spośród n i na \(\displaystyle{ k^2}\) sposobów przydzielić możemy stanowiska przewodniczącego i skarbnika (\(\displaystyle{ {k \choose 1}{k \choose 1}}\)), z drugiej strony
albo przewodniczącym i skarbnikiem będzie ta sama osoba, albo nie, jeśli będzie ta sama, to na \(\displaystyle{ n}\) sposobów dobieramy przewodniczącego, który zarazem będzie skarbnikiem i możemy mu dobrać grupę z \(\displaystyle{ n-1}\) pozostałych, co odpowiada wyborowi podzbioru zbioru \(\displaystyle{ n-1}\)-elementowego, czyli takich wyborów jest \(\displaystyle{ n2^{n-1}}\). Jeśli natomiast przewodniczącym i skarbnikiem będą dwie różne osoby, to na \(\displaystyle{ n}\) sposobów wybieramy przewodniczącego, z pozostałych na \(\displaystyle{ n-1}\) sposobów wybieramy skarbnika, no i możemy jeszcze powiększyć zarząd (albo nie), co odpowiada wyborowi pewnej liczby spośród \(\displaystyle{ n-2}\) pozostałych, czyli wyborowi podzbioru zbioru \(\displaystyle{ n-2}\)-elementowego (na \(\displaystyle{ 2^{n-2}}\) sposobów). Takich możliwości jest zatem \(\displaystyle{ n(n-1)2^{n-2}}\).
Sumując, mamy
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2}=n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}}\)

To zadanie można zrobić inaczej, a mianowicie rozpisując
\(\displaystyle{ k^2{n \choose k}=k(k-1){n \choose k}+k {n\choose k}=n(n-1){n-2\choose k-2}+n{n-1\choose k-1}}\) dla \(\displaystyle{ n\ge 2}\), czyli
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2}=n \sum_{k=1}^{n-1} {n-1\choose k-1}+n(n-1) \sum_{k=2}^{n} {n-2\choose k-2}}\)
ODPOWIEDZ