Dyskusja:Symbol Newtona

Czy stwierdzenie "n nad k" nie jest lekko mylące? Wiele osób używa n nad k jako oznaczenia ułamka ${\displaystyle {\frac {n}{k}}}$...

To źle używają, i powinni się od tego jak najszybciej odzwyczaić – bo ${\displaystyle {\frac {n}{k}}}$ to jest zapis ułamka albo dzielenia, i czyta się "n dzielone przez k", lub krócej "n przez k". --CiaPan 00:28, 15 lut 2005 (CET)

Uważam że właśnie nie powinni się odzwyczajać. Matematycy z całego świata używają określenia n nad k do oznaczania ułamków. Nawet kiedy tutaj piszesz {n \over k} - otrzymujesz ${\displaystyle {n \over k}}$. :) Za to "n po k", twoje "n nad k" piszesz przecież {n \choose k} ${\displaystyle {n \choose k}}$. Paweusz 16:35, 10 cze 2005 (CEST)

Zgadzam się w tym temacie z CiaPan. W Polsce powszechnie jest stosowane w nomenklaturze dla ułamków n przez k zaś dla symbolu Newtona n nad k i niech tak zostanie. Danielm 19:02, 10 cze 2005 (CEST)

Skąd wiesz że "W Polsce powszechnie jest stosowane"?? Masz jakieś statystyki, wyniki badań? Tym bardziej, jeśli nawet - nie uważasz że lepiej byłoby się przestawić? Pisać tak jak wszyscy? paweusz 20:42, 10 cze 2005 (CEST)

Na polskich uczelniach "n nad k" używa się do ułamków, a "n po k" do symbolu newtona.

---

"Procedura ta nie ma wady poprzedniej metody – oblicza końcową wartość bez żadnego nadmiaru w wynikach pośrednich. Niestety, płaci się za to ogromnym kosztem obliczeń: wskutek rekurencji złożoność pamięciowa jest liniowa O(n), i to w bardzo wrażliwym obszarze stosu, zaś pesymistyczna złożoność czasowa aż rzędu kwadratowego O(n2)" ======No jeszcze raz ja..na pewno O(n^2)? a nie przy nCk, 2^(n-k)? ....5C3/\4C2+4C3/\/\3C1+3C2 3C2+3C3 ....1:2^0,2:2^1,3:2^2...1,2,4...=2^n-k....;-)

---

"Drobną wadą tego sposobu jest niewielki nadmiar w trakcie obliczeń: maksymalna wartość pośrednia, otrzymana przed ostatnim dzieleniem przez k, jest k-krotnie większa od ostatecznego wyniku." Coś mi tu nie pasuje. Wykorzystałem tą funkcję w programie i miałem problemy ze zbyt dużymi liczbami. Okazało się, że pośrednie wyniki dla n=100 i k=99 wyglądają tak (trochę wyciąłem):

100.000000
4950.000000
...
98913082887808039000000000000.000000
100891344545564200000000000000.000000 < to jest k * wynik?
98913082887808039000000000000.000000
...
161700.000000
4950.000000 < a może to jest k * wynik?...
100.000000 < wynik

Coś jest chyba źle lub nie dokładnie napisane...

Baktrian 17:29, 29 maja 2007 (CEST)

Trójkąt Pascala

Bardzo często rysuje się trójkąt Pascala jako trójkąt równoboczny, jednak znacznie czytelniejszym zapisem (szczególnie przy omawianiu trójkątów liczbowych) jest trójkąt prostokątny typu:

${\displaystyle {\begin{matrix}\mathbf {n} /{\mathit {k}}&\ {\mathit {0}}\ &\ {\mathit {1}}\ &{\mathit {2}}&{\mathit {3}}&{\mathit {4}}&{\mathit {5}}&{\mathit {6}}&{\mathit {7}}&\ {\mathit {8}}\ &{\mathit {9}}\\\mathbf {0} &1\\\mathbf {1} &1&1\\\mathbf {2} &1&2&1\\\mathbf {3} &1&3&3&1\\\mathbf {4} &1&4&6&4&1\\\mathbf {5} &1&5&10&10&5&1\\\mathbf {6} &1&6&15&20&15&6&1\\\mathbf {7} &1&7&21&35&35&21&7&1\\\mathbf {8} &1&8&28&56&70&56&28&8&1\\\mathbf {9} &1&9&36&84&126&126&84&36&9&1\end{matrix}}}$

patrz: "Matematyka Konkretna" Ronald L. Graham, Donald E. Knuth, Oren Patashnik (WN PWN) --WarX 22:38, 22 cze 2005 (CEST)

Ale przy trójkącie prostokątm zatraca się prostą zasadę rekurencyjną tworzenia kolejnego wiersza, któa mówi, że jako pierwszą i ostatnią wpisujemy jeden zaś kolejne współczynniki to suma dwóch będących powyżej z lewej i prawej strony. Poza tym wersja z trójkątem równobocznym jest jednak powszechniejsza. Zatem jestem za jej utrzymaniem przynajmniej w tym artykule oraz w Trójkąt Pascala. Danielm ✍ ✉ 14:52, 14 lis 2005 (CET)

Wzór ogólny

Myślę, że na samym początku artykułu powinien być podany wzór ogólny, a nie szczególny, czyli

${\displaystyle {n \choose k}={\frac {n(n-1)\cdots (n-k+1)}{1\cdot 2\cdots k}}}$

gdyż ten jest prawdziwy dla wszystkich liczb ${\displaystyle n\in R\land k\in N}$. (za R. Leitner, "Zarys matematyki wyższej").

Póżniej należałoby uwzględnić, że dla ${\displaystyle n\in N\land k\in N}$ zachodzi ${\displaystyle {n \choose k}={\frac {n!}{k!(n-k)!}}}$

Inny wzór

W książce "Matematyka konkretna", Knuth, Graham, Patashnik używa się zapisu ${\displaystyle {n \choose k}={\frac {n^{\underline {k}}}{k!}}}$, gdzie wyrażenie w liczniku to potęga ubywająca (dokładnie to co w wzorze powyżej).

Poza tym pierwsze zdanie jest nie poprawne. symbol newtona nie definiuję się przez wzór (ten czy inny), ale przez "ilość kombinacji k-elementowych ze zbioru n-elementowego", a potem się wyprowadza jego postać i uogólnia na inne przypadki. --Witold Baryluk 21:01, 13 gru 2006 (CET)

Fakt. Proszę koniecznie poprawić!

--WarX <talk> 22:36, 13 gru 2006 (CET)

bibliografia

usuwam bibliografię która została skopiowana z en a która IMHO nie była używana przy pisaniu tego hasła. (Np w naszej wersji nie ma nic o dzielnikach współczynników więc odsyłacz do pracy Singmastera był całŻiem nie na miejscu.) Patrz następująca opinia Hołka w kawiarence:

Nie, samo kopiowanie źródeł nie wchodzi nawet w rachubę, bo to zwykłe oszustwo.

{{Cytat}} Brakujące pola: treść. Przestarzałe pola: 1.

Stotr (dyskusja) 05:09, 6 mar 2008 (CET)

Parzystość symbolu Netwona

Ostatnio przypadkiem dotarłem do bardzo interesującej właściwości symbolu Newtona, niestety niepotwierdzonej żadnym źródłem ani nawet dowodem matematycznym. Dotyczy ona informacji na temat podzielności symbolu z n po k przez dwa która może zostać stwierdzona dla każdej wartości n i k za pomocą prostych działań logicznych: ((~n)&k). W uproszczeniu oznacza to, że jeśli w zapisie dwójkowym liczb n i k istnieje taka pozycja w której k ma 1, a n ma 0 to symbol Newtona z n po k będzie podzielny przez dwa.

