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

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

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

	1	2	3	4	5	6	7	8	9	10	11	12	13
	1			0		1		0	0	1		0

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

Лемма.

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

поскольку

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

то

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

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

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

получаем

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

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

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

Тогда

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

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

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

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

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

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

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

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

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

Лемма.

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

Следствие.

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

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

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

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

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

Пусть

, ;

,

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

, ,…,

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

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

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

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

Следствие.