Mam ciąg specyficznie tworzony np:
\(\displaystyle{ x_{5}=(1,1,0,0,1)}\)
\(\displaystyle{ s(x_{5})=-1}\)
\(\displaystyle{ x_{11}=(1,1,0,0,1,1,0,0,1,1,1)}\)
\(\displaystyle{ s(x_{11})=-1 \cdot -1 \cdot -1 \cdot -1}\)
już widać jak to tworzymy, a więc:
Dany jest ciąg składający się z zer i jedynek o długości \(\displaystyle{ n}\),
I teraz jeśli dwie jedynki sąsiadują ze sobą to mnożymy \(\displaystyle{ -1}\), tyle razy ile jest jedynek sąsiadów.
I pytanie jest takie:
Ile razy w ciągu o długości \(\displaystyle{ n}\), wynik funkcji \(\displaystyle{ s}\), wyjdzie ujemny lub jak kto woli dodatni!
Wydaje mi się że trzeba to ruszyć rekurencją problem nie jest taki banalny!
W przypadku , gdy nie ma jedynek sąsiadów sąsiadów s przyjmuje jeden np:
\(\displaystyle{ x=(1,0,1)}\)
lub:
\(\displaystyle{ x=(0,0,0)}\)
Liczba elementów ciągu zerojedynkowego
-
krzeslo789
- Użytkownik
- Posty: 34
- Rejestracja: 14 sty 2013, o 14:22
- Płeć: Mężczyzna
- Lokalizacja: dom
- Podziękował: 3 razy
- Pomógł: 5 razy
Liczba elementów ciągu zerojedynkowego
Ostatnio zmieniony 19 sty 2013, o 23:44 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Elementy da się policzyć, więc liczba, a nie ilość.
Powód: Elementy da się policzyć, więc liczba, a nie ilość.
-
abc666
Liczba elementów ciągu zerojedynkowego
Podziel sobie na ciągi dla których \(\displaystyle{ s}\) będzie \(\displaystyle{ 1}\) i \(\displaystyle{ -1}\) oraz dodatkowo na takie które kończą się na \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\). Wtedy wyjdą ci bardzo łatwe równanka.
-
krzeslo789
- Użytkownik
- Posty: 34
- Rejestracja: 14 sty 2013, o 14:22
- Płeć: Mężczyzna
- Lokalizacja: dom
- Podziękował: 3 razy
- Pomógł: 5 razy
Liczba elementów ciągu zerojedynkowego
tak ale jeszcze tej łatwości nie odkryłem
Zdaje się że coś takiego wychodzi ale może się mylę:
\(\displaystyle{ x_{2n+1}=(-1)^{n}x_{2n}}\)
dla tych co kończą się na jeden, oraz:
\(\displaystyle{ x_{2n}=-x_{n}}\)
dla tych co w końcówce mają zero
To tak metodą obserwacji
bo można je binarnie przedstawić w rozpisce zerojedynkowej i te z zerem na końcu będą parzyste a te z jedynką nieparzyste.
-- 20 sty 2013, o 00:50 --
Zastanawia mnie jedna rzecz czy można te wzory przerobić na postać jawną?
Zdaje się że coś takiego wychodzi ale może się mylę:
\(\displaystyle{ x_{2n+1}=(-1)^{n}x_{2n}}\)
dla tych co kończą się na jeden, oraz:
\(\displaystyle{ x_{2n}=-x_{n}}\)
dla tych co w końcówce mają zero
To tak metodą obserwacji
bo można je binarnie przedstawić w rozpisce zerojedynkowej i te z zerem na końcu będą parzyste a te z jedynką nieparzyste.
-- 20 sty 2013, o 00:50 --
Zastanawia mnie jedna rzecz czy można te wzory przerobić na postać jawną?
-
abc666
Liczba elementów ciągu zerojedynkowego
Chodzi mi o coś innego. Mianowicie o liczbę tych ciągów, ale teraz próbowałem to policzyć i wychodzi straszny "syf". Chwilowo nie mam pomysłu innego, ale rozpatrzenie oddzielnie parzystych i nieparzystych \(\displaystyle{ n}\) może do czegoś doprowadzić.
-
krzeslo789
- Użytkownik
- Posty: 34
- Rejestracja: 14 sty 2013, o 14:22
- Płeć: Mężczyzna
- Lokalizacja: dom
- Podziękował: 3 razy
- Pomógł: 5 razy
Liczba elementów ciągu zerojedynkowego
No a jakby te moje wynalazki zsumował
\(\displaystyle{ \sum_{}^{} x_{i}}\)
To może by było to .
A tak swoją drogą to ten cały "syf" co piszesz to może być nawet coś ciekawego możesz wrzucić.
\(\displaystyle{ \sum_{}^{} x_{i}}\)
To może by było to .
A tak swoją drogą to ten cały "syf" co piszesz to może być nawet coś ciekawego możesz wrzucić.
-
abc666
Liczba elementów ciągu zerojedynkowego
Po rozpatrzeniu parzystych:
Przez \(\displaystyle{ a_{n}}\) będę oznaczał liczbę ciągów, dla których \(\displaystyle{ s=1}\) oraz kończą się jedynką.
Przez \(\displaystyle{ b_{n}}\) liczbę ciągów, dla których \(\displaystyle{ s=1}\) oraz kończą się zerem.
Analogicznie \(\displaystyle{ c_{n}}\) i \(\displaystyle{ d_{n}}\) dla \(\displaystyle{ s=-1}\)
Teraz będziemy rozpatrywać tylko ciągi o parzystej długości. Możemy zapisać
\(\displaystyle{ a_{2n}=2a_{2n-2}+b_{2n-2}+d_{2n-2}\\
b_{2n}=a_{2n-2}+2b_{2n-2}+c_{2n-2}}\)
Chcemy obliczyć \(\displaystyle{ a_{2n}+b_{2n}}\) więc sumujemy stronami
\(\displaystyle{ a_{2n}+b_{2n}=3a_{2n-2}+3b_{2n-2}+c_{2n-2}+d_{2n-2}}\)
wiemy też, że \(\displaystyle{ a_{n}+b_{n}+c_{n}+d_{n}=2^{n}}\) czyli \(\displaystyle{ c_{2n-2}+d_{2n-2}=2^{2n-2}-(a_{2n-2}+b_{2n-2})}\) skąd
\(\displaystyle{ a_{2n}+b_{2n}=3a_{2n-2}+3b_{2n-2}+2^{2n-2}-(a_{2n-2}+b_{2n-2})\\
a_{2n}+b_{2n}=2a_{2n-2}+2b_{2n-2}+2^{2n-2}}\)
Teraz oznaczmy \(\displaystyle{ x_{2n}=a_{2n}+b_{2n}}\) skąd dostajemy
\(\displaystyle{ x_{2n}=x_{2(n-1)}+2^{2(n-1)}}\)
oraz \(\displaystyle{ x_{2}=3}\)
Dobrze by było jak ktoś by spojrzał czy nie ma jakiś kompletnych głupot po drodze. Generalnie powinno wyjść mniej więcej \(\displaystyle{ 2^{k-2} + 2^{\lfloor \frac{k}{2}\rfloor -1}}\)
Przez \(\displaystyle{ a_{n}}\) będę oznaczał liczbę ciągów, dla których \(\displaystyle{ s=1}\) oraz kończą się jedynką.
Przez \(\displaystyle{ b_{n}}\) liczbę ciągów, dla których \(\displaystyle{ s=1}\) oraz kończą się zerem.
Analogicznie \(\displaystyle{ c_{n}}\) i \(\displaystyle{ d_{n}}\) dla \(\displaystyle{ s=-1}\)
Teraz będziemy rozpatrywać tylko ciągi o parzystej długości. Możemy zapisać
\(\displaystyle{ a_{2n}=2a_{2n-2}+b_{2n-2}+d_{2n-2}\\
b_{2n}=a_{2n-2}+2b_{2n-2}+c_{2n-2}}\)
Chcemy obliczyć \(\displaystyle{ a_{2n}+b_{2n}}\) więc sumujemy stronami
\(\displaystyle{ a_{2n}+b_{2n}=3a_{2n-2}+3b_{2n-2}+c_{2n-2}+d_{2n-2}}\)
wiemy też, że \(\displaystyle{ a_{n}+b_{n}+c_{n}+d_{n}=2^{n}}\) czyli \(\displaystyle{ c_{2n-2}+d_{2n-2}=2^{2n-2}-(a_{2n-2}+b_{2n-2})}\) skąd
\(\displaystyle{ a_{2n}+b_{2n}=3a_{2n-2}+3b_{2n-2}+2^{2n-2}-(a_{2n-2}+b_{2n-2})\\
a_{2n}+b_{2n}=2a_{2n-2}+2b_{2n-2}+2^{2n-2}}\)
Teraz oznaczmy \(\displaystyle{ x_{2n}=a_{2n}+b_{2n}}\) skąd dostajemy
\(\displaystyle{ x_{2n}=x_{2(n-1)}+2^{2(n-1)}}\)
oraz \(\displaystyle{ x_{2}=3}\)
Dobrze by było jak ktoś by spojrzał czy nie ma jakiś kompletnych głupot po drodze. Generalnie powinno wyjść mniej więcej \(\displaystyle{ 2^{k-2} + 2^{\lfloor \frac{k}{2}\rfloor -1}}\)
-
krzeslo789
- Użytkownik
- Posty: 34
- Rejestracja: 14 sty 2013, o 14:22
- Płeć: Mężczyzna
- Lokalizacja: dom
- Podziękował: 3 razy
- Pomógł: 5 razy
Liczba elementów ciągu zerojedynkowego
Wygląda dosyć fajnie
Czyli podobnie by było dla nieparzystych?
tylko coś mi tu nie trybi dla \(\displaystyle{ n=2}\)
bo wtedy:
\(\displaystyle{ x_{4}=x_{2}+2^{2}=3+4=7}\)
a zliczając na piechotę iloczynów z wynikiem \(\displaystyle{ 1}\) będzie \(\displaystyle{ 10}\)
a iloczynów z wynikiem \(\displaystyle{ -1}\) będzie \(\displaystyle{ 6}\)
oczywiście \(\displaystyle{ x_{2}=3}\)
Jakiś drobny błąd chyba jest w pierwszych wzorach na \(\displaystyle{ a_{2n} i b_{2n}}\) wszystko wydaje się mieć ręce i nogi
-- 24 sty 2013, o 21:53 --
Mam coś takiego:
Tak zdefiniowane ciągi:
\(\displaystyle{ A_{n}}\)- ilość ciągów z wynikiem \(\displaystyle{ s=-1}\) , które posiadają jedynkę na pierwszym miejscu (o długości n) np:
\(\displaystyle{ (1,0,1,1)}\)
\(\displaystyle{ B_{n}}\)- ilość ciągów z wynikiem \(\displaystyle{ s=1}\) , które posiadają jedynkę na pierwszym miejscu (o długości n) np:
\(\displaystyle{ (1,0,0,1)}\)
\(\displaystyle{ a_{n}}\)- ilość ciągów z wynikiem \(\displaystyle{ s=-1}\) (o długości n) dowolnych np:
\(\displaystyle{ (0,0,1,1)}\)
\(\displaystyle{ b_{n}}\)- ilość ciągów z wynikiem \(\displaystyle{ s= 1}\) (o długości n) dowolnych np:
\(\displaystyle{ (0,0,1,1,1)}\)
jeśli weźmiemy teraz ciągi z jedynką na pierwszym miejscu, oraz z jedynką na drugim miejscu
\(\displaystyle{ (1,1,U)}\) ,U- coś tam
oraz ciągi typu:
\(\displaystyle{ (1,0,U)}\) ,U- coś tam
można się temu przypatrzeć i wywnioskować, że:
\(\displaystyle{ A_{n+2}=B_{n+1}+a_{n}}\)
\(\displaystyle{ a_{1}=0, B_{2}=1}\)
ale:
\(\displaystyle{ A_{n+1}+B_{n+1}=2^{n}}\)
czyli:
\(\displaystyle{ B_{n+1}=2^{n}-B_{n+1}}\)
po podstawieniu mamy:
\(\displaystyle{ A_{n+2}=2^{n}-A_{n+1}+a_{n}}\)
można jeszcze zaobserwować, że:
\(\displaystyle{ a_{n+1}=A_{n+1}+a_{n}}\)
gdzie:
\(\displaystyle{ a_{1}=0, A_{2}=1}\)
Teraz pytanie czy można to przerobić na postać jawną?
Ten układ równań rekurencyjnych:
\(\displaystyle{ a_{1}=0, A_{2}=1}\)
\(\displaystyle{ A_{n+2}=2^{n}-A_{n+1}+a_{n}}\)
\(\displaystyle{ a_{n+1}=A_{n+1}+a_{n}}\)
-- 24 sty 2013, o 22:00 --
Sprawdzałem to dla kilku przypadków i hula
-- 24 sty 2013, o 23:47 --
Otóż można:
z drugiego liczymy \(\displaystyle{ A_{n+1}=a_{n+1}-a_{n}}\)
i podstawiamy do pierwszego:
\(\displaystyle{ A_{n+2}=a_{n+2}-a_{n+1}}\)
i do pierwszego podstawimy i mamy:
\(\displaystyle{ a_{n+1}=2^{n-1}+2a_{n-1}}\)
lub:
\(\displaystyle{ a_{n+2}=2a_{n}+2^{n}}\)
-- 25 sty 2013, o 01:45 --
wzór jawny na \(\displaystyle{ a_{n}}\)
\(\displaystyle{ a_{n}= \frac{1}{4}[( \sqrt{2}-1 )(-1)^{n}- \sqrt{2}-1 ]2^{ \frac{1}{2}n }+2^{n-1}}\)-- 25 sty 2013, o 17:50 --Teraz wzór jawny na: \(\displaystyle{ A_{n}}\)
\(\displaystyle{ A_{n+1}=- \frac{1}{4}2^{ \frac{1}{2}n }[(-1)^{n}+1] +2^{n-1}}\)
Czyli podobnie by było dla nieparzystych?
tylko coś mi tu nie trybi dla \(\displaystyle{ n=2}\)
bo wtedy:
\(\displaystyle{ x_{4}=x_{2}+2^{2}=3+4=7}\)
a zliczając na piechotę iloczynów z wynikiem \(\displaystyle{ 1}\) będzie \(\displaystyle{ 10}\)
a iloczynów z wynikiem \(\displaystyle{ -1}\) będzie \(\displaystyle{ 6}\)
oczywiście \(\displaystyle{ x_{2}=3}\)
Jakiś drobny błąd chyba jest w pierwszych wzorach na \(\displaystyle{ a_{2n} i b_{2n}}\) wszystko wydaje się mieć ręce i nogi
-- 24 sty 2013, o 21:53 --
Mam coś takiego:
Tak zdefiniowane ciągi:
\(\displaystyle{ A_{n}}\)- ilość ciągów z wynikiem \(\displaystyle{ s=-1}\) , które posiadają jedynkę na pierwszym miejscu (o długości n) np:
\(\displaystyle{ (1,0,1,1)}\)
\(\displaystyle{ B_{n}}\)- ilość ciągów z wynikiem \(\displaystyle{ s=1}\) , które posiadają jedynkę na pierwszym miejscu (o długości n) np:
\(\displaystyle{ (1,0,0,1)}\)
\(\displaystyle{ a_{n}}\)- ilość ciągów z wynikiem \(\displaystyle{ s=-1}\) (o długości n) dowolnych np:
\(\displaystyle{ (0,0,1,1)}\)
\(\displaystyle{ b_{n}}\)- ilość ciągów z wynikiem \(\displaystyle{ s= 1}\) (o długości n) dowolnych np:
\(\displaystyle{ (0,0,1,1,1)}\)
jeśli weźmiemy teraz ciągi z jedynką na pierwszym miejscu, oraz z jedynką na drugim miejscu
\(\displaystyle{ (1,1,U)}\) ,U- coś tam
oraz ciągi typu:
\(\displaystyle{ (1,0,U)}\) ,U- coś tam
można się temu przypatrzeć i wywnioskować, że:
\(\displaystyle{ A_{n+2}=B_{n+1}+a_{n}}\)
\(\displaystyle{ a_{1}=0, B_{2}=1}\)
ale:
\(\displaystyle{ A_{n+1}+B_{n+1}=2^{n}}\)
czyli:
\(\displaystyle{ B_{n+1}=2^{n}-B_{n+1}}\)
po podstawieniu mamy:
\(\displaystyle{ A_{n+2}=2^{n}-A_{n+1}+a_{n}}\)
można jeszcze zaobserwować, że:
\(\displaystyle{ a_{n+1}=A_{n+1}+a_{n}}\)
gdzie:
\(\displaystyle{ a_{1}=0, A_{2}=1}\)
Teraz pytanie czy można to przerobić na postać jawną?
Ten układ równań rekurencyjnych:
\(\displaystyle{ a_{1}=0, A_{2}=1}\)
\(\displaystyle{ A_{n+2}=2^{n}-A_{n+1}+a_{n}}\)
\(\displaystyle{ a_{n+1}=A_{n+1}+a_{n}}\)
-- 24 sty 2013, o 22:00 --
Sprawdzałem to dla kilku przypadków i hula
-- 24 sty 2013, o 23:47 --
Otóż można:
z drugiego liczymy \(\displaystyle{ A_{n+1}=a_{n+1}-a_{n}}\)
i podstawiamy do pierwszego:
\(\displaystyle{ A_{n+2}=a_{n+2}-a_{n+1}}\)
i do pierwszego podstawimy i mamy:
\(\displaystyle{ a_{n+1}=2^{n-1}+2a_{n-1}}\)
lub:
\(\displaystyle{ a_{n+2}=2a_{n}+2^{n}}\)
-- 25 sty 2013, o 01:45 --
wzór jawny na \(\displaystyle{ a_{n}}\)
\(\displaystyle{ a_{n}= \frac{1}{4}[( \sqrt{2}-1 )(-1)^{n}- \sqrt{2}-1 ]2^{ \frac{1}{2}n }+2^{n-1}}\)-- 25 sty 2013, o 17:50 --Teraz wzór jawny na: \(\displaystyle{ A_{n}}\)
\(\displaystyle{ A_{n+1}=- \frac{1}{4}2^{ \frac{1}{2}n }[(-1)^{n}+1] +2^{n-1}}\)