parzystość wyrazu w trójkącie Pascala

[faustus]

Chodzi mi z tyłu głowy cały czas taki problem: jak, znając n i k, powiedzieć czy \(\displaystyle{ {n\choose k}}\) jest parzyste czy nieparzyste? Wiem, że jak się zbuduje trójkąt Pascala i zaznaczy na nim liczby nieparzyste powstaje trójkąt Sierpińskiego, możnaby napisać taką funkcję rekurencyjną, która by to sprawdzała, ale chodzi mi o rozwiązanie w czasie stałym.

[Sir George]

Jak wiadomo \(\displaystyle{ {n \choose k} \ = \ \frac{n!}{\,k!\cdot(n-k)!\,}}\)

Aby stwierdzić, czy \(\displaystyle{ {n \choose k}}\) jest parzyste wystarczy wiedzieć, w jakiej potędze występuje 2 w rozkładzie na czynniki pierwsze liczby \(\displaystyle{ m!}\) (dla dowolnego \(\displaystyle{ m\,\in\,{\mathbb N}}\) )

Potęga ta jest równa dokładnie \(\displaystyle{ m-s_m}\), gdzie \(\displaystyle{ s_m}\) jest sumą cyfr liczby \(\displaystyle{ m}\) w zapisie dwójkowym (czyli na co samo wychodzi liczbą jedynek w zapisie dwójkowym...)

Teraz wystarczy sprawdzić, kiedy
\(\displaystyle{ n\,-\,s_n \ > \ \big(\,k\, -\, s_k\, \big) \ + \ \big(\,(n-k) \,- \, s_{(n-k)}\, \big)}\)

czyli kiedy

\(\displaystyle{ s_k \, + \, s_{(n-k)} \ > \ s_n}\)



.... a to już chyba nie jest takie trudne ....

[DEXiu]

Na pewno są parzyste wszystkie liczby \(\displaystyle{ {n}\choose{k}}\) w których \(\displaystyle{ n=2^{m},\,m\in\mathbb{N}_{+}\,\wedge\,k\notin\{0,n\}}\) (łatwo to wykazać - na tegorocznym OMie w pierwszym etapie jedno z zadań przechodziło z tego lematu), ale to tylko część parzystych symboli Newtona. Jaki jest warunek dla pozostałych - nie mam pojęcia

[mol_ksiazkowy]

DEXiu napisał:

Na pewno są parzyste wszystkie liczby \(\displaystyle{ {n}\choose{k}}\) w których \(\displaystyle{ n=2^{m},\,m\in\mathbb{N}_{+}\,\wedge\,k\notin\{0,n\}}\) (łatwo to wykazać - na tegorocznym OMie w pierwszym etapie jedno z zadań przechodziło z tego lematu),

oj tak! co więcej:
Liczba nieparzystych elementów \(\displaystyle{ n}\) tego wiersza trójkąta Pascala jest postaci \(\displaystyle{ 2^{m}}\), gdzie \(\displaystyle{ m}\) jest liczbą jedynek w dwójkowym zapisie liczby \(\displaystyle{ n}\)...

Sir George napisał:

Aby stwierdzić, czy \(\displaystyle{ {n \choose k}}\) jest parzyste wystarczy wiedzieć, w jakiej potędze występuje 2 w rozkładzie na czynniki pierwsze liczby \(\displaystyle{ m!}\) (dla dowolnego \(\displaystyle{ m\,\in\,{\mathbb N}}\) )

Potęga ta jest równa dokładnie \(\displaystyle{ m-s_m}\), gdzie \(\displaystyle{ s_m}\) jest sumą cyfr liczby \(\displaystyle{ m}\) w zapisie dwójkowym (czyli na co samo wychodzi liczbą jedynek w zapisie dwójkowym...)

oj, a czy mógłyś wyjaśnić na konkrtenym przykładzie, np. \(\displaystyle{ n=45}\).... powinno być 16 elementów nieparzystych....które to będą....?

ps. temat jest super!

[faustus]

Potęga ta jest równa dokładnie \(\displaystyle{ m-s_m}\), gdzie \(\displaystyle{ s_m}\) jest sumą cyfr liczby \(\displaystyle{ m}\) w zapisie dwójkowym (czyli na co samo wychodzi liczbą jedynek w zapisie dwójkowym...)

Chyba za dużo gram w piłkę ostatnio. Dlaczego akurat \(\displaystyle{ m-s_m}\) ???
Mogłbyś to pokazać na jakims konkretnym przykładzie, np. ... 36?

[Sir George]

a czy mógłyś wyjaśnić na konkrtenym przykładzie, np. \(\displaystyle{ n=45}\) .... powinno być 16 elementów nieparzystych....które to będą....?

\(\displaystyle{ 45 \ = \ 101101_2}\) Nieparzyste wartości dwumianu są dla: 0, 1, 4, 5, 8, 9, 12, 13, 32, 33, 36, 37, 40, 41, 44, 45.

Mogłbyś to pokazać na jakims konkretnym przykładzie, np. ... 36?

