Всем привет. Сейчас мы будем разбирать задачи четвертой недели курсеры. Курс основ iiI теории чисел. А-а-а, первая задача, она состоит в том, чтобы найти число циклических последовательностей. [ШУМ] Циклических последовательностей длины 6 над алфавитом из r символов. [ШУМ] [ШУМ] [ШУМ] [ШУМ] [ШУМ] Ну мы хотим, что сделать? Мы хотим э-э-э, пр, э-э-э, рассказать, то же самое доказательство, которое было на лекциях, только показать его на примере, когда n равно 6. А на лекциях оно было для произвольного r. Ну и я буду все время опускать фразу "алфавитом из r символов" подразумевая, что мы всегда всегда составляем только слова из r символов. Итак, начнем повторять доказательство. Значит, для начала мы обозначим через v это множество всех линейных последовательностей а-а-а, длины 6 над алфавитом из r символов. [ШУМ] [ШУМ] Вот это была по длине на лекциях, но сейчас я его немножко модифицирую, потому что мне так удобно. И поставлю здесь индекс 6, и буду считать, что у меня вообще v от n – это множество всех линейных последовательностей длины n. [ШУМ] Что мы дальше делаем на лекциях. Эти последовательности мы разбивали, значит эти последовательности мы разбивали на группы разного периода. А периодами могут быть любые последовательности, у которых, а-а-а, период делит число n, ну или в данном случай число 6. То есть период, периоды последовательностей из V n они могут равны делителям n. Ну, в частности для 6 это будут 1,2,3,6. [ШУМ] Ну и дальше, мы разбили множество всех линейных последовательностей длины n на множество разных периодов и написали вот такую формулу. Значит v n, количество элементов v n равно сумме по делителям числа n, а то б мы написали такое v от d. Где v от d, значит вот это v от d это множество последовательностей периода d, а мож, для этого естественно мощность это множества. То есть это последовательности периода d и длины n. Дальше мы воспользовались хитрым утверждением и перешли к последовательностям периода d и длины d. Это было w от d. [ШУМ] [ШУМ] Ну и сейчас, используя вот это вот это равенство, мы найдем все значения w от 1,2,3,6. Как мы это сделаем? Подставим n равно 1. [ШУМ] Так. Значит n равно 1. Значит мощность v 1 равна сумме по всем делителям единицы w от d. Так давайте тогда перейдем на ту доску, чтобы было удобно, чтобы места хватало. Значит, чему равно количество линейных последовательностей длины 1. Так у нас всего r символов, то мы можем составить ровно r последовательностей. И это, с другой стороны, равно, значит, в сумме по делителям единицы мощности v, w от 1, то есть просто w от 1. Так, отлично, значит, количество элементов w от 1 мы уже нашли. Давайте найдем количество элементов w от 2. Для этого мы напишем следующую цепочку равенств. Значит, если мы возьмем последовательность v 2, то их всего будет v в квадрате. А, с другой стороны, это равно сумме по всем делителям 2 мощности w от d. То есть это будет мощность w от 1 плюс мощность w от 2. Таким образом, мы отсюда можем найти мощность w от 2. Она равна r в квадрате минус мощность w от 1, то есть r. [ШУМ] Так, w от 2 равно r в квадрате минус r. Ну, аналогичным образом можно найти w от 3. Значит, r в кубе это у нас количество элементов в множестве v3, то есть в последовательности 3, оно равно в сумм, в сумме w от 1 плюс w от 3, потому что у 3 только делитель 1 и 3 ну и отсюда, w от 3 равно r в кубе минус r. Ну и осталось найти w от 6. Значит, для этого мы напишем такую большую цепочку равенств. R в 6 это у нас количество элементов v6, и это равно сумме на этот раз 4 слагаемых, потому что у 6 есть 4 делителя 1,2,3, и 6 и это будет вот такая сумма, w от 1 плюс w от 2, плюс w от 3 плюс мощность w от 6. Ну и отсюда, количество элементов, количество последовательностей, которые имеют длину 6 и период 6 оно равно значит r в 6 минус сумма вот этих трех количеств, которые мы уже нашли раньше: это r, r в квадрате минус r и r в кубе минус r. Значит, это будет минус r, минус r в квадрате минус r, минус r в кубе минус r. Ни и если раскрыть скобки и сократить подобные слагаемые, мы получим, что это равно r в 6 минус r в кубе, минус r в квадрате, а r у нас будет один раз с минусом, два раза с плюсом, значит будет плюс r. Так, значит, это мы нашли все значения w от d. количество элементов в множестве w от d. А теперь, чтобы найти на Tr от 6, мы приминем следующую формулу: Значит если мы рассмотрим циклические последовательности длины 6 над алфавитом из r символов, то мы можем их разбить на последовательности, которые имеют, которые соответствуют линейным последовательностям периода d. И это у нас обозначалось, сейчас я посмотрю, m от d. Значит это равно сумме по всем делителям n количеству элементов в множестве m от d. А это значит у нас циклические последовательности которые соответствуют а-а-а, собственному множеству v от d. Вот, а количество в каждом из этих множеств, оно равно мощности множества v от d делить на d. Ну, или, используя равенство, то, что мощность v от d она равна мощности w от d, можно записать вот такое равенство. Значит это будет сумма по делителям n, мощность w от d делить на d. Так, значит тут вместо n нужно поставить 6, сейчас аккуратненько это сделаю, [ШУМ] Ну и дальше подставить все найденные нами значения w от d. Значит это будет равно w от 1 на 1, плюс w от 2 на 2, плюс мощность w от 3 на 3 плюс мощность w от 6 на 6. Так, ну и аккуратно подставляем, что у нас происходит? Значит, количество iii w 1 это у нас r, r на 1 плюс значит, мощность w от 2 это вот она найдена, это r квадрат минус r. Пополам, так, плюс мощность w от 3 это r в кубе минус r, все это делим на 3. И, наконец, последнее слагаемое самое длинное – это количество элементов w от 6, деленное на 6. [ШУМ] Вот, ну и для красоты, можно это все привести к общему знаменателю. Что мы тут напишем? Значит, это будет 6r будем делить на 6 плюс 3 умножить на r в квадрате минус r – это мы умножили на 3. Это умножаем на 2 будет плюс 2 r в кубе минус r ну и плюс – продолжим сюда, вот это выражение, которое у нас было в самом начале. r в 6, минус r в кубе, минус r в квадрате плюс r. Ну и чему же это равно? Можно привести подобное и посчитать. Значит r в 6 так и останется r в 6. Так, дальше у нас будет, r в кубе, вот тут у нас встречается дважды, здесь мы его вычитаем один раз, значит будет один раз r в кубе. Так, r в квадрате, Здесь встречается три раза, а здесь минус 1, будет 2 r в квадрате? и еще осталось r посчитать, значит у нас здесь III получается 6 минус 3, минус 2, это будет r и еще плюс r. Плюс 2r. И все это делить на 6. Так, хорошо, значит ответ мы получили, давайте теперь проанализируем. Значит, вот эта формула, из 4 слагаемых, это ровно та знакопереме,это ровно та знакопеременная формула, которая получалась на лекциях с использованием функции Мёбиуса, а вот эта формула, которая написана в конце, это более краткий ее вариант, который можно посмотреть в iii задачах, это более удобная формула для использования, потому что здесь просто меньше слагаемых. Поэтому я всячески призываю вас ею пользоваться. Вот, задача решена.