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

[waxtep]

Уважаемые коллеги, доброе утро!

Просьба помочь в решении следующей задачи (источник: 10ый класс, внешкольные умеренно "продвинутые" занятия).

Найти число двоичных последовательностей длины $n$, в которых нет двух нулей стоящих подряд, а все максимальные подпоследовательности из одних единиц нечетной длины.

Попытка решения:
1. Будем называть последовательности, обладающими данным свойством "хорошими", и обозначать их число как $G(n)$. Будем искать выражение для $G(n)$ в рекуррентном виде.

2. Если мы захотим говорить о "хороших" последовательностях длины $n$, начинающихся с определенной последовательности двоичных цифр $abcd...$, то их число будем обозначать как $G(n, abcd)$. Например, $G(4,01)$ - число хороших последовательностей длины $4$, начинающихся с $01$. Легко проверить, что таких последовательности две - $0101$ и $0111$, т.е. $G(4,01)=2$.

3. Набросок попытки решения, основанной на добавлении нулей и единиц в начало последовательности, с минимумом комментариев:

$$G(n)=G(n,01)+G(n,10)+G(n,11) \eqno (1)$$

$$G(n,01)=G(n-1,1) \eqno (2)$$

$$G(n,10)=G(n-1,0) \eqno (3)$$

(добавление нуля слева не изменяет "хорошести" последовательности, начинающейся с единицы, и то же самое верно для добавления единицы к последовательности, начинающейся с нуля).
По определению,

$$G(n-1,0)+G(n-1,1)=G(n-1) \eqno (4)$$

Следовательно, из $(1-3)$ получаем

$$G(n)=G(n-1)+G(n,11) \eqno (5)$$

Далее, при анализе $G(n,11)$ есть соблазн предположить, что "добавление четного количества единиц в начало последовательности не меняет ее свойства хорошести" и, тогда, очевидно,

$$G(n,11)=G(n-2) \eqno (6)$$ $$G(n)=G(n-1)+G(n-2) \eqno (7)$$

Искомое рекуррентное соотношение найдено, известная последовательность Фибоначчи.
К сожалению, это не так, предположение про добавление четного кол-ва единиц неверно, чему легко построить контр-примеры:
$01\to 1101$ - из хорошей последовательности получилась плохая
$1011\to 111011$ - наоборот, из плохой хорошая.
Попробуем понять, чему равна разность между числом улучшаемых плохих последовательностей и ухудшаемых хороших, обозначим ее $d(n-2,11)$. В этом обозначении верная формула для $G(n)$:

