obliczanie sumy, wykazanie sumy oraz cykle

[fiman]

Witam,
Poszukuje pomocy z 3 zadaniami:

1)
Obliczyć: \(\displaystyle{ \sum_{i = 1}^{n} i {n \choose i}}\)
2)
Wykazać: \(\displaystyle{ \sum_{i = 0}^{n} {n \choose i} ^{2} = {2n \choose n}}\)
3)
Niech:
\(\displaystyle{ a = {1 2 3 4 5 6 7 \choose 2 4 3 1 5 6 7} \\
b = {1 2 3 4 5 6 7 \choose 7 6 2 1 4 5 3}}\)

wyznaczyć: \(\displaystyle{ a^{2}, ab, ba}\). Otrzymane permutacje rozłożyć na cykle rozłączne.

[lina2002]

1. \(\displaystyle{ \sum_{i = 1}^{n} i {n \choose i} = \sum_{i = 1}^{n} i\frac{n!} {i!(n-i)!} = \sum_{i = 1}^{n} \frac {(n-1)!n} {(i-1)!((n - 1) - (i - 1))!} = \sum_{i = 1}^{n} n {n - 1 \choose i -1} = n \sum_{i = 0}^{n - 1} {n - 1 \choose i} = n 2^{n-1}}\)

2. \(\displaystyle{ \sum_{i = 0}^{n} {n \choose i} ^{2} = \sum_{i = 0}^{n} {n \choose i} {n \choose n - i} = {2n \choose n}}\)
Uzasadnienie kombinatoryczne: dzielisz \(\displaystyle{ 2n}\) przedmiotów na dwie połowy. Zeby wybrać \(\displaystyle{ n}\) z nich możesz: wybrać 0 z pierwszej i wszystkie z drugiej, 1 z pierwszej i \(\displaystyle{ n - 1}\) z drugiej,..., czyli ogólnie \(\displaystyle{ i}\) z pierwszej i \(\displaystyle{ n-i}\) z drugiej dla \(\displaystyle{ i \in 0,...,n}\)

3. Próbowałeś w ogóle się za to zabrać? Robi się to tak: żeby dostać \(\displaystyle{ a^2}\) musisz zrobić permutację \(\displaystyle{ a}\) i na tym, co dostaniesz znowu. Np. popatrzmy na element 1: w \(\displaystyle{ a}\) przechodzi on na 2, z kolei 2 przechodzi na 4. Tak więc w \(\displaystyle{ a^2}\) 1 będzie przechodziło na 4 itd.