[Kombinatoryka] symbol 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.
[Kombinatoryka] symbol Newtona
udowodnić:
\(\displaystyle{ \sum_{k=0}^{n} ^2 = {2n \choose n}}\)
Najpierw próbowałem indukcją (ale nie wyszło), potem próbowałem wykorzystać fakt, że \(\displaystyle{ {p+1 \choose k+1}= {p \choose k}+ {p \choose k+1}}\), ale powstał problem z policzeniem \(\displaystyle{ \sum_{k=0}^{n-1} {n \choose k+1}}\)
jeśli ktoś umie, to można rozwiązywać drugą nierówność. Jeśli jednak robię niezbyt dobrze, to pierwsza równość jest równie mile widziana.
\(\displaystyle{ \sum_{k=0}^{n} ^2 = {2n \choose n}}\)
Najpierw próbowałem indukcją (ale nie wyszło), potem próbowałem wykorzystać fakt, że \(\displaystyle{ {p+1 \choose k+1}= {p \choose k}+ {p \choose k+1}}\), ale powstał problem z policzeniem \(\displaystyle{ \sum_{k=0}^{n-1} {n \choose k+1}}\)
jeśli ktoś umie, to można rozwiązywać drugą nierówność. Jeśli jednak robię niezbyt dobrze, to pierwsza równość jest równie mile widziana.
[Kombinatoryka] symbol Newtona
Dargi, z tego co wiem, to \(\displaystyle{ \sum_{k=0}^{n} =2^n}\) ale też
\(\displaystyle{ \sum_{k=0}^{n} ^2 < ( \sum_{k=0}^{n} )^2=(2^n)^2=2^{2n}}\)
chyba, że znów mi coś nie wyszło...
\(\displaystyle{ \sum_{k=0}^{n} ^2 < ( \sum_{k=0}^{n} )^2=(2^n)^2=2^{2n}}\)
chyba, że znów mi coś nie wyszło...
-
- Użytkownik
- Posty: 195
- Rejestracja: 13 paź 2005, o 17:04
- Płeć: Mężczyzna
- Lokalizacja: Jelenia Góra
- Podziękował: 4 razy
- Pomógł: 28 razy
[Kombinatoryka] symbol Newtona
Niech dana będzie siatka punktów kratowych o rozmiarach n+1 x n+1.
Z lewego-dolnego do prawego-górnego rogu można dotrzeć na \(\displaystyle{ {2n\choose n}}\) sposobów, wykonując wyłącznie ruchy w prawo oraz w górę po siatce, ponieważ każda droga to sekwencja 2n ruchów, z których dokładnie n to ruchy w prawo i dokładnie n to ruchy w górę.
Każda z tych dróg przechodzi przez dokładnie jeden z n+1 punktów kratowych dużej przekątnej niezawierającej położenia początkowego. Łatwo pokazać, że liczby dróg przechodzących przez kolejne punkty owej przekątnej (patrząc z perspektywy jednego z jej końców) są równe odpowiednio \(\displaystyle{ {n\choose 0}^2,\ {n\choose 1}^2,\ \ldots, {n\choose n}^2}\).
Sorry, jeśli za bardzo skracałem myśli.
Z lewego-dolnego do prawego-górnego rogu można dotrzeć na \(\displaystyle{ {2n\choose n}}\) sposobów, wykonując wyłącznie ruchy w prawo oraz w górę po siatce, ponieważ każda droga to sekwencja 2n ruchów, z których dokładnie n to ruchy w prawo i dokładnie n to ruchy w górę.
Każda z tych dróg przechodzi przez dokładnie jeden z n+1 punktów kratowych dużej przekątnej niezawierającej położenia początkowego. Łatwo pokazać, że liczby dróg przechodzących przez kolejne punkty owej przekątnej (patrząc z perspektywy jednego z jej końców) są równe odpowiednio \(\displaystyle{ {n\choose 0}^2,\ {n\choose 1}^2,\ \ldots, {n\choose n}^2}\).
Sorry, jeśli za bardzo skracałem myśli.
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
[Kombinatoryka] symbol Newtona
Mamy wielomian:
\(\displaystyle{ P(x)=(x+1)^{2n} \\ P(x)=({n \choose 0}x^n + {n \choose 1}x^{n-1}+\ldots+{n \choose n} 1) ({n \choose 0}x^n + {n \choose 1}x^{n-1}+\ldots+{n \choose n} 1)}\)
Na dwa sposoby zapiszmy współczynnik przy \(\displaystyle{ x^n}\) (oznaczmy Q). Z pierwszego równania mamy (bezpośrednio z dwumianu Newtona \(\displaystyle{ Q={2n \choose n}}\). Z drugiego równania wynosi on (wymnażamy wyrazy z \(\displaystyle{ x^k}\) przez wyrazy z \(\displaystyle{ x^{n-k}}\)):
\(\displaystyle{ Q={n \choose 0} {n \choose n} + {n \choose 1} {n \choose n-1} + \ldots = \\ ={n \choose 0} {n \choose 0} + {n \choose 1} {n \choose 1} + \ldots = \sum_{k=0}^{n} ^2}\)
Przedostatnia równość z najbardziej podstawowej własności symbolu Newtona.
\(\displaystyle{ P(x)=(x+1)^{2n} \\ P(x)=({n \choose 0}x^n + {n \choose 1}x^{n-1}+\ldots+{n \choose n} 1) ({n \choose 0}x^n + {n \choose 1}x^{n-1}+\ldots+{n \choose n} 1)}\)
Na dwa sposoby zapiszmy współczynnik przy \(\displaystyle{ x^n}\) (oznaczmy Q). Z pierwszego równania mamy (bezpośrednio z dwumianu Newtona \(\displaystyle{ Q={2n \choose n}}\). Z drugiego równania wynosi on (wymnażamy wyrazy z \(\displaystyle{ x^k}\) przez wyrazy z \(\displaystyle{ x^{n-k}}\)):
\(\displaystyle{ Q={n \choose 0} {n \choose n} + {n \choose 1} {n \choose n-1} + \ldots = \\ ={n \choose 0} {n \choose 0} + {n \choose 1} {n \choose 1} + \ldots = \sum_{k=0}^{n} ^2}\)
Przedostatnia równość z najbardziej podstawowej własności symbolu Newtona.
Ostatnio zmieniony 3 lip 2008, o 23:38 przez Sylwek, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 260
- Rejestracja: 3 lis 2007, o 17:47
- Płeć: Mężczyzna
- Lokalizacja: Nidzica
- Podziękował: 30 razy
- Pomógł: 59 razy
[Kombinatoryka] symbol Newtona
\(\displaystyle{ f(x)=(1+x)^{n} (1+x)^{n}}\)
Współczynnik przy x^n w iloczynie będzie \(\displaystyle{ \sum_{k=0}^{n} ^{2}}\) Natomiast w wielomianie \(\displaystyle{ f(x)=(1+x)^{2n}}\) wpółczynnik przy x^n wynosi \(\displaystyle{ {2n \choose n}}\) stąd juz otrymujemy co chcieliśmy.
edit
heh to samo co Sylwek
Współczynnik przy x^n w iloczynie będzie \(\displaystyle{ \sum_{k=0}^{n} ^{2}}\) Natomiast w wielomianie \(\displaystyle{ f(x)=(1+x)^{2n}}\) wpółczynnik przy x^n wynosi \(\displaystyle{ {2n \choose n}}\) stąd juz otrymujemy co chcieliśmy.
edit
heh to samo co Sylwek