1)Udowodnić tożsamość:
\(\displaystyle{ \sum_{k=1}^{n}k^{2} =n(n+1)2^{n-2}}\)
2)Rozważmy wszystkie r-elementowe podzbiory zbioru {1,...,n} dla ustalone \(\displaystyle{ r \leqslant n}\) i w każdym z nich wybieramy najmniejszą liczbę. Wykaż, że średnia arytmetyczna otrzymanych w ten sposób liczb jest równa \(\displaystyle{ \frac{n+1}{r+1}}\)
[Kombinatoryka] Dwumian Newtona
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
frej
[Kombinatoryka] Dwumian Newtona
1)
KLIK
Zapamiętajmy drugą sumę. Rozważmy teraz funkcję:
\(\displaystyle{ f(x)=(1+x)^n}\)
Z jednej strony druga jej pochodna wynosi
\(\displaystyle{ n(n-1)(1+x)^{n-2}}\)
Z drugiej strony
\(\displaystyle{ f''(x)=\left( \sum_{k=0}^{n}{n \choose k}x^{k} \right)''=\left( \sum_{k=0}^{n} k(k-1){n \choose k}x^{k} \right)=\sum_{k=0}^{n} k^2{n \choose k}x^{k} - \sum_{k=0}^{n} k{n \choose k}x^{k}}\)
Przyjmując \(\displaystyle{ x=1}\) Mamy, że
\(\displaystyle{ n(n-1)2^{n-2}= \sum_{k=0}^{n} k^2{n \choose k}x^{k} - n2^{n-1}}\)
Wobec czego szukana suma wynosi \(\displaystyle{ \sum_{k=0}^{n} k^2{n \choose k}x^{k}=n\left( n2^{n-2}-2^{n-2}+2^{n-1}\right)=n(n+1)2^{n-2}}\)
KLIK
Zapamiętajmy drugą sumę. Rozważmy teraz funkcję:
\(\displaystyle{ f(x)=(1+x)^n}\)
Z jednej strony druga jej pochodna wynosi
\(\displaystyle{ n(n-1)(1+x)^{n-2}}\)
Z drugiej strony
\(\displaystyle{ f''(x)=\left( \sum_{k=0}^{n}{n \choose k}x^{k} \right)''=\left( \sum_{k=0}^{n} k(k-1){n \choose k}x^{k} \right)=\sum_{k=0}^{n} k^2{n \choose k}x^{k} - \sum_{k=0}^{n} k{n \choose k}x^{k}}\)
Przyjmując \(\displaystyle{ x=1}\) Mamy, że
\(\displaystyle{ n(n-1)2^{n-2}= \sum_{k=0}^{n} k^2{n \choose k}x^{k} - n2^{n-1}}\)
Wobec czego szukana suma wynosi \(\displaystyle{ \sum_{k=0}^{n} k^2{n \choose k}x^{k}=n\left( n2^{n-2}-2^{n-2}+2^{n-1}\right)=n(n+1)2^{n-2}}\)
-
Wasilewski
- Użytkownik
- Posty: 3921
- Rejestracja: 10 gru 2007, o 20:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 36 razy
- Pomógł: 1194 razy
[Kombinatoryka] Dwumian Newtona
2) https://www.matematyka.pl/67705.htm?highlight=srednie+minimum
1) Bez pochodnych:
\(\displaystyle{ k^2 {n\choose k} = k(k-1) {n\choose k} + k {n\choose k} = k(k-1) \frac{n!}{k!(n-k)!} + k \frac{n!}{k!(n-k)!} = \\ n(n-1) {n-2 \choose k-2} + n {n-1 \choose k-1}}\)
Zatem:
\(\displaystyle{ \sum_{k=0}^{n} k^2 {n\choose k} = \sum_{k=0}^{n} n(n-1) {n-2\choose k-2} + \sum_{k=0}^{n} n {n-1 \choose k-1} = \sum_{k=0}^{n-2} n(n-1) {n-2 \choose k} + \sum_{k=0}^{n-1} n {n-1 \choose k} = n(n-1)2^{n-2} + n2^{n-1} =n(n+1)2^{n-2}}\)
1) Bez pochodnych:
\(\displaystyle{ k^2 {n\choose k} = k(k-1) {n\choose k} + k {n\choose k} = k(k-1) \frac{n!}{k!(n-k)!} + k \frac{n!}{k!(n-k)!} = \\ n(n-1) {n-2 \choose k-2} + n {n-1 \choose k-1}}\)
Zatem:
\(\displaystyle{ \sum_{k=0}^{n} k^2 {n\choose k} = \sum_{k=0}^{n} n(n-1) {n-2\choose k-2} + \sum_{k=0}^{n} n {n-1 \choose k-1} = \sum_{k=0}^{n-2} n(n-1) {n-2 \choose k} + \sum_{k=0}^{n-1} n {n-1 \choose k} = n(n-1)2^{n-2} + n2^{n-1} =n(n+1)2^{n-2}}\)
-
Dumel
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
[Kombinatoryka] Dwumian Newtona
fajne rozwiązanie zad. 1. zaprezentował soliter na kongresie matematyków:
wyobraźmy sobie że z grupy \(\displaystyle{ n}\) osob chcemy wybrac jakac podgrupe do czegoś tam i w tej podgrupie przydzielic jakies dwie funkcje (np. pucybuta i podawacza ręczników ), przy czym jedna osoba moze sprawować je obie.
Na ile sposobów mozna to uczynić? Z jednej strony możemy dla każdego \(\displaystyle{ k}\) rozwazyc \(\displaystyle{ k}\)-osobowe grupy osób i w kazdej z nich na \(\displaystyle{ k^2}\) sposobow przydzielic te funkcje- to wlasnie reprezentuje lewa strona tożsamości
Mozna tez rozbić to na 2 przypadki:
a)obie funkcje sprawuje ta sama osoba. tutaj mamy \(\displaystyle{ n 2^{n-1}}\) możliwości (wybieramy jedną z \(\displaystyle{ n}\) osob i dorzucamy do niej jedną z \(\displaystyle{ 2^{n-1}}\) grup pozostalych)
b)funkcje sprawują różne osoby. liczba możliwości: \(\displaystyle{ n(n-1)2^{n-2}}\)
wyobraźmy sobie że z grupy \(\displaystyle{ n}\) osob chcemy wybrac jakac podgrupe do czegoś tam i w tej podgrupie przydzielic jakies dwie funkcje (np. pucybuta i podawacza ręczników ), przy czym jedna osoba moze sprawować je obie.
Na ile sposobów mozna to uczynić? Z jednej strony możemy dla każdego \(\displaystyle{ k}\) rozwazyc \(\displaystyle{ k}\)-osobowe grupy osób i w kazdej z nich na \(\displaystyle{ k^2}\) sposobow przydzielic te funkcje- to wlasnie reprezentuje lewa strona tożsamości
Mozna tez rozbić to na 2 przypadki:
a)obie funkcje sprawuje ta sama osoba. tutaj mamy \(\displaystyle{ n 2^{n-1}}\) możliwości (wybieramy jedną z \(\displaystyle{ n}\) osob i dorzucamy do niej jedną z \(\displaystyle{ 2^{n-1}}\) grup pozostalych)
b)funkcje sprawują różne osoby. liczba możliwości: \(\displaystyle{ n(n-1)2^{n-2}}\)