Функция Мёбиуса. Формула обращения Мёбиуса

Функция Мёбиуса натурального аргумента определяется следующим:образом:

Первые 13 значений

 

 

Далее символ означает, что суммирование распространяется на все натуральные делители числа .

Лемма.

Доказательство. Для утверждение очевидно. Пусть и − каноническое разложение числа . Тогда, учитывая, что делители имеют вид , где , ,…, ; , получаем

 

поскольку

Теорема. (Аддитивная формула обращения Мёбиуса.) Пусть и − функции натурального аргумента . Тогда, если

то

Доказательство. Имеем

Пусть . Тогда прификсированном пробегает все значения делителей числа . Это означает, что знаки суммирования в последней двойной сумме можно поменять местами, т.е.

Теперь, учитывая, что

получаем

Имеется другая форма доказанной теоремы:

Теорема. (Мультипликативная формула обращения Мёбиуса.) Пусть

где символ обозначает произведение, распространенное на все делители числа .

Тогда

Доказательство:

Примеры использования формулы обращения Мёбиуса:

. Задача о числе кольцевых последовательностей. См.: Холл М. Комбинаторика. М.: Мир, , § .

. Число неприводимых многочленов заданной степени над конечным полем из элементов. См.: Берлекэмп Э. Алгебраическая теория кодирования. − М.: Мир, 1970, Гл. 3.

Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. В -х т. М.: Гелиос, . Т. , § .

Для самостоятельного изучения:

Обращение Мёбиуса на частично упорядоченных множествах. Принцип включения-исключения как частный случай формулы обращения Мёбиуса. См.: Холл М. Комбинаторика. М.: Мир, , § ; Бендер Э., Гольдман Дж. О приложениях обращения Мёбиуса в комбинаторном анализе. В кн.: Перечислительные задачи комбинаторного анализа. М.: Мир, 1971. С. - .

Сравнения для чисел сочетаний

Пусть − простое число.

Лемма.

Доказательство. При числитель в формуле

Следствие.

Доказательство.

Лемма. Пусть , , , − неотрицательные целые числа, причем , . Тогда

Доказательство. Имеем

С другой стороны,

Сравнивая коэффициенты при одинаковых степенях , получаем требуемый результат. ∎

Пусть

, ;

,

− представления неотрицательных целых чисел и по основанию . (Здесь любое целое, при котором , ). На множестве неотрицательных целых чисел определим отношение частичного порядка (отношение предшествования) , полагая , тогда и только тогда, когда

, ,…,

Теорема Лукаса ( ).

Доказательство. Согласно предыдущей лемме,

где , . Применяя лемму повторно к надлежащее число раз, получаем требуемый результат. ∎

Замечание. Теорема не верна для непростых . Например (см. Берлекэмп, с. ),

Следствие.

II. Алгебраические структуры

II. 1. Множества с бинарными операциями. Группоиды, полугруппы, моноиды

Бинарной алгебраической операцией (или законом композиции) на непустом множестве S называется отображение : , сопоставляющее паре , элементов , однозначно определённый элемент , . На множестве может быть задано много операций . (Если, например, конечно, то число способов равно , где − число элементов в .) Желая выделить одну их них, например, , пишут , . Такой объект называют бинарной алгеброй, или группоидом. Вместо , часто пишут , а саму операцию обозначают каким-либо символом (, , , и т.п.).

Замечание. Наряду с бинарными операциями рассматривают более общие -арные операции (унарные при , тернарные при и т.д.). Связанные с ними алгебраические структуры (системы) составляют предмет исследования т.н. универсальных алгебр.

Бинарная операция на множестве называется ассоциативной, если

, для любых , , .

Группоид с ассоциативной операцией называют полугруппой.

Пример неассоциативного группоида. На множестве определим операцию как . Операция неассоциативна: , но .

Теорема. Если бинарная операция на множестве ассоциативна, то значение выражения не зависит от расстановки в нём скобок.

Доказательство. При , или утверждение очевидно. Для достаточно, применяя индукцию, показать, что

для любых , . По предположению индукции расстановка скобок в

не существенна; в частности, .

Если , то .

Если , то

.

К такому же виду приводится и правая часть доказываемого равенства (1). ∎

 

Элемент называется нейтральным относительно операции , если

для любого .

Полугруппу , с элементом называют моноидом (или полугруппой с единицей) и обозначают , , .

В полугруппе (группоиде) может быть не более одного нейтрального элемента: если

