Функция Мёбиуса и её свойства

Пусть дан алфавит А из s букв. Имеется sn слов длины n в данном алфавите. Для каждого слова w0 = a1 a2 … an можно определить n — 1 слов w1 = a2a3 … ana1, w2 = a3a4 … a1a2 , … , wk-1 = an a1 … an-1, получаемых один из другого циклическими сдвигами. На множестве всех sn слов введем отношение эквивалентности: два слова объявим эквивалентными, если один из другого получается циклическим сдвигом. Нас будут интересовать число классов, которые содержат точно n слов. Такая задача возникает в теории синхронизирующих кодов.
Будем называть слово w вырожденным, если класс эквивалентности, содержащий w, состоит из менее, чем n слов. Назовем w периодическим, если существует слово u и натуральное число m, такое, что w = u u … u (m раз).
Теорема 2. Слово w периодическое тогда и только тогда, когда оно вырождено.
Ясно, что если w периодическое, то оно вырождено. Пусть w вырождено. Пусть p — минимальное целое, такое, что w = wp. Тогдаеслиw = a1 a2 … an, тоwp = a1+p a2+pan+p (индексыпомодулю n). Отсюда получаем, что в качестве u можно взять a1 a2 … ap, а в качестве m= np.
Обозначим через M(d) — число квадратов, которые содержат d слов. Из предыдущего имеем d n. Таким образом, справедлива формула:
d/ndMd= sn
Применим формулу обращения Мебиуса для случая g(n) = sn, f(d) =dM(d). Тогда получаем
nMn= d/nμdsnd2
или
Mn=1nd/nμdsnd.
Таким образом, M(n) — интересующее нас число. Если n = p — простое число, то
Mp=1p(sp-s)
Имеется мультипликативный вариант обращения Мебиуса.
Теорема 3. Пусть f(n) и g(n) — функции натурального аргумента, связанные соотношениями
fn=d/ng(d)
Тогда g(n) = d/nf(d)μ(nd)
Обратное утверждения также верно.
Таким образом в данном пункте была рассмотрена одна из важнейших формул связанных с функцией Мёбиуса, а именно формула обращения. Данная формула имеет множество применений в различных разделах математики.