Jeśli słyszał ktoś cokolwiek o tej właściwości i posiada jakieś źródło prosiłbym o wypowiedź lub uzupełnienie hasła.

Dowód

Tak, właśnie z ciekawości to udowodniłem. :-)
Zdaje się, że właśnie z tej właściwości wynika fraktalny wygląd trójkąta Pascala i sposób tworzenia z niego trójkąta Sierpińskiego. Do hasła wrzucał nie będę, bo to jednak mój OR, ale mogę się podzielić.

Niech ${\displaystyle d(x)\;}$ będzie liczbą dwójek w rozkładzie na czynniki pierwsze liczby x (czyli liczbą zer na końcu rozwinięcia binarnego x).

Jak łatwo zauważyć i udowodnić:

${\displaystyle d(2^{n})=n\;}$

(1)

${\displaystyle 1<x<2^{n}\Rightarrow d(2^{n}+x)=d(x)}$

(2)

${\displaystyle d(xy)=d(x)+d(y)\;}$

(3)

${\displaystyle d(x!)=\sum \limits _{i=1}^{x}d(i)}$

(4)

Lemat 1: ${\displaystyle d(2^{n}!)=2^{n}-1\;}$
Dowód przez indukcję ze względu na n:

• ${\displaystyle d(2^{0}!)=2^{0}-1\;}$
• ${\displaystyle d(2^{n+1}!){\overset {(4)}{=}}\sum \limits _{i=1}^{2^{n+1}}d(i)}$${\displaystyle {\overset {(3)}{=}}\sum \limits _{i=1}^{2^{n}-1}d(i)+d(2^{n})+\sum \limits _{i=1}^{2^{n}-1}d(2^{n}+i)\ +d(2^{n+1})}$${\displaystyle =\sum \limits _{i=1}^{2^{n}-1}\left(d(i)+d(2^{n}+i)\right)+n+n+1}$${\displaystyle =2\left(\sum \limits _{i=1}^{2^{n}-1}d(i)\ +n\right)+1}$${\displaystyle {\overset {(4)}{=}}2d(2^{n}!)+1{\overset {(indukcja)}{=}}2(2^{n}-1)+1=2^{n+1}-1}$

Jeśli ${\displaystyle 1<x<2^{n}\;}$ to:

${\displaystyle d((2^{n}+x)!){\overset {(3)}{=}}\sum \limits _{i=1}^{2^{n}}d(i)+\sum \limits _{i=1}^{x}d(2^{n}+i)}$${\displaystyle {\overset {(4),(2)}{=}}d(2^{n}!)+\sum \limits _{i=1}^{x}d(i)}$${\displaystyle {\overset {(4)}{=}}d(2^{n}!)+d(x!){\overset {(Lemat1)}{=}}2^{n}-1+d(x!)}$

(5)

Niech

${\displaystyle t_{k}=\sum \limits _{i=1}^{k}2^{b_{i}}}$

(6)

gdzie ${\displaystyle b_{i+1}>b_{i}\;}$


Lemat 2: ${\displaystyle d(t_{k}!)=t_{k}-k\;}$
Dowód przez indukcję ze względu na k.

• ${\displaystyle d(t_{1}!)=d(2^{b_{1}}!)=2^{b_{1}}-1=t_{1}-1\;}$
• ${\displaystyle d(t_{k+1}!)=d\left(\left(\sum \limits _{i=1}^{k}2^{b_{i}}\ +2^{b_{k+1}}\right)!\right)}$${\displaystyle {\overset {(3),(Lemat1)}{=}}2^{b_{k+1}}-1+d\left(\left(\sum \limits _{i=1}^{k}2^{b_{i}}\right)!\right)}$${\displaystyle {\overset {(4)}{=}}2^{b_{k+1}}-1+d(t_{k}!)=2^{b_{k+1}}-1+t_{k}-k=t_{k+1}-(k+1)}$

