Функция Мебиуса

Пусть (X, £) – конечное частично упорядоченное множество. Рассмотрим последовательность функций Pⁿ: X´X® Z, определенных при n =0 и n =1 по формулам:

А при n≥2:

Pⁿ(x,y) = |{(x₁ , x₂ , ×× ×, x_n-1): x< x₁ < x₂ < ××× < x_n-1 <y}|.

Определение 1. Функцией Мебиуса m: X´X®Z называется функция, определенная по формуле

.

Определение 2. Пусть X={ x₁ , x₂ , ×××, x_n} – конечное частично упорядоченное множество, матрицей смежности называется матрица A, имеющая коэффициенты

Лемма 1. Пусть X={ x₁ , x₂ , ×××, x_n} – конечное частично упорядоченное множество, A – матрица смежности. Тогда матрица M, коэффициенты которой равны значениям m(x_i, x_j), будет обратной к матрице A.

Доказательство. Пусть Id – единичная матрица. Положим Q=A-Id. Тогда A=Id+Q. Откуда

A^-1 = Id - Q + Q² - Q³ + ××× = .

Легко видеть, что коэффициенты матрицы Q^k равны P^k(x_i,x_j), откуда , в силу . Что и требовалось доказать.

Пример 1. X=[n].

Отсюда получаем m(i,i)=1, m(i,i+1)=-1. Остальные значения функции Мебиуса равны 0.