Symbol Newtona

Zbiór informacji o elementarnych zagadnieniach matematyki, klasyfikowanych najczęściej jako "ciekawostki" właśnie...
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Symbol Newtona

Post autor: mol_ksiazkowy »

Termin ten ma ogromne zastosowanie w wielu dziedzinach i stad jego tak duże znaczenie, ale najbardziej przewija się on jednak w kombinatoryce, co ma m.in związek z faktem iz wyraza on ilość k elementowych podzbiorów zbioru n elementowego, jak też to że istnieje bardzo wiele jego własności, które sa całkiem proste- zas ich dowody są na ogol trywialne, lecz niezwykle ważne. Trzeci powód wiąże się z tzw wzorem dwumiennym o czym ponizej, wzór ten jest jak łatwo zobaczyc tylko pewnym szczegolnym przypadkiem,- swego uogólnienia, a na koniec trzeba omówić trójkat Pascala,- sposób w jaki jest on zbudowany i korzysci z niego płynące. Nastąpi tez omówienie pewnych wiążacych się z tematem zagadnień z teorii liczb, a tj. z kwestią podzielności.


:arrow:
Def:
\(\displaystyle{ {n \choose k}= \frac{n!}{k! (n-k)!}}\), dla \(\displaystyle{ 0 \leq k \leq n}\), i \(\displaystyle{ n \in N}\). O ile n< k to symbol Newtona jest równy zero Uwaga: Uogolnienie :polega ono na dopuszenieniu liczb rzeczywistych i zespolonych jako "górnych " elementów. Tak "wzmocniony" symbol Newtona jest wszak po prostu wielomianem zmiennej x, stopnia k, którego współczynniki wyrazaja się przez tzw. liczby Stirlinga s(k,j) I go rodzaju, co wygląda tak:

\(\displaystyle{ {x \choose k}= \frac{x(x-1).....(x-(k-1))}{k!}= \sum_{j=0}^k \frac{s(k,j)}{k!} x^j}\)


Przykład
Obliczmy \(\displaystyle{ {6 \choose 2}}\) Mamy \(\displaystyle{ {6 \choose 2} =\frac{6!}{2! 4!} = \frac{4!* 5*6}{2! 4!} = \frac{30}{2!} =15}\) , Oznacza to że ze zbioru szescio-elementowego mozna wybrać 15 podzbiorów dwu-elementowych. I tyleż samo podzbiorów cztero-elementowych. Mamy też
\(\displaystyle{ {6 \choose 0} <{6 \choose 1} < {6 \choose 2} < {6 \choose 3} > {6 \choose 4} > {6 \choose 5} > {6 \choose 6}}\)



Dwumian Newtona jest to potoczna nazwa wzoru wyrazającego naturalną potęgę dwumianu, tj sumy dwóch składnikow przez potęgi jego składnikow :arrow: Po podstawieniu x=y=1, otzrymuje się wzór (1), zas gdy x=1, y=-1 wzór (b)..Liczba k element. kombinacji zbioru n+m elementowego spełnia zależność(c), którą zwiemy tożsamością Cauchy'ego. tj wzór (c). Ponadto zachodzą cztery ważne formuły wzory (a-d), i dalsze (e-h) :


\(\displaystyle{ (x+y)^n =\sum_{k=0}^n {n \choose k}x^ky^{n-k}}\) tj wzor-dwumian Newtona

:idea:

(a) \(\displaystyle{ \sum_{k=0}^n {n \choose k}=2^n}\)
(b) \(\displaystyle{ \sum_{k=0}^n (-1)^k {n \choose k}=0}\)
(c) \(\displaystyle{ {n+m \choose k}= \sum_{r=0}^k {n\choose r}{m \choose k-r}}\)
(d) \(\displaystyle{ {n \choose k}= {n \choose n-k}}\)



(e) \(\displaystyle{ {n+1 \choose k+1}= \frac{n+1}{k+1} {n \choose k}}\)

(f)\(\displaystyle{ {n \choose k+1}= {n \choose k} \frac{n-k}{k+1}}\)

(g) \(\displaystyle{ {n \choose m} {m \choose k}= {n \choose k} {n-k \choose m-k}}\)

(h) \(\displaystyle{ \sum_{r=k}^n {r\choose k} = {n+1 \choose k+1}}\)


:arrow: Wzór dwumianowy. można uogółnienić, wyraza to ponizszy wzór, sumowanie odbywa się po wszystkich rozkładach liczby \(\displaystyle{ n}\), tj. \(\displaystyle{ n_j \geq 0}\) oraz \(\displaystyle{ \sum_{j} n_j=n}\), zas wartość symbolu \(\displaystyle{ {n \choose n_1....n_k}}\) jest równa \(\displaystyle{ \frac{n!}{n_1 !....n_k !}}\)

\(\displaystyle{ (x_1+....+x_k)^n =\sum {n \choose n_1....n_k}x_1^{n_1}.....x_k^{n_k}}\)

Przyklad:
:arrow: \(\displaystyle{ (x+y+z)^3=x^3+3x^2y +3x^2z +3xy^2+ 6xyz+ 3xz^2+y^3+ 3y^2z +3yz^2+ z^3}\)