Niech ${\displaystyle b(t)}$ będzie liczbą jedynek w reprezentacji bitowej liczby t. Teraz lemat 2 można zapisać jako:

${\displaystyle d(t!)=t-b(t)\;}$

(7)

${\displaystyle d\left({n \choose k}\right)=d\left({\frac {n!}{k!(n-k)!}}\right){\overset {(3)}{=}}d(n!)-d(k!)-d((n-k)!)}$${\displaystyle {\overset {(7)}{=}}n-b(n)-k+b(k)-(n-k)+b(n-k)=-b(n)+b(k)+b(n-k)}$

Symbol Newtona jest parzysty wtedy i tylko wtedy, gdy ma dwójkę wśród dzielników: ${\displaystyle d\left({n \choose k}\right)>0}$, czyli gdy

${\displaystyle -b(n)+b(k)+b(n-k)>0\;}$

(8)

Niech:

• ${\displaystyle (x)_{i}\;}$ oznacza i-ty bit liczby x.
• ${\displaystyle r_{i}\;}$ oznacza liczbę "w pamięci" przy przejściu w dodawaniu x+y od bitu i do i+1 (algorytm pisemnego dodawania liczb binarnych).

Zauważmy, że:

${\displaystyle (x+y)_{0}=(x)_{0}+(y)_{0}-2r_{0}\;}$

${\displaystyle (x+y)_{1}=(x)_{1}+(y)_{1}+r_{0}-2r_{1}\;}$

Ogólnie, przyjmując ${\displaystyle r_{-1}=0\;}$:

${\displaystyle (x+y)_{i}=(x)_{i}+(y)_{i}+r_{i-1}-2r_{i}\;}$

${\displaystyle b(x+y)=\sum \limits _{i=0}^{N}(x+y)_{i}=\sum \limits _{i=0}^{N}(x)_{i}+\sum \limits _{i=0}^{N}(y)_{i}+\sum \limits _{i=0}^{N}r_{i}-2\sum \limits _{i=0}^{N}r_{i}}$${\displaystyle =b(x)+b(y)-\sum \limits _{i=0}^{N}r_{i}}$

gdzie ${\displaystyle N\geqslant \log _{2}(x+y)\;}$

W szczególności w odniesieniu do wzoru (8):

${\displaystyle b(n)=b(k)+b(n-k)-\sum \limits _{i=0}^{N}r_{i}}$

gdzie ${\displaystyle r_{i}}$ to przeniesienia przy dodawaniu liczb k i (n-k)

Symbol Newtona jest więc parzysty wtedy i tylko wtedy gdy

${\displaystyle \sum \limits _{i=0}^{N}r_{i}>0}$

czyli gdy istnieje takie j, że przy dodawaniu liczb k i (n-k): ${\displaystyle r_{i}=0\;}$ dla ${\displaystyle i<j\;}$ i ${\displaystyle r_{j}=1\;}$ co jest równoważne:

${\displaystyle r_{j}=1,r_{j-1}=0\;}$

co jest równoważne:

${\displaystyle (k)_{j}=1,(n-k)_{j}=1,r_{j-1}=0\;}$

co jest równoważne:

${\displaystyle (k)_{j}=1,(n)_{j}=(k)_{j}+(n-k)_{j}+r_{j-1}-2r_{j}=1+1+0-2=0\;}$

Czyli symbol Newtona ${\displaystyle n \choose k}$ jest parzysty wtedy i tylko wtedy, gdy istnieje taki bit, na którym n ma wartość 0, a k ma wartość 1.

Co należało udowodnić. Olaf @ 01:17, 22 maj 2008 (CEST)

zliczanie

w artykule znajduje się mnóstwo tożsamości, które mają swoją interpretację w zliczaniu obiektów. można by się nimi podeprzeć, aby dać ich łatwe dowody. konrad ^mów!

Liczby wielokątne