$$G(n)=G(n-1)+G(n-2)+d(n-2,11) \eqno (7')$$

Улучшаемые плохие последовательности удовлетворяют следующим критериям:
- в них нет двух нулей подряд;
и
- они начинаются с нечетного количества единиц, на единицу меньшего максимальной длины подпоследовательности из идущих подряд единиц, и, затем, нуля; пример: $1011$.
А, ухудшаемые хорошие таким:
- в них нет двух нулей подряд (по определению);
и
(
- они начинаются с нуля и не содержат $111$; легко видеть, что для любого $n$, такая последовательность ровно одна - $01010...$;
или
- они начинаются с четного количества единиц, на единицу меньшего максимальной длины подпоследовательности из идущих подряд единиц, и, затем, нуля; пример: $110111$.
)
Далее, нестрого, в силу "симметричности" двух определений выше, можно предположить, что

$$d(n-2,11)=-1 \eqno (8)$$

для любого $n$. Но это не работает сразу для $n=3$, и далее "то работает, то не работает".
Опровержение $(8)$ получено прямым построением хороших последовательностей для $n=1,2,...8$ и подсчете $G(n)$ для них:

$$1,2,3,4,6,10,16,26$$

Следующие два члена $G(n)$, для $n=9,10$, предположительно, $44$ и $68$, вручную для них строил только "ухудшаемые" и "улучшаемые" последовательности.
Первые члены $d(n-2,11)$, начиная с $n=3$:

$$0,-1,-1,0,0,0,2,-2$$

===09.01.15 11:25: Исправление супер-дурацкой ошибки! Конечно, $G(1)=1$, а не $2$, как было в исходной версии.
Соответственно, d(1)=0, и формула (8) неверна сразу, для $n=3$.
На OEIS ближайшая по смыслу, но, несовпадающая последовательность - A143283
===
Уважаемые коллеги, запрос о помощи следующий:
1. Возможно, я где-то проврался (в выводе и/или ручном построении), и вы сможете подсказать иной способ решения?
2. Если нет, и все правда мрачно (нет внятной линейной рекуррентности), то что можно сказать о $d(n,11)$ как функции $n$, как можно подойти к вопросу получения нижней и верхней оценки для ее значений?
Заранее большое спасибо!

[iancaple]

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

... сможете подсказать иной способ решения?

Есть другой способ, который не может не привести к ответу. Рассмотрим случайное блуждание по графу из трех стостояний:
1.На конце строящейся допустимой последовательности 0
2. На конце единицы, в нечетном количестве.
3. На конце единицы, в четном количестве.
Из состояний 1 или 3 - можно перейти только в 2. А из 2 в любое из 1 и 3 (то есть состояние 2- единственная точка бифуркации)
Вот и надо найти число допустимых n-вершинных путей на этом графе.
Хотя, конечно, надо и Ваш текст проанализировать, он разумен, но спешу(

[provincialka]

waxtep
Честно говоря, читать весь текст затруднительно... Тем более, у вас там много "сопутствующих рассуждений". А вы не пробовали разбить все случаи по числу нулей (групп единиц)?
Например, обозначим через $N(n)$ число искомых последовательностей, начинающихся и заканчивающихся единичками. Тогда ответом будет $N(n)+N(n-2)$ при нечетном $n$ и $2N(n-1)$ при четном.
А для фиксированного числа групп единичек всё можно свести к известной схеме "предметы и перегородки", то есть к размещениям с повторениями.
Правда не уверена, что там получится формула в замкнутом виде...

-- 09.01.2016, 12:27 --

Нет, кажется, суммируется! Причём ответ подозрительно простой...

[waxtep]

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

1.На конце строящейся допустимой последовательности 0
2. На конце единицы, в нечетном количестве.
3. На конце единицы, в четном количестве.
Из состояний 1 или 3 - можно перейти только в 2. А из 2 в любое из 1 и 3 (то есть состояние 2- единственная точка бифуркации)

Спасибо!
Здесь, если я правильно понимаю, вот в чем коварство: нельзя запретить переход из 3 в 1.
Например, мы находимся в вершине 011; действительно, последовательность 0110, соответствующая переходу 3->1, будет "плохой". Но, более длинная 0110111, находящаяся на этом же пути, будет "хорошей", т.е. не получается запретить такие переходы.

[provincialka]

waxtep
Не надо рекуррентной формулы! Я попробовала посчитать "по-своему", значение $N(n)$ -- проще некуда! Вы, кстати, провели эксперимент? Проверили, сколько последовательностей получается при небольших $n$?

(Оффтоп)

Последовательности $101110101$ можно поставить в соответствие последовательность $1(01)(11)(01)(01)$... хм... дальше не подсказываю, будет уже полное решение!

[waxtep]

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

А вы не пробовали разбить все случаи по числу нулей (групп единиц)?
Например, обозначим через $N(n)$ число искомых последовательностей, начинающихся и заканчивающихся единичками. Тогда ответом будет $N(n)+N(n-2)$ при нечетном $n$ и $2N(n-1)$ при четном.
...

Нет, кажется, суммируется! Причём ответ подозрительно простой...

Спасибо! Да, думал о таком подходе, но не смог сообразить, как в нем формализовать условие нечетности длин максимальных последовательностей из идущих подряд единиц. Я могу Вас попросить развернуть этот момент?
Плюс, меня смущает, что последовательности $G(n)$ нет в OEIS, т.е. простого аналитического вида ждать трудно(?) хотя, конечно, я мог просто наврать при ручном построении Подскажите, пожалуйста, у Вас получается, например, $G(6)=10$?

PS: прошу прощения за длинноты в тексте, хотел показать, в какие тупики уже заходил.

[provincialka]

А у меня так не получается!
У меня трудность в том, что нельзя в учебном разделе писать полные решения. Но я советую вам сосредоточиться на вычислении $N(2k+1)$, остальное приложится.
Например, при $n=6$ последовательность обязательно начинается или заканчивается нулем. То есть $G(6)=2N(5)$.
В $N(5)$ входят такие последовательности: $(11111),(11101),(10111),(10101)$, всего 4, то есть $G(6)=8$ Откуда у вас еще две последовательности взялись?

-- 09.01.2016, 13:13 --

Вы прочитали подсказку в оффтопе? На самом деле, данную последовательность можно некиим способом получить из произвольной, но более короткой...

[waxtep]

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

waxtep
Не надо рекуррентной формулы! Я попробовала посчитать "по-своему", значение $N(n)$ -- проще некуда! Вы, кстати, провели эксперимент? Проверили, сколько последовательностей получается при небольших $n$?

Заглянул в "спойлер", попробую побороться, спасибо! Кас. эксперимента для небольших $n$, да, конечно, вот они для $n=1,...,8$:

$$1,2,3,4,6,10,16,26$$

и, с меньшей уверенностью могу сказать, что дальше будут члены 44 и 68 (для них проводил только неполное построение - какие последовательности длины $n-2$ изменят свойство "хорошести" при добавлении к ним двух единиц слева). У Вас столько же получается, например для $n=6, 7$?

[provincialka]

У меня $N(2k+1)=2^k$. И есть простой алгоритм, как найти это число без долгих построений!
Ой! Надеюсь, меня модераторы не накажут ...

[waxtep]

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

В $N(5)$ входят такие последовательности: $(11111),(11101),(10111),(10101)$, всего 4, то есть $G(6)=8$ Откуда у вас еще две последовательности взялись?

Вот они, 10 хороших последовательностей для $n=6$, в порядке возрастания:
010101
010111
011101
011111
101010
101110
110111
111010
111011
111110

И, 6 штук для $n=5$:
01010
01110
10101
10111
11101
11111

[provincialka]

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

вот они для $n=1,...,8$:

$$1,2,3,4,6,10,16,26$$

Это $G$ или $N$? У меня получилось $1,2,3,4,6,8,12,16,24,...$

-- 09.01.2016, 13:29 --

А! Я поняла! Мы по-разному понимаем условие задачи! насчёт "максимальных последовательностей из 1".
Там ведь сказано "ВСЕ максимальные последовательности". Например, в цепочке $10111101101$ максимальными будут подпоследовательности $(1),(1111),(11),(1)$, а не только $(1111)$! Иначе зачем о них говорить во множественном числе!
А вот эта подпоследовательность $10\underbrace{111}_{}101101$ максимальной не будет! Потому что её можно продолжить ещё на одну единичку.

[waxtep]

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

У меня $N(2k+1)=2^k$. И есть простой алгоритм, как найти это число без долгих построений!
Ой! Надеюсь, меня модераторы не накажут ...

по следующему Вашему сообщению, понял, что не те примеры привожу, т.к. говорю про $G$, а не про $N$; прошу прощения, сейчас попробую разобраться.
А последовательность 1,2,3,4,6,8,12,16,24 - это у Вас для $G$, верно? Если да, посмотрите плиз мой пример для $G(6)$ - я там выписал все 10 (а не 8) последовательностей в явном виде.

-- 09.01.2016, 13:42 --

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

А! Я поняла! Мы по-разному понимаем условие задачи! насчёт "максимальных последовательностей из 1".

О! Вот это похоже "в яблочко"! Я решал не ту задачу, которую задали
Про самые длинные подпоследовательности, а не про ограниченные нулями.
СПАСИБО!!!

[provincialka]

waxtep
Видимо, да. "Моя" формулировка, во-первых, дает простое решение (и простой ответ). А во-вторых, соответствует тому, как слово "максимальный" понимает высшая математика: тот, который нельзя увеличить, а не тот, который больше других о размеру.

А вы все-таки напишите своё решение! (если напишете, я смогу в ответ написать своё)

[waxtep]

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

waxtep
Видимо, да. "Моя" формулировка, во-первых, дает простое решение (и простой ответ). А во-вторых, соответствует тому, как слово "максимальный" понимает высшая математика: тот, который нельзя увеличить, а не тот, который больше других о размеру.

А вы все-таки напишите своё решение! (если напишете, я смогу в ответ написать своё)

Да, я, честно говоря, не воспринял "максимальную подпоследовательность" за термин, а самоуверенно списал на корявость формулировки условия сейчас попробую порешать, напишу.

[waxtep]

Найти число двоичных последовательностей длины $n$, в которых нет двух нулей стоящих подряд, а все максимальные подпоследовательности из одних единиц нечетной длины.

Решение:

$$G(n)=G(n,01)+G(n,10)+G(n,11) \eqno (1)$$

$$G(n,01)=G(n-1,1) \eqno (2)$$

$$G(n,10)=G(n-1,0) \eqno (3)$$

$$G(n-1,0)+G(n-1,1)=G(n-1) \eqno (4)$$

Следовательно, из $(1-3)$ получаем

$$G(n)=G(n-1)+G(n,11) \eqno (5)$$

Далее, новое равенство для $G(n,11)$:

$$G(n,11)=G(n-2,1) \eqno (6)$$

(добавление двух единиц слева оставлят хорошими только последовательности, начинающиеся с единицы, но не с нуля)
Рассмотрим, что такое $G(m,1)$ и получим рекуррентно:

$$G(m,1)=G(m)-G(m,0)=G(m)-G(m-1,1)=$$ $$=G(m)-G(m-1)+G(m-2)-...+{-1}^{m-1}G(1,1) \eqno (7)$$

Подставим $(7)$ в $(6)$ и далее в $(5)$, записанное для $n$ и $n+1$:

$$G(n)=G(n-1)+G(n-2)-G(n-3)+...+{-1}^{n-1}G(1,1) $$ $$G(n+1)=G(n)+G(n-1)-G(n-2)+...+{-1}^{n}G(1,1) \eqno (8)$$

И сложим, получая

$$G(n+1)+G(n)=G(n)+2G(n-1) \eqno (9)$$

Т.е.

$$G(n+1)=2G(n-1) \eqno (9')$$

(Заметим, что это равенство верно только при $n\ge 3$)
Значения для $n<3$ вычисляем эмпирически $(1,2,3)$, а далее, $G(2m)=2^m, G(2m+1)=3\cdot2^{m-1}$, что и дает первые члены

$$1,2,3,4,6,8,12,16,24,32,48,...$$

-- 09.01.2016, 15:55 --

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

waxtep

А вы все-таки напишите своё решение! (если напишете, я смогу в ответ написать своё)

Решил, посмотрите плз предыдущее сообщение в теме. Таки через рекурретность, осознаю, что довольно громоздко, но, гм, это решение
Я воспроизвел в сообщении условие и начало поиска отношеия; новое начинается с формулы (6) - в правильной постановке задачи упрощается и рекурретно выражается $G(n,11)$