В общем, конечно, вся эта наука была введена, на самом деле,
ради того, чтобы вам посчитать, ну не вам посчитать, а чтобы я смог
для вас посчитать количество циклических последовательностей.
Эта задача ставилась на прошлой лекции, правда ведь?
Ну давайте я напомню, что нас интересует такая задача: вот есть
у нас некоторый алфавит,
состоящий из r различных символов,
r – это просто какое-то натуральное число, конечно.
У нас есть еще одно натуральное число n, которое так же служит параметром задачи.
И нас интересует T с индексом r от n, которое
представляет собой число различных
циклических последовательностей,
которые имеют длину n,
...длины n, и которые составлены из букв нашего алфавита.
Ну я это коротко запишу как «над алфавитом X».
Число различных циклических последовательностей,
имеющих длину n и составленных из букв нашего алфавита.
В прошлый раз я вам приводил примеры, которые показывают,
почему подсчет числа этих циклических последовательностей нетривиален.
Давайте введем такие обозначения, если не делали этого раньше,
а именно обозначим обычную последовательность
a1, a2, ...,
an – просто вот так, как ее и принято, в общем, обозначать.
А циклическую последовательность
обозначим вот так со скобочками (a1,
a2, ..., an), желая подчеркнуть, что мы именно зациклили наше соединение.
Добавили еще одну связку, стрелочку.
Так, еще раз вопрос: сколько всего различных вот таких вот
последовательностей обычных?
r в степени n.
Ну давайте это зафиксируем: r в степени n – это число всех, давайте их
называть не обычными последовательностями для удобства, а линейными.
Линейные последовательности и циклические.
В линию вытянуты или по циклу расположены.
Число всех линейных последовательностей – оно,
конечно, r в степени n.
Так.
Смотрите, сейчас я буду делать следующее.
Конечно, если вы хотите, я прямо сразу сформулирую теорему.
Но мне, честно говоря, кажется теорема слишком страшной.
Давайте я лучше буду постепенно к ней приходить, и в итоге у нас получится
нужное нам утверждение, то есть формула для числа циклических последовательностей.
Будем постепенно, постепенно ее получать, путем некоторых естественных рассуждений.
Вот я вместе с вами этот путь сейчас собираюсь пройти.
Давайте введем еще одно обозначение стандартное для нас.
Буквой V обозначим множество всех линейных последовательностей.
Не число, а множество.
Множество все тех же линейных последовательностей,
то есть мощность V – это r в степени n.
Просто такое обозначение, удобное для нас.
[КАШЕЛЬ] Так,
вот давайте возьмем какую-нибудь линейную последовательность a1,
a2, ..., an, так,
принадлежащую множеству V.
Взяли какую-то последовательность.
Давайте назовем ее циклическим сдвигом,
назовем ее циклическим сдвигом,
[ШУМ] операцию,
которая переводит
ее в последовательность a2,
a3, ..., an, a1.
Ну очень простое определение.
Вот у нас есть какая-то последовательность.
Представим себе на мгновение, что она зациклена,
возьмем, сдвинем ее так по циклу и снова развернем.
Вот это и называется результатом применения циклического сдвига.
Ну там было, скажем, COCO, да?
Что значит сдвинули по циклу?
Это рассмотрели OCOC.
Вот было COCO, циклический сдвиг – это OCOC,
еще один циклический сдвиг – снова COCO, ну и так далее.
А если, скажем, была последовательность COCH,
то первый циклический сдвиг нам даст OCHC,
второй – CHCO, третий – HCOC
и четвертый – COCH.
Успеваете?
Ну смотрите, то есть в результате какого-то количества циклических сдвигов,
конечно, каждая последовательность возвращается в себя, правда ведь?
Ну понятно, что за n сдвигов она точно в себя вернется.
Но видите, иногда раньше, вот здесь не за 4 сдвига,
а за 2 сдвига она в себя вернулась.
Ну какая догадка?
Правильно, да, ну давайте я сейчас это аккуратно сформулирую.
Сначала введу еще одно определение, а потом мы поймем,
откуда здесь берутся делители числа n.