Teoria liczb a symbol Newtona
:arrow: (Erdos) Nie istnieja liczby naturalne \(\displaystyle{ 1<k<l<n}\) takie, ze \(\displaystyle{ {n \choose k}}\) i \(\displaystyle{ {n \choose l}}\) sa względnie pierwsze
:arrow: Jesli \(\displaystyle{ p}\) jest liczbą pierwszą, to \(\displaystyle{ {p \choose k}}\) jest podzielne przez \(\displaystyle{ p}\) dla \(\displaystyle{ k=1,2,....,p-1}\)
:arrow: Jeśli \(\displaystyle{ k}\) i \(\displaystyle{ n}\) sa to liczby naturalne i \(\displaystyle{ k<n}\), to
gdy Jeśli \(\displaystyle{ k}\) i \(\displaystyle{ n}\) sa względnie pierwsze, to \(\displaystyle{ n}\) dzieli \(\displaystyle{ {n \choose k}}\)
gdy \(\displaystyle{ k}\) jest pierwsza i dzieli \(\displaystyle{ n}\) to \(\displaystyle{ n}\) nie dzieli \(\displaystyle{ {n \choose k}}\)
:arrow:
:arrow: Jeśli \(\displaystyle{ 0 \leq k \leq n}\) to wtedy \(\displaystyle{ {n \choose k}}\) jest liczbą pierwszą, wtedy i tylko wtedy, gdy \(\displaystyle{ n}\) jest liczbą pierwszą i \(\displaystyle{ k=1}\) lub \(\displaystyle{ k=n-1}\)
:arrow: Jeśli \(\displaystyle{ p}\) jest liczbą pierwszą, a \(\displaystyle{ k <2p}\) i \(\displaystyle{ k}\) nie dzieli się przez \(\displaystyle{ p}\). Wtedy \(\displaystyle{ {2p \choose k}}\) dzieli się przez \(\displaystyle{ p}\)
:arrow: Jeśli \(\displaystyle{ p}\) jest liczbą pierwszą, i \(\displaystyle{ n<p}\), to reszta z dzielenia \(\displaystyle{ {np \choose p}}\) przez \(\displaystyle{ p}\) wynosi \(\displaystyle{ n}\)

:arrow: (i) wzor Lucasa, \(\displaystyle{ F_n= {n \choose 0} + {n-1 \choose 1}+ {n-2 \choose 2}+ ....}\), suma kończy sie gdy gorna liczba stanie sie mniejsza od dolnej.
gdzie \(\displaystyle{ F_n}\) to ciąg Fibonacciego


:arrow: Trójkat Pascala
Pierwszy wiersz i kolumna tego trójkąta złożone są z samych jedynek. Następne wiersze wypełnia się w ten sposób, że każda liczba w nim jest sumą liczby umieszczonej na lewo od niej i liczby jaka jest nad nią. Poza tym mamy tu symetryczna budowe przekątnych biegnących z lewej strony od dołu w prawą strone do góry. Suma liczb na każdej przekątnej (-mozna też mówić: "lewym skosie") jest dwukrotnością sumy liczb na przekątnej która ja poprzedza, etc. Warto "znależć" wypisane wyzej wzory w trójkącie Pascala. Liczby Fibonacciego mozna uzyskać z trójkącie Pascala wg reguły konia szachowego -tzw wzór Lucasa (i). Liczba jaka znajduje się w \(\displaystyle{ m}\)-tym wierszu i \(\displaystyle{ n}\)-tej kolumnie ma postać:

:arrow:\(\displaystyle{ t_{m,n}=\frac{m(m+1)....(m+n-2)}{(n-1)!}}\)

\(\displaystyle{ 1 \ \ 1 \ \ 1 \ \ 1 \ \ 1 .....}\)
\(\displaystyle{ 1 \ \ 2 \ \ 3 \ \ 4 \ \ 5 .....}\)
\(\displaystyle{ 1 \ \ 3 \ \ 6 \ \ 10 ......}\)
\(\displaystyle{ 1 \ \ 4 \ \ 10 \ 20......}\)
\(\displaystyle{ 1 \ \ 5 \ \ 15 ......}\)
\(\displaystyle{ 1 \ \ 6......}\)
\(\displaystyle{ 1......}\)
.........................................


Dodatkowe bardziej zaawansowane tożsamości:
(j) \(\displaystyle{ \sum_{k=0}^n { n \choose k}^2 = {2n \choose n}}\)
(k) \(\displaystyle{ \sum_{k=0}^n { n \choose k} \frac{1}{k+1} = \frac{2^{n+1}-1}{n+1}}\)
(l) \(\displaystyle{ \sum_{k=1}^n { n \choose k} \frac{(-1)^{k+1}}{k} = \sum_{k=1}^n \frac{1}{k}}\)
(m) \(\displaystyle{ \sum_{k=1}^n { n \choose k}^2 k = (2n-1) { 2n-2 \choose n-1}}\)
(n) \(\displaystyle{ \sum_{k=0}^{n-p} { n \choose k} {n \choose p+k} = {2n \choose n-p}}\), dla n>p>0
(o) \(\displaystyle{ \sum_{k=0}^{p} { n \choose k} {n-k \choose p-k} = 2^p{n \choose p}}\), dla n>p>0
(q) \(\displaystyle{ \sum_{k=0}^{n-1} (-1)^k { 4n \choose 2k} = \frac{(-1)^n}{2}(2^{2n} - {4n \choose 2n})}\), dla n>0
ODPOWIEDZ