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.
obliczanie sumy, wykazanie sumy oraz cykle
obliczanie sumy, wykazanie sumy oraz cykle
Ostatnio zmieniony 16 maja 2013, o 23:35 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex] .
Powód: Całe wyrażenia matematyczne umieszczaj w tagach
- lina2002
- Użytkownik
- Posty: 599
- Rejestracja: 27 mar 2008, o 13:55
- Płeć: Kobieta
- Lokalizacja: Kraków
- Pomógł: 151 razy
obliczanie sumy, wykazanie sumy oraz cykle
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.
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.