Давайте сейчас я поставлю еще одну комбинаторную задачу, которая решается с помощью чуть-чуть более продвинутой техники, нежели та, которую мы до сих пор изучали. Комбинаторная задача будет очень близкая к тем, которые мы рассматривали, но, вот, тем не менее, я сейчас продемонстрирую, что это не вполне тривиально, и дальше мы постепенно двинемся в сторону понимания той техники, с помощью которой можно решить эту задачу. Значит, назовем тему «Число циклических последовательностей». [ПИШЕТ НА ДОСКЕ] Тема у нас будет «Число циклических последовательностей», и сейчас я объясню, о чем идет речь. Ну вот давайте, пусть у нас есть некоторый набор символов, объектов, ну, скажем, X, это набор таких вот объектов b₁, ..., br, r – это просто их количество, скажем, 100, 10 там, неважно, – сколько-то объектов. Можно себе представлять это таким образом, что у нас есть алфавит X, в котором есть буквы b₁, ..., br. Ну, по сути, то же самое. Значит, есть алфавит, состоящий из символов b₁, ..., br. Давайте еще зафиксируем какое-нибудь натуральное число n, и, сперва, зададимся совершенно тривиальным вопросом, который мы с вами уже умеем решать. А именно, сколько существует слов, слов длины n вот в этом алфавите? Ну, r в степени n, правильно? Ну, давайте я это просто напишу: всего различных слов длины n, которые, в принципе, можно составить из букв нашего алфавита, ну вот так я напишу: слов длины n над алфавитом X. Вот всего слов длины n над этим алфавитом X, конечно, r в степени n. На каждую позицию можно поставить любую из r-букв, мы это много раз проходили. Слова – это, по сути, размещения с повторениями, ничего нового. Слова – это размещения с повторениями. Ну вот, давайте запишем какое-нибудь слово a₁, a₂, a₃, ..., an. Записали. Давайте я его еще так вот нарисую, чтоб было совсем понятно, какую операцию мы затем над ним проделаем. Мы поставим стрелочки, идущие от предыдущей буквы к следующей, то есть, стрелочку, которая идет от а₁ к а₂, потом стрелочку от а₂ к а₃, ну и так далее, просто, ну таким образом замечая, что за одной буквой следует другая, ничего особенного. Это обычное слово, обычное слово. А теперь смотрите, я возьму и добавлю вот такую стрелку. Добавлю к обычному слову вот такую вот стрелку, которая его как бы зацикливает, то есть, расположу буквы этого слова по циклу. Что-нибудь изменится? Ну, давайте пример. Чтоб было всем абсолютно понятно, что что-то изменится, надо рассмотреть пример. Вот пусть, скажем, у нас X – это алфавит, состоящий из каких-нибудь символов, да? Ну я очень люблю биологам рассказывать, используя символы химического происхождения. Мне тут говорили, что, в качестве альтернативы к этой аудитории, можно рассматривать большую химическую, там бы это было очень уместно. Ну, я думаю, что мы отсюда уже никуда не уйдем, а химические символы, если кому не нравятся, можете интерпретировать, как буквы русские С, О, Н. Да? Вот, было у нас с вами такое слово СОСО, можете интерпретировать по-своему. Вот мы его буквы, буквы этого слова, взяли и расположили по циклу: С, О, С, О. И зациклили, то есть, провели стрелочку из последней буквы в начальную. Понятно, что если бы мы проделали ту же самую операцию с вот таким вот словом – ОСОС, я не думаю, что надо его как-то иначе интерпретировать, это О С О С. Вот, если мы проделаем аналогичную операцию зацикливания с таким словом, то, согласитесь, получится абсолютно тот же самый цикл. Ну, какая разница, как он там расположен на плоскости? Ну повернуть его можно как угодно, с точностью до поворотов, до переносов каких-то параллельных, это абсолютно тот же самый цикл. А исходные слова, они же разные, ну согласитесь. Разные слова дают один и тот же цикл, то есть, в результате вот этой операции зацикливания, некоторые разные слова превращаются в одно и то же циклическое слово. Вопрос основной: сколько различных циклических слов, циклических слов длины n над вот этим алфавитом X? Как это посчитать? Неправильно! Потому что r в степени n делить на n нельзя. Это не целое число. Ну, 2 в степени n на 17 делится? 2 в 17-той на 17? Не судьба! А почему нельзя делить на n? Нельзя делить на n, потому что некоторые слова, вот, смотрите, допустим, в этом же алфавите, вот такое возьмем слово СОСН. Почти «СОСНА», да? Ну, «А» у нас буквы нету, к сожалению. Значит, вот, давайте возьмем такое слово – СОСН. Попробуем начать его располагать, да? С, О, С, Н. Вот это слово хорошее, с вашей-то как раз точки зрения, тут надо делить на n, это правильно, потому что, если вы возьмете любое слово, получающееся, так сказать, циклическим сдвигом из него, то есть, ОСНС, потом СНСО и, наконец, НСОС, вот, любое из этих четырех слов, и примените к нему операцию зацикливания, то получится один и тот же цикл. Правильно? То есть, действительно, для этого слова есть n различных перестановок, циклических сдвигов, которые приводят к одному и тому же циклическому слову. Но уже вот для этого слова, сколько таких? Только 2, правильно, не 4? Не n, потому что следующий циклический сдвиг приводит нас обратно. Вот в этом основная идея, то есть, делить на что-то единообразное мы точно не можем, нам нужно как-то расклассифицировать все наши обычные слова по вот этой вот, так сказать, периодичности. Но это мы потом последовательно сделаем, всё будет, конечно, всё будет аккуратно изложено. Но, для того чтобы расклассифицировать, нам потребуется некоторые факты из теории чисел. Нам придется, знаете, так немножко забежать вперед что ли. Вообще-то, теория чисел, это, конечно, отдельный кусок курса, который начнется после комбинаторики, но для решения вот этой задачи нам потребуется несколько фактов из теории чисел. Давайте я про них расскажу. То есть, смотрите, я поставил задачу: мне нужно отыскать вот такую величину, – это количество различных циклических слов длины n над алфавитом из r символов. Но я пока не умею её решать, потому что я не могу использовать некоторые факты. И вот сейчас будет такое существенное отступление, которое поможет нам, в конечном счете, решить эту задачу. Вот так себе это как-то и пометьте. Сейчас будет довольно длительное отступление, но, в итоге, мы вернемся к этой задаче и её блистательно решим.