symbol newtona a parzystosc

[kawaii]

Czy jest jakis sposob, bez obliczania wartosci symbolu newtona, aby sprawdzic czy daje on liczbe parzysta czy nieparzysta?

[yorgin]

Hm wydaje mi się że prostego sposobu nie ma by to stwierdzić. Dla dowolnych n i k nie ustali się tak łatwo parzystości \(\displaystyle{ {n\choose k}}\)
Można np analizować trójkąt pascala i rozkład liczb parzystych wśród nieparzystych czy np rysując trójkąt ale wpisując w miejsca liczb reszty z dzielenia przez 2 można coś zauważyć ciekawego odnośnie tego ale ja nic nie zauważyłem.
(Tak na marginesie usuwając z trójkąta pascala liczby parzyste otrzymamy trójkąt Sierpińskiego)

[max]

Mamy:
\(\displaystyle{ {n\choose k} = \frac{n!}{k!(n - k)!}}\)

Niech:
\(\displaystyle{ n! = 2^{p}\cdot s,\\
k! = 2^{q}\cdot t,\\
(n - k)! = 2^{r} \cdot u}\)
Przy czym:
\(\displaystyle{ s, t, u \in \mathbb{N},\\
p, q, r \in \mathbb{N} \cup \{0\},\\
\tfrac{s}{2}, \tfrac{t}{2}, \tfrac{u}{2} \notin \mathbb{N}}\)

Wtedy:
\(\displaystyle{ p \geqslant q + r}\)

oraz:
\(\displaystyle{ p = \sum\limits_{h = 1}^{\lfloor\log_{2} n\rfloor} \left\lfloor\frac{n}{2^{h}}\right\rfloor\\
q = \sum\limits_{i = 1}^{\lfloor\log_{2} k\rfloor} \left\lfloor\frac{k}{2^{i}}\right\rfloor\\
r = \sum\limits_{j = 1}^{\lfloor\log_{2} (n - k)\rfloor}\left\lfloor\frac{n-k}{2^{j}}\right\rfloor}\)

A zatem
\(\displaystyle{ \frac{1}{2}\cdot {n\choose k} \in \mathbb{N} \iff p \neq q + r\\
\frac{1}{2}\cdot {n\choose k} \in \mathbb{N} \iff \sum\limits_{h = 1}^{\lfloor\log_{2} n\rfloor} \left\lfloor\frac{n}{2^{h}}\right\rfloor \neq \sum\limits_{i = 1}^{\lfloor\log_{2} k\rfloor} \left\lfloor\frac{k}{2^{i}}\right\rfloor + \sum\limits_{j = 1}^{\lfloor\log_{2} (n - k)\rfloor}\left\lfloor\frac{n-k}{2^{j}}\right\rfloor}\)

Takie dosyć brutalne, ale dla dużych \(\displaystyle{ n}\) zdecydownanie szybsze niż trójkąt Pascala