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

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 11Следующая ⇒

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

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

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

Лемма.

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

поскольку

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

то

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

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

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

получаем

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

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

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

Тогда

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

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

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

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

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

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

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

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

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

Лемма.

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

Следствие.

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

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

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

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

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

Пусть

, ;

,

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

, ,…,

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

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

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

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

Следствие.

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

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

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

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

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

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

Если , то .

Если , то

.

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

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

для любого .

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

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

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

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

и для любых , .

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

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

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

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

Группы

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

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

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

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

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

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

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

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

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

, , .

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

Примеры.

Познавательные статьи:



Техника нижней прямой подачи мяча

Комплекс физических упражнений для развития мышц плечевого пояса

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов