[Kombinatoryka] Dwumian Newtona

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
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.
Awatar użytkownika
kluczyk
Użytkownik
Użytkownik
Posty: 441
Rejestracja: 20 paź 2006, o 22:44
Płeć: Mężczyzna
Lokalizacja: Małopolska
Podziękował: 77 razy
Pomógł: 12 razy

[Kombinatoryka] Dwumian Newtona

Post autor: kluczyk » 14 gru 2008, o 22:50

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 qslant 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}}\)

frej

[Kombinatoryka] Dwumian Newtona

Post autor: frej » 14 gru 2008, o 23:20

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}}\)

Wasilewski
Użytkownik
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

Post autor: Wasilewski » 14 gru 2008, o 23:28

2) http://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}}\)

Dumel
Użytkownik
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

Post autor: Dumel » 15 gru 2008, o 18:35

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}}\)

ODPOWIEDZ