\(\displaystyle{ 36 \ = \ 100100_2}\)
Stąd w rozkładzie 36! na czynniki pierwsze 2 występuje w potędze 34.
A dlaczego? Wśród 36 czynników w 36! 18 jest podzielnych przez 2. Wśród nich 9 jest podzielnych przez 4, 4 - przez 8, 2 - przez 16 i 1- przez 1. W sumie zatem jest 18+9+4+2+1=34 dwójek...


Prawdziwy jest ogólniejszy fakt: jeśli \(\displaystyle{ m_p}\) oznacza sumę cyfr liczby \(\displaystyle{ m}\) przedstawionej w systemie o podstawie \(\displaystyle{ p}\) będącej liczbą pierwszą.
Wówczas w rozkładzie \(\displaystyle{ m!}\) na czynniki pierwsze \(\displaystyle{ p}\) występuje w potędze \(\displaystyle{ \frac{m-m_p}{p-1}}\).

Dowód nie jest trudny, ale cokolwiek żmudny.

Jak znajdę chwilkę, to spróbuję go spisać...

[faustus]

Prawdziwy jest ogólniejszy fakt: jeśli \(\displaystyle{ m_p}\) oznacza sumę cyfr liczby \(\displaystyle{ m}\) przedstawionej w systemie o podstawie \(\displaystyle{ p}\) będącej liczbą pierwszą.
Wówczas w rozkładzie \(\displaystyle{ m!}\) na czynniki pierwsze \(\displaystyle{ p}\) występuje w potędze \(\displaystyle{ m-m_p}\).

Dowód nie jest trudny, ale cokolwiek żmudny.

Jak znajdę chwilkę, to spróbuję go spisać...

To by bylo ciekawe.
Skąd znasz taki fakt? Chyba go raczej nie wymyślilesz czytając mojego posta?

[Sir George]

Skąd znasz taki fakt? Chyba go raczej nie wymyślilesz czytając mojego posta?

... chyba jednak tak... (we wcześniejszym poście wkradł się mały błąd, który już poprawiłem)...

A oto dowód:

1. Zastosujmy dzielenie m z resztą przez p:
\(\displaystyle{ m \ = \ m_1 p\, + \, r_0}\),

\(\displaystyle{ m_1 \ = \ m_2 p\, + \, r_1}\),

\(\displaystyle{ \quad \ \vdots}\)

\(\displaystyle{ m_k \ = \ 0 p\, + \, r_k}\),


gdzie \(\displaystyle{ 0\le r_i0}\) dla \(\displaystyle{ i=0,...,k}\) oraz \(\displaystyle{ r_k>0}\).


Wówczas m ma w systemie przy podstawie p postać: \(\displaystyle{ m \ = \ (\overline{r_k...r_1r_0})_p}\)



2. Wśród liczb od 1 do m liczb podzielnych przez \(\displaystyle{ p}\) jest \(\displaystyle{ m_1}\),
przez \(\displaystyle{ p^2}\) - \(\displaystyle{ m_2}\), itd...

Zatem w rozkładzie \(\displaystyle{ m!}\) na czynniki pierwsze \(\displaystyle{ p}\) występuje dokładnie \(\displaystyle{ m_1+m_2+...+m_k}\) razy.



3. Policzmy teraz:
\(\displaystyle{ m\,-\,(r_0+r_1+...+r_k) \ =}\)

\(\displaystyle{ \qquad \ = \ m-r_0 \, - \,(r_1+...+r_k)}\)

\(\displaystyle{ \qquad \ = \ m_1 p \, - \,(r_1+...+r_k)}\)

\(\displaystyle{ \qquad \ = \ m_1 (p-1) \, + \, m_1-r_1\, - \,(r_2+...+r_k)}\)

\(\displaystyle{ \qquad\qquad\vdots}\)

\(\displaystyle{ \qquad \ = \ (m_1+m_2+...+m_k)(p-1)}\)



4. Jeśli oznaczymy przez \(\displaystyle{ m_p \ := \ r_0+r_1+...+r_k}\), czyli sumę cyfr m w systemie o podstawie p, to otrzymujemy, że p występuje w rozkładzie m! na czynniki pierwsze w potędze
\(\displaystyle{ \frac{1}{p-1}(m-m_p)}\).



[ Dodano: 19 Lipiec 2006, 14:16 ]
Zatem, jak już łatwo sprawdzić, w rozkładzie \(\displaystyle{ n \choose k}\) na czynniki pierwsze liczba \(\displaystyle{ p}\) występuje dokładnie \(\displaystyle{ \frac{1}{p-1}(k_p+(n-k)_p-n_p)}\) razy...

[ Dodano: 19 Lipiec 2006, 14:20 ]
Przychodzą mi do głowy w związku z tym dwa nowe zadanka:

1. Dla jakich \(\displaystyle{ n}\) wartości \(\displaystyle{ n \choose k}\) są nieparzyste dla wszystkich \(\displaystyle{ k \, = \, 0,1,...,n}\) ?

2. Ile zer ma na końcu liczba \(\displaystyle{ n\choose k}\) ?

[mol_ksiazkowy]

Sir George, napisał:

Przychodzą mi do głowy w związku z tym dwa nowe zadanka:

1. Dla jakich \(\displaystyle{ n}\) wartości \(\displaystyle{ n \choose k}\) są nieparzyste dla wszystkich \(\displaystyle{ k \, = \, 0,1,...,n}\) ?

wszystkie te współczynniki Newtona będą nieparzyste, wtw, gdy ilorazy:napisane w nieskracalnej postaci będą miały ...nieparzyste liczniki i mianowniki.
tj.:
\(\displaystyle{ \frac{n \choose k+1}{n \choose k}}\),

tj.:
\(\displaystyle{ \frac{n}{1}, \frac{n-1}{2},...., \frac{n-k}{k+1},....\frac{1}{n},}\):
\(\displaystyle{ n={2}^m-1}\) .mamy... \(\displaystyle{ n={n \choose 1}}\) jest nieparzyste. tj: \(\displaystyle{ n=p{2}^m-1}\) p jest nieparzyste. Wtedy przy \(\displaystyle{ k={2}^m-1}\): \(\displaystyle{ \frac{n-({2}^m-1)}{{2}^m}=\frac{n-({2}^m-1)}{{2}^m}=p-1}\) To jest liczba parzysta, o ile tylko ...\(\displaystyle{ p>1}\)....tj. pewne \(\displaystyle{ n={n \choose k}}\) jest parzyste.

Gdy \(\displaystyle{ p=1}\), to tego współczynnika (ilorazu)nie ma!Odwrotnie:Jeśli: \(\displaystyle{ n={2}^m-1}\), \(\displaystyle{ k+1=r{2}^q}\), to: \(\displaystyle{ \frac{n -k}{k+1}=\frac{{2}^{m-q}-r}{r}}\),
cbdo.

Podam tu też taki problem:
W \(\displaystyle{ n}\)tym wierszy trójkąta Pascala jest \(\displaystyle{ P_{n}}\) liczb parzystych i \(\displaystyle{ N_{n}}\)liczb nieparzystych. Zbadać kiedy zachodzą:
1. \(\displaystyle{ P_{n}=N_{n}}\)
2. \(\displaystyle{ P_{n}=N_{n}+1}\)
3. \(\displaystyle{ P_{n}=N_{n}-1}\)

Utwórzymy trójkąt \(\displaystyle{ T'}\), t że jest to trójkąt Pacala modulo 2, tj. zera i jedynki są na tych pozycjach, gdzie w zwykłym trójkacie Pascala są odpowiednio: liczby parzyste i nieparzyste...
Jak już wiemy, w każdy wierszu, którego numer jest potęgą dwójki, wszystkie wyrazy-prócz dwóch skrajnych jedynek - są zerami.
Ustalmy \(\displaystyle{ n}\) i niech \(\displaystyle{ T}\) oznacza to część trójkąta utworzona przez wiersze o numerach od 0 do \(\displaystyle{ 2^{m}-1}\). Wtedy w wierszach od \(\displaystyle{ 2^{m}}\)do \(\displaystyle{ 2^{m+1}-1}\)tworzą się dwa rozłączne trójkąty, identyczne z \(\displaystyle{ T}\). Trójkąty te oddzielone są blokiem złożonym z samych zer. Zatem liczba jedynek w każdym wierszu, którego numer nie jest postaci \(\displaystyle{ 2^{m}}\)jest równa podwojonej liczbie jedynek w wierszu wczesniejszym. Stąd indukcyjnie: liczba jedynek w każdym wierszu \(\displaystyle{ N_{n}}\) jest potęgą dwójki.
Jeśli więc \(\displaystyle{ P_{n}-N_{n}}\) jest równe 1 lub -1, lub 0, ... to \(\displaystyle{ n=P_{n}+N_{n}-1=2N_{n}+P_{n}-N_{n}-1}\) jest postaci: \(\displaystyle{ 2^{k}}\) lub \(\displaystyle{ 2^{k}-1}\) lub \(\displaystyle{ 2^{k}-2}\). Wtedy też n-ty wiersz ma postać:1000....0001, 1111....1111, 101010....101, tj odp.:

1. to jest niemożliwe
2. \(\displaystyle{ n=4}\)
3. \(\displaystyle{ n=2^{k}-2}\)

[Arek]

Co do zadania na początku tematu, polecam lekturę:

1. Tw. Kummera (1852)



2. Tw. Lucasa (1878)



Tradycyjnie sporo informacji jest też na MathWorld:

http://mathworld.wolfram.com/BinomialCoefficient.html


A oto ciekawe zadanie co do samej podzielności przez 2:

[url=http://130.44.194.100/mcom/1998-67-224/S0025-5718-98-01002-3/S0025-5718-98-01002-3.pdf] INFINITE FAMILIES OF SOLUTIONS OF THE EQUATION [/url] \(\displaystyle{ {n \choose k} = 2 { a \choose b}}\)

[półpasiec]

na pytanie dla jakiego n wszystkie dwumiany sa nieparzyste mozna odpowiedziec tak
skoro wiersz ma miec same jedynki to wiersz ponizej musi miec same 0, a to sie dzieje dla n ktore jest potega 2 wiec \(\displaystyle{ n=2^m-1}\)