, − нейтральные элементы, то

Группоид (полугруппу) , называют подгруппоидом (подполугруппой) группоида (полугруппы) , , если

и для любых , .

В этом случае говорят, что подмножество замкнуто относительно операции . Моноид , , называют подмоноидом моноида , , , если выполняется и .

Элемент моноида , , называется обратимым, если найдётся элемент такой, что (очевидно, что тогда и обратим). Если таким же свойством обладает и элемент , т.е. , то из равенств следует, что элемент является на самом деле единственным (по отношению к ). Это позволяет говорить об обратном элементе , к(обратимому) элементу , со свойствами: , .

Если , − обратимые элементы моноида , , , то их произведение − также обратимый элемент, поскольку , . Очевидно, что − обратимый элемент. Следовательно, имеет место

Теорема. Множество всех обратимых элементов моноида , , замкнуто относительно операции ∗ и образует подмоноид в , , .

 

Группы

Определение группы. Моноид , , , все элементы которого обратимы, называется группой.

Другими словами, группа − это множество с бинарной операцией , для которых выполняются следующие аксиомы:

. (Замкнутость операции.) , .

. (Ассоциативность операции.) ,

. (Существование нейтрального элемента.) ∃ .

. (Существование обратного элемента.) .

Замечание. Возвращаясь к введённым выше алгебраическим структурам, мы наблюдаем среди них следующую иерархию: пара , является группоидом, если выполняется аксиома ; полугруппой, если выполняются аксиомы и ; моноидом, если выполняются аксиомы , и ; группой, если выполняются аксиомы , , и .

Удобно считать, что наряду с бинарной операцией в группе определена унарная операция взятия обратного : , . Справедливы формулы:

, .

Естественным образом определяются степени элементов с очевидными свойствами:

( раз),

( раз), ,

; , (, , .

Переставлять элементы в выражении , вообще говоря, нельзя (т.е. ). Если , то элементы называются перестановочными, или коммутирующими. Если любые два элемента группы коммутируют, то группа называется коммутативной, или абелевой (в честь норвежского математика Риль Хенрика Абеля ( - )).

Операция в группе чаще всего обозначается либо символом (сложение), либо символом (умножение). При этом группа называется соответственно аддитивной или мультипликативной, её нейтральный элемент − соответственно нулём () или единицей (). В аддитивной группе элемент, элемент, обратный к элементу , называется противоположным и обозначается , а вместо пишут . В мультипликативной группе вместо обычно пишут , опуская символ операции.

Примеры аддитивных групп. 1) , , , , , , , – аддитивные группы кольца и полей , , . Пишут просто , , , . 2) Любое кольцо по сложению − абелева группа. В частности, кольцо многочленов ,…, ] и кольцо матриц , порядка над полем − абелевы группы. 3) Любое векторное пространство над полем относительно сложения − абелева группа. 4) , 1,…, − полная система наименьших неотрицательных вычетов по модулю с операцией сложения по модулю .

Примеры мультипликативных групп. 1) , , − мультипликативные группы полей , , . 2) − множество обратимых элементов любого кольца с единицей относительно умножения. В частности, = ; , − множество обратимых матриц из . 3) − всех (вещественных и комплексных) корней

, , 1,…, , − мнимая единица,

уравнения − мультипликативная абелева группа. 4) − множество вращений правильного -угольника в плоскости и в пространстве − некоммутативная группа (при ).

 

Далее чаще используется мультипликативная форма записи операции. Группа обычно обозначается одной буквой без указания операции. Множество всех элементов группы называется основным множеством группы и обозначается той же буквой . Если основное множество конечно, то группа называется конечной; в противном случае она называется бесконечной. Число элемент конечной группы называется её порядком. Группа порядка 1 называется единичной, или т ривиальной. О бесконечной группе говорят, что она имеет бесконечный порядок. Для обозначения порядка группы (мощности основного множества) используются равноправные символы Card (кардинальное число), и ().

Если , − подмножества (основного множества) группы, то полагаем

, , .

Подгруппой группы называется подмножество в само являющееся группой относительно той же операции, что и в . Другими словами, подмножество является подгруппой тогда и только тогда, когда ( единица в ) и замкнуто относительно умножения и взятия обратного, т.е. , (на самом деле здесь даже равенства). Если − подгруппа в , то пишут ; если при этом , то называется собственной подгруппой и это обозначается как .

Примеры.