Parzystość symbolu Newtona

Ziemniak1990 · Post autor: **Ziemniak1990** » 4 cze 2009, o 15:28

Wiem, że podobny temat gdzieś tu był na forum, ale nie mogę go odnaleźć ponownie więc pytam.

Jak sprawdzić, czy \(\displaystyle{ {n \choose k}\) jest parzysty?

Podobno istnieje jakieś twierdzenie, ale jaką nosi nazwę?

abc666 · Post autor: **abc666** » 4 cze 2009, o 16:12

Trzeba policzyć ile dwójek w rozkładzie na czynniki pierwsze ma symbol. Jeśli nie ma żadnej to jest nieparzysty. Np mamy
\(\displaystyle{ {23 \choose 7} = \frac{23!}{7! \cdot 16!}}\)

Oznaczmy przez \(\displaystyle{ f(n)}\) liczbę dwójek w rozkładzie liczby \(\displaystyle{ n!}\) wtedy
\(\displaystyle{ f(23)=19 \\
f(7)=4\\
f(16)=15}\)

mamy więc
\(\displaystyle{ 19=4+15}\)
więc nasz symbol jest nieparzysty, wszystkie dwójki się skracają

Jak obliczać liczbę tych dwójek można przeczytać w temacie viewtopic.php?f=41&t=129700

Ziemniak1990 · Post autor: **Ziemniak1990** » 4 cze 2009, o 20:51

Gdyby to bylo takie proste to bym nie pytal. To jest zbyt malo optymalne dla wysokich liczb. jesli stworzysz algorytm szybkiego liczenia dwojek dla N=1000000000 i K = 500000000 to ok.

Podobno jest twierdzenie mowiace o podzielnosci przez dwa, symbolu newtona

abc666 · Post autor: **abc666** » 4 cze 2009, o 21:01

Przecież przy tym algorytmie liczby które podałeś są raczej małe

\(\displaystyle{ 1000000000< 2^{30}}\)
Wystarczy wykonać więc 29 razy dzielenie. Wystarczy do tego kalkulator prosty (tylko żeby miał odpowiednią liczbę miejsc na wyświetlaczu) i jakieś 3 minuty.

Skoro uważasz to za niepraktyczne to powiedz do czego ci to jest potrzebne?

Ziemniak1990 · Post autor: **Ziemniak1990** » 5 cze 2009, o 13:26

Nie no przepraszam, nie przyjrzałem się dokładnie i pomyślałem że mam rozkładać na czynniki każdą z liczb należących do silni, dlatego, że sam na początku próbowałem w ten sposób liczyć te dwójki, a tu wygląda, że ten algorytm jest dość szybki.

Sage! · Post autor: **Sage!** » 8 cze 2009, o 23:54

Najłatwiej to zrobić przy użyciu programowania liniowego tzn. przez wzór rekurencyjny \(\displaystyle{ {n \choose k }= {n-1 \choose k} + {n-1 \choose k-1}}\) gdzie pamiętamy tylko reszty dzielenia przez \(\displaystyle{ 2}\). Możemy zapamiętywać je w tablicy dwuwymiarowej przykładowo.

Jeżeli \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\) różnymi kolorami to zobaczysz dywan Sierpińskiego.