suma k^2*(n po k)

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
nivwusquorum
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 31 maja 2007, o 17:53
Płeć: Mężczyzna
Lokalizacja: Chojnice
Podziękował: 1 raz
Pomógł: 3 razy

suma k^2*(n po k)

Post autor: nivwusquorum »

Witam,

siedzę już od ponad godziny i nie mogę rozwiązać. A wygląda tak niepozornie:

\(\displaystyle{ 1^2{n \choose 1 } + 2^2 {n \choose 2} + ... + n^2{n \choose n} = n(n+1)2^{n-2}}\)

Dodatkowo możliwe, że rozwiązanie ułatwia skorzystanie z któregoś z (było w tym samym zadaniu co to powyżej):

a) \(\displaystyle{ {n \choose 0 } + {n \choose 1} + ... + {n \choose n} = 2^n}\)

b) \(\displaystyle{ 1{n \choose 1 } + 2 {n \choose 2} + ... + n{n \choose n} = n2^{n-1}}\)

c) \(\displaystyle{ 1{n \choose 0 } + \frac{1}{2}{n \choose 1} + ... + \frac{1}{n+1}{n \choose n} = \frac{1}{n+1}(2^{n+1}-1)}\)

d) Rozwinięcie \(\displaystyle{ (1+x)^n}\)
abc666

suma k^2*(n po k)

Post autor: abc666 »

A jak zrobiłeś podpunkt b) ?
nivwusquorum
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 31 maja 2007, o 17:53
Płeć: Mężczyzna
Lokalizacja: Chojnice
Podziękował: 1 raz
Pomógł: 3 razy

suma k^2*(n po k)

Post autor: nivwusquorum »

Dzielisz obustronnie przez n, że
\(\displaystyle{ \frac{k}{n} {n \choose k} = {n-1 \choose k-1 }}\)

czyli masz po prostu
\(\displaystyle{ {n-1 \choose 0 } + {n-1 \choose 1} + ... + {n-1 \choose n-1} = 2^{n-1}}\)
jacek.karaskiewicz
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 22 cze 2010, o 16:41
Płeć: Mężczyzna
Lokalizacja: Warszawa

suma k^2*(n po k)

Post autor: jacek.karaskiewicz »

Nie wiem, czy rozwiązanie za pomocą interpretacji kombinatorycznej jest dla Ciebie satysfakcjonujące, ale tak czy owak je przedstawię.

Zliczamy ogólnie delegacje (o dowolnej liczbie osób) z grupy n-osobowej, a następnie w delegacji wyznaczamy szefa i skarbnika, z tymże jedna osoba może pełnić obie funkcje naraz. Po lewej stronie równości mamy sumę po liczności delegacji - każdy składnik odpowiada za wybranie \(\displaystyle{ k}\) osób z \(\displaystyle{ n}\) wszystkich uczestników, a następnie szefa (\(\displaystyle{ k}\) możliwości) i skarbnika (\(\displaystyle{ k}\) możliwości), co daje \(\displaystyle{ k^{2}}\) przed każdym składnikiem sumy. Z \(\displaystyle{ k}\) idziemy oczywiście od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\). Z kolei można to też zinterpretować tak:

Wybieramy szefa i skarbnika, a następnie dobieramy delegacje.
1) Szef i skarbnik to ta sama osoba, więc możemy wybrać ją na \(\displaystyle{ n}\) sposobów, a następnie pozostałych uczestników delegacji na \(\displaystyle{ 2^{n-1}}\) sposobów (liczba podzbiorów zbioru \(\displaystyle{ (n-1)}\)-elementowego).
Daje nam to \(\displaystyle{ n \cdot 2^{n-1}}\).

2) Szef i skarbnik to dwie różne osoby. Wybieramy szefa na \(\displaystyle{ n}\) sposobów, skarbnika na \(\displaystyle{ n-1}\) sposobów, a pozostałą delegację na \(\displaystyle{ 2^{n-2}}\) sposobów. W ten sposób mamy \(\displaystyle{ n \cdot (n-1) \cdot 2^{n-2}}\).

Po zsumowaniu daje nam to \(\displaystyle{ n \cdot (n+1) \cdot 2^{n-2}}\), czyli tyle co po prawej stronie równania.
nivwusquorum
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 31 maja 2007, o 17:53
Płeć: Mężczyzna
Lokalizacja: Chojnice
Podziękował: 1 raz
Pomógł: 3 razy

suma k^2*(n po k)

Post autor: nivwusquorum »

Zarąbiste rozwiązanie, podoba mi się strasznie. Niemniej jednak chętnie poznałbym rozwiązanie polegające na przekształceniach, bo takie rozwiązanie najprawdopodobniej jest oczekiwane...
jacek.karaskiewicz
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 22 cze 2010, o 16:41
Płeć: Mężczyzna
Lokalizacja: Warszawa

suma k^2*(n po k)

Post autor: jacek.karaskiewicz »

Znalazłem też rozwiązanie przez "normalne", ale niestety jest trochę skomplikowane (pewnie gdzieś sam coś sobie utrudniłem).

A więc tak - przekształcamy z lewej do prawej.

Po lewej stronie mamy:

\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2} = \sum_{k=0}^{n} {n \choose k} k^{2} = S_n}\)

Mamy teraz:

\(\displaystyle{ S_{n+1} = \sum_{k=0}^{n+1} {n+1 \choose k} k^{2} = \sum_{k=0}^{n+1} {n \choose k} k^{2} + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = \sum_{k=0}^{n} {n \choose k} k^{2} + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = S_n + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = S_n + \sum_{k=-1}^{n} {n \choose k} (k+1)^{2} = S_n + \sum_{k=0}^{n} {n \choose k} (k+1)^{2} = S_n + \sum_{k=0}^{n} {n \choose k} (k^{2}+2k+1) = S_n + \sum_{k=0}^{n} {n \choose k} k^2 + 2\sum_{k=0}^{n} {n \choose k} k + \sum_{k=0}^{n} {n \choose k} = 2S_n + 2n \cdot 2^{n-1}+2^n}\)

Z tego mamy:

\(\displaystyle{ S_{n+1} = 2S_n + (n+1)2^n}\), czyli:
\(\displaystyle{ S_n = 2S_{n-1} + n2^{n-1}}\)
\(\displaystyle{ S_0 = 0}\)

Po rozwinięciu mamy:

\(\displaystyle{ S_n = 2S_{n-1} + n2^{n-1} = 2 \cdot (2S_{n-2} + (n-1) \cdot 2^{n-2}) + n2^{n-1} = ... = \sum_{k=0}^{n}2^{k}(n-k)2^{n-k-1}= \sum_{k=0}^{n} 2^{n-1} \cdot (n-k) = 2^{n-1} \cdot \sum_{k=0}^{n}(n-k) = 2^{n-1} \cdot \sum_{k=0}^{n}k = 2^{n-1} \cdot \frac{n(n+1)}{2} = n(n+1) \cdot 2^{n-2}}\)
ODPOWIEDZ