Комбинаторика

[Ward]

Здравствуйте!

Рассматривается последовательность длины $N$ из цифр $0,1$. Во скольких из них $1$ не встречается 3 раза подряд?

[VAL]

Ward в сообщении #651220 писал(а):

Рассматривается последовательность длины $N$ из цифр $0,1$. Во скольких из них $1$ не встречается 3 раза подряд?

Очень странное условие! "Рассматривается последовательность" - то есть одна. А вопрос ставиться - "Во скольких из них...".

[Ward]

VAL
Извиняюсь там рассматриваются последовательности длины $N$ из $0, 1$. Всего таких $2^N$

[cool.phenon]

Кроме тех,которые идут 3 раза подряд, еще есть в последовательностях какие-то единицы?

[Ward]

да конечно могут.

[gris]

Посчитайте количество последовательностей, в которых 3 единицы подряд встречаются хотя бы раз.

[Whitaker]

gris
не понимаю Вас, а зачем это? да и вообще это не так уж легко посчитать
ровно 3 раза?

[Slip]

Попробуйте связать количество таких последовательностей длины $N$ с количеством таких же последовательностей меньшей длины. Что-то из серии "если последняя цифра в последовательности 0, то перед ним может идти... Если последняя цифра 1, то перед ней может идти... и т.д.".

[VAL]

Математика Трибоначчи нет и никогда не было. Но дело его живет!

[Ward]

Slip
Искомое количество обозначим через $f(N)$. Если последняя цифра $0$, то таких всего $f(N-1)$, а если последняя цифра $1$, то тут уже что-то не понимаю. А как быть в случае когда последняя цифра единица?

[Whitaker]

Ward
Ну если последняя цифра нулевая, то количество таких равно $f(N-1)$
Если последняя цифра единица, то рассмотрим еще 2 случая:
- предпоследняя нулевая, тогда искомое количество есть $f(N-2)$
- предпоследняя единица, значит предпредпоследняя может быть только нулевой, а это количество $f(N-3)$
Получаем, что $f(N)=f(N-1)+f(N-2)+f(N-3)$

(Оффтоп)

Хотя могу ошибаться, но думаю спецы подскажут..

[VAL]

Whitaker в сообщении #651307 писал(а):

Ward
Ну если последняя цифра нулевая, то количество таких равно $f(N-1)$
Если последняя цифра единица, то рассмотрим еще 2 случая:
- предпоследняя нулевая, тогда искомое количество есть $f(N-2)$
- предпоследняя единица, значит предпредпоследняя может быть только нулевой, а это количество $f(N-3)$
Получаем, что $f(N)=f(N-1)+f(N-2)+f(N-3)$

(Оффтоп)

Хотя могу ошибаться, но думаю спецы подскажут..

(Оффтоп)

То, что Вы не ошибаетесь, я уже раньше написал.
А то, что спецом не считаюсь... Абидна!..

[Whitaker]

VAL
Если я Вас чем-то обидел, то прошу прощения!
Я имел ввиду, что если ошибусь Вы или другие спецы исправят меня ..

[Shadow]

Whitaker,

(Оффтоп)

$a_n=a_{n-1}+a_{n-2}$ - числа Фибоначчи (или Дибоначчи, или Бибоначчи)
$a_n=a_{n-1}+a_{n-2}+a_{n-3}$ - числа Трибоначчи

[VAL]

Whitaker в сообщении #651320 писал(а):

VAL

(Оффтоп)

Если я Вас чем-то обидел, то прошу прощения!

(Оффтоп)

Я ведь смайлик поставил. То есть не обиделся

Цитата:

Я имел ввиду, что если ошибусь Вы или другие спецы исправят меня ..

А я имел в виду то, что уже прокомментировал Shadow.