Сколько двоичных последовательностей длины $%n$% в которых есть только два элемента $% \{0;1 \} $% и в ней нет
(($%k$% или более единиц подряд) и ($%m$% и более нулей подряд))?

задан 25 Май '17 6:42

изменен 25 Май '17 12:50

В первой фразе, наверное, имелось в виду, что рассматриваются двоичные последовательности. Обращаю внимание на то, что мысль там сформулирована несколько неудачно: ведь наличие 0 и 1 не исключает того, что могут быть какие-то ещё символы.

Такого рода задачи в принципе решаются стандартными методами, хотя я не уверен, что ответ в общем случае будет выглядеть "красиво". Но его можно представить через производящие функции, и найти показатель роста. Имеется в виду, что число растёт как a^n, где a зависит от k и m.

(25 Май '17 12:44) falcao

Ну, я понял вашу мысль о показательной функции, ведь частные примеры вроде: 'без двух единиц' выражаются через фиббоначи, а это есть золотое сечение с аргументом в степени. Да, сейчас переформулирую.

(25 Май '17 12:50) Williams Wol...

Да, там из общей теории следует, что асимптотика имеет именно такой вид. То есть корень n-й степени из n-го члена стремится к какому-то значению a, которое в частном случае, Вами отмеченном, равно "золотому сечению". Это корень алгебраического уравнения, которое можно выписать явно для любых k и m. Далее его можно найти с любой заданной точностью численными методами.

(25 Май '17 13:00) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

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

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,696

задан
25 Май '17 6:42

показан
212 раз

обновлен
25 Май '17 13:00

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru