parzystość wyrazu w trójkącie Pascala
- faustus
- Użytkownik
- Posty: 90
- Rejestracja: 25 maja 2005, o 11:35
- Płeć: Mężczyzna
- Lokalizacja: z drzewa binarnego
- Podziękował: 3 razy
- Pomógł: 2 razy
parzystość wyrazu w trójkącie Pascala
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
- Użytkownik
- Posty: 1145
- Rejestracja: 27 kwie 2006, o 10:19
- Płeć: Mężczyzna
- Lokalizacja: z Konopii
- Podziękował: 4 razy
- Pomógł: 203 razy
parzystość wyrazu w trójkącie Pascala
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 ....
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
- Użytkownik
- Posty: 1174
- Rejestracja: 17 lut 2005, o 17:22
- Płeć: Mężczyzna
- Lokalizacja: Jaworzno
- Pomógł: 69 razy
parzystość wyrazu w trójkącie Pascala
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
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
parzystość wyrazu w trójkącie Pascala
DEXiu napisał:
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ł:
ps. temat jest super!
oj tak! co więcej: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),
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ł:
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ą....?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...)
ps. temat jest super!
- faustus
- Użytkownik
- Posty: 90
- Rejestracja: 25 maja 2005, o 11:35
- Płeć: Mężczyzna
- Lokalizacja: z drzewa binarnego
- Podziękował: 3 razy
- Pomógł: 2 razy
parzystość wyrazu w trójkącie Pascala
Chyba za dużo gram w piłkę ostatnio. Dlaczego akurat \(\displaystyle{ m-s_m}\) ???Sir George pisze: 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...)
Mogłbyś to pokazać na jakims konkretnym przykładzie, np. ... 36?
- Sir George
- Użytkownik
- Posty: 1145
- Rejestracja: 27 kwie 2006, o 10:19
- Płeć: Mężczyzna
- Lokalizacja: z Konopii
- Podziękował: 4 razy
- Pomógł: 203 razy
parzystość wyrazu w trójkącie Pascala
\(\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.mol_ksiazkowy pisze: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{ 36 \ = \ 100100_2}\)faustus pisze:Mogłbyś to pokazać na jakims konkretnym przykładzie, np. ... 36?
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ć...
Ostatnio zmieniony 19 lip 2006, o 11:58 przez Sir George, łącznie zmieniany 1 raz.
- faustus
- Użytkownik
- Posty: 90
- Rejestracja: 25 maja 2005, o 11:35
- Płeć: Mężczyzna
- Lokalizacja: z drzewa binarnego
- Podziękował: 3 razy
- Pomógł: 2 razy
parzystość wyrazu w trójkącie Pascala
To by bylo ciekawe.Sir George pisze: 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ć...
Skąd znasz taki fakt? Chyba go raczej nie wymyślilesz czytając mojego posta?
- Sir George
- Użytkownik
- Posty: 1145
- Rejestracja: 27 kwie 2006, o 10:19
- Płeć: Mężczyzna
- Lokalizacja: z Konopii
- Podziękował: 4 razy
- Pomógł: 203 razy
parzystość wyrazu w trójkącie Pascala
... chyba jednak tak... (we wcześniejszym poście wkradł się mały błąd, który już poprawiłem)...faustus pisze:Skąd znasz taki fakt? Chyba go raczej nie wymyślilesz czytając mojego posta?
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
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
parzystość wyrazu w trójkącie Pascala
Sir George, napisał:
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}\)
wszystkie te współczynniki Newtona będą nieparzyste, wtw, gdy ilorazy:napisane w nieskracalnej postaci będą miały ...nieparzyste liczniki i mianowniki.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}\) ?
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
- Użytkownik
- Posty: 1729
- Rejestracja: 9 sie 2004, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Koszalin
- Podziękował: 2 razy
- Pomógł: 12 razy
parzystość wyrazu w trójkącie Pascala
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}}\)
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}}\)
-
- Gość Specjalny
- Posty: 534
- Rejestracja: 8 lip 2004, o 17:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 17 razy
parzystość wyrazu w trójkącie Pascala
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}\)
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}\)