Условие задачи "Найдите количество циклических последовательностей длины 16 из 3 символов, в которых встречается ровно 2 символа из 3" Решаю, но все время получается нецелый ответ.

Мое решение 1) Выберем 2 символа из 3 - это можно сделать 3 способами. Затем считаем количество циклических последовательностей по формуле включения исключения. Фотография предполагаемого решения по ссылке https://scontent-mxp1-1.xx.fbcdn.net/v/t34.0-0/p280x280/28512596_10210772873229213_1178242398_n.jpg?_nc_ad=z-m&_nc_cid=0&oh=6415a7cfb1c0c4f62724486ae5ea45b0&oe=5A9B73EC

Что я делаю неправильно? Спасибо заранее.

задан 2 Мар '18 11:52

10|600 символов нужно символов осталось
1

Что изображено по ссылке, я совершенно не могу разобрать, поэтому не могу сказать, что там неправильно. Итак, считаем число циклических последовательностей длины 16 на символах a, b, из которых оба входят. В конце умножаем на 3.

С каждой последовательностью (циклической или нет) можно связать её наименьший период. Он всегда является делителем длины последовательности, что следует из простых теоретико-числовых соображений. В нашем случае длина наименьшего периода принимает значения 16, 8, 4 или 2. Период 1 невозможен, так как получается слово из одинаковых символов.

Если слово не имеет минимальный период 16, то оно является "квадратом" слова длины 8, и наоборот. Поэтому последовательностей с минимальным периодом 16 будет 2^{16}-2^8. Каждая из них даёт ровно 16 циклических сдвигов, и они попарно различны (если нет, то есть меньший период). Поэтому циклических последовательностей с таким периодом будет в 16 раз меньше, то есть (2^{16}-2^8)/16. Теперь смотрим на слова с минимальным периодом 8. Здесь по аналогичным соображениям получается (2^8-2^4)/8 циклических последовательностей. Далее (2^4-2^2)/4 ц.п. с минимальным периодом 4, и (2^2-2^1)/2 с минимальным периодом 2 (это одна штука).

Складывая, имеем (2^{12}-2^4)+(2^5-2^1)+(2^2-2^0)+(2^1-2^0)=4114. Умножение на 3 даёт ответ 12342.

ссылка

отвечен 2 Мар '18 17:57

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,301

задан
2 Мар '18 11:52

показан
541 раз

обновлен
2 Мар '18 17:57

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

по почте:

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

по RSS:

Ответы

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

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