Нахождение количества двоичных последовательностей

[provincialka]

Ох... что-то нет азарта всё это читать. Вот мое решение.

Рассмотрим "хорошие" последовательности (длины $n$), начинающиеся и заканчивающиеся 1, обозначим их число через $N(n)$. Легко заметить, что такие последовательности существуют только для нечетного $n=2k+1$. Разобьём последовательность на первую единицу и пары цифр: $1110101111101=1(11)(01)(01)(11)(11)(01)$. Пар будет $k$ штук и они будут иметь вид $(01)$ или $(11)$. Поставим им в соответствие цифры $0$ и $1$. Получим последовательность из единицы и $k$ цифр $0$ и $1$ в произвольном порядке (для примера -- $1100110$). Таких последовательностей существует $2^k$. Значит, $N(2k+1)=2^k$.
Теперь вспоминаем про связь $G(n)$ и $N(n)$. Получаем, что

$$G(2k)=2N(2k-1)=2\cdot2^{k-1}=2^k$$

$$G(2k+1)=N(2k+1)+N(2k-1)=2^k+2^{k-1}=3\cdot2^{k-1}$$

[iancaple]

provincialka в сообщении #1089321 писал(а):

Получаем, что

$$G(2k)=2N(2k-1)=2\cdot2^{k-1}=2^k$$

$$G(2k+1)=N(2k+1)+N(2k-1)=2^k+2^{k-1}=3\cdot2^{k-1}$$

К сему подпись: W.Edwin Clark,2008 A063579
Только его ответы надо делить на 2, так как начало и конец в позиции 3 у нас не допускаются. А номера состояний у него такие же, как у меня в посте 2 (случайное совпадение)
Извините, вернулся к шапочному разбору, задача и раньше на форумах была
И еще интересное исключение: $G(1)=2$

[waxtep]

provincialka в сообщении #1089321 писал(а):

Вот мое решение

Согласен, Ваш способ гораздо изящнее, еще раз большое спасибо!

В качестве оффтопика: мне этот способ субъективно дался труднее, поломал голову над связью между $G$ и $N$, а потом снова попытался "соскочить" на рекуррентность, не выписывая в явном виде выражения для $N$. Это в данном варианте не дает решения, а только равенство $G(2m)$ удвоенной знакопеременной сумме $G$ для нечетных индексов $\lt 2m$, типа $16=2(12-6+3-1)$ и т.п.

-- 09.01.2016, 18:11 --

iancaple в сообщении #1089329 писал(а):

К сему подпись: W.Edwin Clark,2008 A063579
Только его ответы надо делить на 2, так как начало и конец в позиции 3 у нас не допускаются. А номера состояний у него такие же, как у меня в посте 2 (случайное совпадение)
Извините, вернулся к шапочному разбору, задача и раньше на форумах была
И еще интересное исключение: $G(1)=2$

Спасибо за участие! Наверное, опечатка, Вы имеете в виду A029744?
Мне очень помогла provincialka, в первую очередь, правильно понять условие решаемой задачи И способ решения, конечно, элегантный, я бы до него точно не быстро допер. В обоснование своего подхода могу только сказать, что он вызван желанием максимально изолироваться от рассмотрения структуры изучаемых последовательностей, поиск легкого пути.

[iancaple]

waxtep в сообщении #1089357 писал(а):

iancaple в сообщении #1089329 писал(а):

К сему подпись: W.Edwin Clark,2008 A063579

Наверное, опечатка, Вы имеете в виду A029744?

Другая опечатка, A063759
Примерно в 2006м решалась на аопсе. Потом Кларк написал в oeis о связи ответа этой задачи с уже имевшейся там последовательностью, может, в связи с этим, ну неважно. Потом еще на одном форуме, и там пошла ссылка на этот аопс, сейчас не найти. Но я и так помню, что все математики, решавшие задачу, не сговариваясь, работали с моделью случайных блужданий, как более наглядной, и я полагал, что так проще объяснить, в уме решается. provincialka- редкий человек, увидевшая задачу впервые, но ответ у нее вышел верный с одной поправкой, поздравляю :)

[provincialka]

"Поправка" -- это про $G(1)$? Ну, я просто не стала на этом заострять внимание... А что касается "случайных блужданий" -- я их просто плохо знаю

[waxtep]

iancaple в сообщении #1089466 писал(а):

waxtep в сообщении #1089357 писал(а):

iancaple в сообщении #1089329 писал(а):

К сему подпись: W.Edwin Clark,2008 A063579

Наверное, опечатка, Вы имеете в виду A029744?

Другая опечатка, A063759

Рискну немного позанудничать, A029744 подходит лучше, т.к. это в явном виде "Numbers of the form $2^n$ or $3\cdot2^n$" - в точности решение данной задачи, без поправок. (Прошу прощения, я, похоже, не уловил связи с последовательностю A063759, просто фиксирую лобовое наблюдение, что в ней отсутствует значение $G(2)=2$ из решения данной задачи).

И еще капля: в методе, предложенном provincialka, можно обойтись без "заглядывания внутрь" последовательности $N(n)$, если заметить, что последовательности $N(n+2)$ могут быть однозначно получены из $N(n)$ добавлением к ним слева $10$ или $11$. Это сразу дает $N(n+2)=2\cdot N(n)$ и ответ в явном виде для $N$ и $G$.

[iancaple]

Кларк рассматривал последовательности из $1,2,3$, такие, что соседние члены отличаются ровно на единицу.Чтобы его последовательности превратить в Ваши, надо тройки и двойки заменить на единицы, а его единицы на наши нули. А у нас еще условие, чтобы в начале и в конце не было тройки, только это гарантирует нечетность на концах. Оказывается, это просто сдвигает последовательность вправо , т.к. свойство остается: увеличение степени двойки в 2 раза происходит в 2 этапа, сначала в $\frac 32$ раза, потом в $\frac 43$ раза -а как еще оно могло происходить, чтобы числа оставались целыми. То, что увеличение при $n>1$ происходит в одно и то же число раз, следует из того, что $10$ или $01$ -ровно одну из них, и $11$ можно вставлять после 1-й позиции, чтоб не нарушить концы.

[waxtep]

iancaple в сообщении #1089532 писал(а):

Кларк рассматривал последовательности из $1,2,3$, такие, что соседние члены отличаются ровно на единицу.Чтобы его последовательности превратить в Ваши, надо тройки и двойки заменить на единицы, а его единицы на наши нули. А у нас еще условие, чтобы в начале и в конце не было тройки, только это гарантирует нечетность на концах. Оказывается, это просто сдвигает последовательность вправо , т.к. свойство остается: увеличение степени двойки в 2 раза происходит в 2 этапа, сначала в $\frac 32$ раза, потом в $\frac 43$ раза -а как еще оно могло происходить, чтобы числа оставались целыми. То, что увеличение при $n>1$ происходит в одно и то же число раз, следует из того, что $10$ или $01$ -ровно одну из них, и $11$ можно вставлять после 1-й позиции, чтоб не нарушить концы.

В значительной степени понял, спасибо Вам! Что не допонял, оставлю себе на додумывание
А метод со вставкой двух цифр на вторую позицию, это, похоже, самый быстрый способ решения! (только в нем надо не забыть аккуратно обработать тот самый исключительный случай $n=3$, где последовательность $011$ "нехороша")