Dotyczy historycznej wersji artykułu.

W sekcji "związek z liczbami wielokątnymi" jest błąd. W n-tym wierszu ukośnym znajdują się nie liczby n-kątne, lecz liczby piramidalne (k-1) - wymiarowe utworzone na bazie liczb trójkątnych --Matematyk (dyskusja) 19:09, 1 cze 2009 (CEST)

n po 1

We właściwościach symbolu Newtona brakuje elementarnego wniosku, że n po 1 równe jest n (i ewentualnie n po n-1 = n). Myślę, że jest to warte odnotowania. --156.17.234.129 (dyskusja) 01:29, 12 maj 2012

Już jest --CiaPan (Odp.) 08:42, 15 maj 2012 (CEST)

Błędne określenie

Stwierdzenie jest to funkcja dwóch argumentów całkowitych nieujemnych, jest błędne, dlatego że argumenty n, k odnoszą się do mocy zbiorów, a moce zbiorów opisują liczby naturalne a nie całkowite. Owszem, można przyjąć "nieujemne całkowite" === "naturalne", ale wikipedię czytają ludzie nie będący dobrze rozeznani w teorii mnogości i po co sobie mają wyrabiać błędne pojęcie? -- anonimowy wpis umieścił 89.66.249.106 (dyskusja) (a podpis dodał CiaPan (dyskusja))

Określenie "liczby naturalne" jest nie do końca ścisłe, bo czasem zalicza się do nich zero, a czasem nie. Stąd użycie "nieujemnych całkowitych". Nie widzę tu błędu. Olaf @ 22:23, 20 maj 2021 (CEST)

A co jeśli n=k&nbsp;?

Zauważyłem ciekawe zjawisko, skoro w definicji jest zawarte, że

${\displaystyle {n \choose k}={\frac {n!}{k!(n-k)!}}}$    dla   ${\displaystyle 0\leqslant k\leqslant n,}$

To uprawnione jest takie przekształcenie:

${\displaystyle {\begin{aligned}{\binom {n}{k}}+{\binom {n}{k+1}}={\binom {n+1}{k+1}}\\[10pt]{\text{niech}}{\text{ }}{\text{ }}n=6\land k=6\\[10pt]{\text{wtedy}}\\[10pt]{\binom {6}{6}}+{\binom {6}{7}}={\binom {7}{7}}\\[10pt]1+{\binom {6}{7}}=1&{\bigg |}-1\\[10pt]{\binom {6}{7}}=0\end{aligned}}}$

Ponad to, jeśli mielibyśmy podłubać to dalej, to moglibyśmy uzyskać:

${\displaystyle {\begin{aligned}{\binom {6}{7}}=0\\[10pt]{\frac {6!}{(6-7)!\cdot 7!}}=0\\[10pt]{\frac {6!}{(-1)!\cdot (7\cdot 6!)}}=0\\[10pt]{\frac {\cancel {6!}}{(-1)!\cdot 7\cdot {\cancel {6!}}}}=0\\[10pt]{\frac {1}{(-1)!\cdot 7}}=0&{\bigg |}\cdot 7\\[10pt]{\frac {1}{(-1)!}}=0&{\bigg |}(...)^{-1}\\[10pt]{\frac {(-1)!}{1}}={\frac {1}{0}}\\[10pt](-1)!={\frac {1}{0}}\\[10pt](-1)!\in \{-\infty$ ;+\infty \}\end{aligned}}}

Czy takie wnioskowanie jest uprawnione?

Superjurek (dyskusja) 12:12, 20 maj 2021 (CEST)

Nie jest. Silnia nie jest określona dla liczb całkowitych ujemnych, właśnie dlatego że (n+1)! = (n+1) * n!, więc podstawiając n = -1 mielibyśmy 1 = 0 * (-1)! a żadna liczba tego nie spełnia. Wprowadzanie nieskończoności do rachunków nie ma sensu. Można rozszerzyć silnię na liczby zespolone (funkcja gamma), ale z wyjątkiem ujemnych liczb całkowitych. Olaf @ 22:21, 20 maj 2021 (CEST)

@Olaf Ale w tym przypadku, który przytoczyłeś, mamy do czynienia z symbolem nieoznaczonym, którym jest ${\displaystyle 0\cdot \infty }$ (taki zapis traci sens liczbowy). Gdybyśmy jednak postępowali tak jak przy wyznaczaniu granicy ciągu (gdzie np. ${\displaystyle x\rightarrow \infty }$) i uprzednio przekształcili wspomniane przez Ciebie równanie ${\displaystyle (n+1)!=(n+1)\cdot n!}$ dzieląc obie strony przez ${\displaystyle n!}$ (przed podstawieniem ${\displaystyle \infty }$), to doszlibyćmy do postaci ${\displaystyle {\frac {(n+1)!}{n!}}=(n+1)}$ (możemy tak zrobić, bo ${\displaystyle {\begin{aligned}\bigwedge \\n\in \mathbb {R} \end{aligned}}(n!\neq 0)}$), to wówczas po podstawieniu ${\displaystyle n=(-1)}$ dojdziemy do ${\displaystyle {\frac {0!}{(-1)!}}=0\Rightarrow {\frac {1}{(-1)!}}=0}$. Jeśli założymy, że ${\displaystyle (-1)!=+\infty }$ to otrzymamy ${\displaystyle {\frac {1}{\infty }}=0}$, czyli wszystko gra, bo podczas wyznaczania granicy ciągu, gdzie ${\displaystyle x\rightarrow \infty }$ wykonujemy dokładnie takie samo przekształcenie. Rozważyłbym jeszcze drugi przypadek, gdzie ${\displaystyle (-1)!=-\infty }$, wtedy ${\displaystyle {\frac {1}{-\infty }}=0}$, ale rysując komputerowo wykres funkcji ${\displaystyle \Gamma (n+1)}$ zauważamy, że zarówno dla ${\displaystyle n\rightarrow (-1)^{-}}$ i dla ${\displaystyle n\rightarrow (-1)^{+}}$ wyrażenie ${\displaystyle (n!)}$ przyjmuje wartość dodatnią (tym samym funkcja obustronnie dąży do ${\displaystyle +\infty }$, czyli dążąc idealnie do ${\displaystyle n=(-1)}$ dążymy do ${\displaystyle +\infty }$ i tym samym eliminujemy przypadek ${\displaystyle (-1)!=-\infty }$, więc pozostałaby tylko jedna możliwość, czyli ${\displaystyle (-1)!=+\infty }$. Czy w tej formie dalej to nie ma sensu? Superjurek (dyskusja) 10:27, 21 maj 2021 (CEST)

Sprostowanie, jednak nie dąży obustronnie do ${\displaystyle +\infty }$ więc nie można wykluczyć ${\displaystyle -\infty }$, tym samym ${\displaystyle (-1)!\in \{-\infty$ ;+\infty \}} Superjurek (dyskusja) 10:40, 21 maj 2021 (CEST)

Symbol Newtona jako działanie

Przy odpowiednich definicjach, obejmujących dół wyższy od góry (k>n), jest to funkcja dwóch zmiennych naturalnych o wartościach naturalnych, czyli działanie dwuargumentowe. Przydałoby się napisać, że jest nieprzemienne, czy jest łączne, skracalne, idempotentne, rozdzielne względem innych działań, czy jakieś jest rozdzielne względem niego itd. Chętnie bym zobaczył jakieś źródło, które o tym pisze, choć obawiam się, że może być o to trudno, bo takie fakty przeczące (negatywne) – jak brak pewnych własności – raczej się przemilcza. Mimo to warto o nich napisać ku przestrodze uczniom i studentom. Tarnoob (dyskusja) 22:12, 15 lip 2024 (CEST)