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

Лемма.

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

поскольку

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

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

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

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

получаем

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

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

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

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

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

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

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

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

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

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

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

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

Лемма.

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

Следствие.

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

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

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

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

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

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

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

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

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

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

Следствие .

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

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

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

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

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

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

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

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

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

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

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

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

Если , то .

Если , то

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

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

для любого .

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

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

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

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

И для любых , .

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

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

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

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

Группы

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

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

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

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

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

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

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

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

( раз),

; , ( , , .

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

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

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

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

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

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

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

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

, , .

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

1. Напомним сначала определение важной теоретико-числовой функции Мебиу-

1, если n = 1

µ (n)=0, если существует простое число p, p2 n (-1)k , если n = p1 … pk - произведение k различных простых множителей.

Докажем основное свойство функции Мебиуса:

Теорема 1.

♦ Если n = 1, то единственный делитель d = 1 и (1) верно, т.к. µ (1) = 1. Пусть теперь n > 1. Представим его в виде

n = p1 s 1 ps 2 2 K ps k k ,

где pi , i 1, k - простые числа, si - их степени. Если d - делитель n, то d = p1 d 1 pd 2 2 K pd k k ,

где 0 ≤ di ≤ si , i 1, k . Если di > 1 для некоторого i 1, k , то µ (d) = 0. Значит в (1) нужно рассмотреть только такие d, для которых di ≤ 1, i 1, k . Каждый такой делитель со-

стоит из произведения r различных простых чисел, где r 1, k , причем его вклад в сумму

(1) равен (-1)r и всего их k . Таким образом, получаем


	µ (d) = 1 −	K + (− 1) k	0. ♦



	Теорема 2. (Формула обращения Мебиуса). Пусть f(n) и g(n) - функции нату-
рального аргумента. Тогда равенство
			∑ f(d)

справедливо тогда и только тогда, когда справедливо равенство
			∑ µ (d)g(
			∑ µ (d)g(

♦ Пусть (2) справедливо для любого n. Тогда

g(d n ) = ∑ f(d′ )

d ′ d n

Подставляя в правую часть (3), получаем

∑ µ (d)g(	) = ∑ µ (d) ∑ f(d′ )

		d′

Двойное суммирование справа проводится по всем парам d, d′ , таким, что d d′ n . Если выбрать d′ , то d будет пробегать все делители d n ′ . Таким образом

∑ µ (d)g(

) = ∑ f(d′ ) ∑ µ (d′ )

d′

n > d′

Но согласно (1) имеем ∑

µ (d′ ) =

n = d′

d′

Значит, равенство (3) установлено. Пусть теперь (3) справедливо для любого n. Тогда

∑ f(d) =

∑ ∑ µ (d′ )g(

) , d′′ = d d ′ - является делителем n и двойная сумма может

d′

n d′

быть переписана в виде

∑ µ (d′ )g(d′′ ) =

∑ g(d′′ )

∑ µ (d′ )

d ′′

n d ′

d ′′

d′

d ′′

Согласно (1) последняя сумма превращается в единицу в случае d′′ = n, в остальных слу-

чаях она есть ноль. Это доказывает (2). ♦ 2. Рассмотрим приложение обращения Мебиуса.

Пусть дан алфавит А из s букв. Имеется sn слов длины n в данном алфавите. Для каждого слова w0 = a1 a2 … an можно определить n - 1 слов

w1 = a2 a3 … an a1 , w2 = a3 a4 … a1 a2 , … , wk-1 = an a1 … an-1 , получаемых один из другого циклическими сдвигами. На множестве всех sn слов введем отношение эквивалентности: два слова объявим эквивалентными, если один из другого получается циклическим сдвигом. Нас будут интересовать число классов, которые содержат точно n слов. Такая задача возникает в теории синхронизирующих кодов.

Будем называть слово w вырожденным, если класс эквивалентности, содержащий w, состоит из менее, чем n слов. Назовем w периодическим, если существует слово u и натуральное число m, такое, что w = u u … u (m раз).

Теорема 3. Слово w периодическое тогда и только тогда, когда оно вырождено.

качестве u можно взять a 1 a 2 … a p , а в качестве m =

♦ Ясно, что если w периодическое, то оно вырождено. Пусть w вырождено. Пусть p - минимальное целое, такое, что w = wp . Тогда если

w = a1 a2 … an , то wp = a1+p a2+p … an+p (индексы по модулю n). Отсюда получаем, что в n p . (Легко видеть, что p n). ♦ Обо-

значим через M(d) - число квадратов, которые содержат d слов. Из предыдущего имеем

d n. Таким образом, справедлива формула ∑ dM(d) = s n . d n

Применим формулу обращения Мебиуса для случая g(n) = sn , f(d) = dM(d). Тогда получаем

nM(n) = ∑ µ (d)s n d d n

∑ µ (d)sn d

Таким образом, M(n) - интересующее нас число. Если n = p - простое число, то

− s)

Имеется мультипликативный вариант обращения Мебиуса. Справедлива

Теорема 4. Пусть f(n) и g(n) - функции натурального аргумента, связанные соот-

ношениями

f(n) = ∏ g(d)

µ(n

g(n) = ∏ f(d)

и обратно, из (5) следует (4).

Используя формулу обращения Мебиуса, можно решить важную в практическом отношении задачу о числе неприводимых многочленов фиксированной степени над конечным полем. Пусть GF(q) - поле из q элементов и m - натуральное число. Тогда для числа

Φ m (q) неприводимых многочленов над полем GF(q) справедлива формула

Приведем таблицу нескольких первых значений функции Φ m (2)


Φ m (2)

§ 5. Перманенты и их применение к перечислительным

1. Для решения многих комбинаторных задач используются перманенты. Рассмотрим числовую матрицу

A = (ai , j), i = 1, n , j = 1, m , n ≤ m

Перманент матрицы А (обозначение - per А) определяется равенством

per A = ∑			a 2 j L a nj
(j1 ,K , jn )
(j1 ,K , jn )

где суммирование производится по всем n-перестановкам из m элементов 1, 2, m. Другими словами, перманент матрицы равен сумме произведений элементов, взятых по одному из каждой строки и разных столбцов.

Из формулы (1) следуют некоторые очевидные свойства перманента, аналогичные свойствам определителя для квадратных матриц.

1. Если одна из строк (n× m)-матрицы А (n ≤ m) состоит из нулей, то per A = 0. При n = m то же верно и для столбцов.

2. При умножении всех элементов одной из строк матрицы А на некоторое число значение перманента А умножается на то же число.

3. Перманент не меняется при перестановке ее строк и столбцов.

Обозначим через Aij - матрицу, полученную из А вычеркиванием i-ой строки и j-го столбца.

4. Справедлива формула разложения перманента по i-ой строке per A = ai1 per Ai1 + ai2 per Ai2 + ... + aim per Aim (2)

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

Однако, основное свойство определителей det(A B) = detA detB не выполняется для перманентов, и это обстоятельство сильно затрудняет их вычисление.


Например,


	2, per


Однако, 4 = per		≠ per

рассмотрим одно из важнейших применений понятия перманента в комбинаторных за-

дачах. Пусть X = {x1 , xm } - конечное множество, а X1 , … , Xn - система подмножеств

При этом говорят, что элемент xi представляет множество Xi . Необходимость нахождения системы различных представителей возникает при решении многих прикладных задач. Рассмотрим следующую задачу кодирования. Пусть имеется некоторое предложение, т.е. упорядоченный набор слов в некотором алфавите. Требуется закодировать данное предложение так, чтобы каждому слову ставилась в соответствие одна буква, причем эта буква должна входить в состав этого слова, а разным словам должны соответствовать разные буквы.

Пример: Предложение a bc ab d abe c de cd e можно закодировать как abecd. В то же время, предложение ab ab bc abc bcd не может быть закодировано подобным образом, поскольку первые четыре слова в совокупности содержат только три буквы.

Для системы множеств X1 , … , Xn определим матрицу инцидентности A = (aij ), i = 1, n ,


	1, если xi
a ij =
	0, в противном случае.
Справедлива
Теорема 1. Пусть A = (aij ), i =		(n ≤ m) матрица инцидентности
Теорема 1. Пусть A = (aij ), i =		(n ≤ m) матрица инцидентности

множеств X1 , … , Xn , где Xi X, i = 1, n , X = {x1 , … , xm } . Тогда для числа систем раз-

личных представителей R(X1 , … , Xn ) множеств X1 , … , Xn справедливо равенство

R(X1 , … , Xn ) = per A

♦ Действительно, поскольку в матрице А элемент aij = 1 , если xj Xi и aij = 0 ,

если xj

K , xi

) элементов X является системой различных пред-

Xi , то набор (xi

ставителей для X1 , … , Xn

в том и только в том случае, когда a1i

K ,a ni

менты a1i

K ,a ni

находятся в разных столбцах матрицы А. Суммируем числа

a1i ,K ,a ni

по всем n-перестановкам элементов 1, 2, … , m. Тогда получим с одной сто-

роны число систем различных представителей для X1 , … , Xn , а с другой - значение пер-

манента матрицы А. ♦

a 1i 1 a 2i 2 L a ni n

Следствие. Система различных представителей для X1 , … , Xn существует тогда и только тогда, когда для соответствующей матрицы инциденция А выполнено:

Поскольку в формуле (1) m(m - 1) … (m - n +1) членов, то вычисление перманента на основе определения затруднительно. Приведем для этой цели общую формулу.

2. Ограничимся рассмотрением квадратных числовых матриц А = (aij ), i, j = 1, n .

Тогда per A = ∑

(i1 ,K ,in )

где сумма распространяется по всем перестановкам i1 , … , in элементов

1, 2, … , n. Применим формулу включения-исключения для вычисления перманента матрицы А. Каждому набору i1 , … , in поставим в соответствие вес , равный a1i 1 ,K ,a ni n .

Значит перманент А - это сумма весов тех наборов, которые соответствуют перестановкам. Введем n свойств P1 , … , Pn на множестве всех наборов i1 , i2 , … , in из 1, 2, … , n, где свойство Pi означает, что в наборе i1 , … , in нет элемента i. Таким образом, перманент А - это сумма весов наборов i1 , … , in , не обладающих ни одним из свойств P1 , … , Pn . Осталось определить сумму весов W(Pi 1 ,K , Pi k ) наборов, обладающих k свойствами

Pi 1 ,K , Pi k . Имеем для суммы весов W(0) всех наборов i1 , … , ik .
W(0) = ∑		K , a ni	= (a 11 + L + a 1n )(a 21 + L + a 2n ) L (a n1 + L + a nn )
i1 ,K ,in
i1 ,K ,in

W(N(Pi )) =		a1i ,K , a ni		= (a 11 + L + a 1i	L + a1n )L (a n1 + L a ni + L + a nn ) (9)

	≠i

где знак ^ над элементом матрицы А означает, что этот элемент следует опустить. Аналогично для sij (i < j) имеем


W(N(Pi , Pj )) = (a11 + L + a1i	L +a 1j	L + a1n )L (a n1 + L a ni + L + a nj + L + a nn ) (10)

Теперь, используя формулу включения-исключения, получаем формулу Райзера для перманента А:


per A = ∏ i n = 1 (ai1 + L + ain ) − ∑∏ k n = 1 (a k1 + L + a ki + L + a kn )+ L +

+ (− 1)s	∑∏n
+ (− 1)s	∑∏n	(a k1 + L + a ki1	L +a ki	L +a kn ) +L
	1≤ i1 < L < is ≤ k n= 1

Вычисление перманента по формуле Райзера можно организовать так, что потребуется

(2n - 1)(n - 4) умножений и (2n - 2)(n + 1) сложений. Хотя эта величина растет быстро с ростом n, данная формула дает наиболее эффективный способ вычисления перманентов.

3. Выясним теперь вопрос об условиях равенства нулю перманента (0, 1)-матрицы. Ограничимся случаем квадратной матрицы.

Теорема 2. Пусть A = (aij ), i, j = 1, n - (0, 1)-матрица порядка n. Тогда

per A= 0 в том и только в том случае, когда в А существует подматрица из нулей размера s × t, где s + t = n + 1.

♦ Пусть такая нулевая подматрица в А существует. Поскольку перманент не меняется от перестановок строк и столбцов, то можно считать, что эта подматрица расположена в левом нижнем углу, т.е.

где О - (s × t) - матрица из нулей, подматрица B имеет размер (n - s) × t. Любой член перманента А должен содержать по одному элементу из первых t столбцов. Поэтому, если искать положительный член перманента, то элементы этих столбцов должны принадлежать попарно различным строкам с номерами 1, 2, … , n - s. Однако n - s = t - 1 < t и поэтому данное условие выполнить нельзя, т.е. per A = 0.

Пусть теперь per A = 0. Доказательство теоремы проводим индукцией по n. При n = 1 утверждение очевидно (А = (0)). Пусть оно справедливо для всех порядков, меньших n. Если А - нулевая матрица порядка n, то утверждение очевидно. Если А - не нулевая матрица, то пусть aij = 1. Запишем разложение А по строке i:

per A = ai1 Ai1 + … + ain Ain

Поскольку per А = 0, то per Аij = 0. Но Аij имеет размер (n - 1) × (n - 1) и по предположению индукции для нее существует подматрица из нулей размера

s1 × t1 , причем s1 + t1 = n - 1 + 1 = n. Переставим строки и столбцы так, чтобы эта нулевая подматрица оказалась в нижнем левом углу:


A → B =

где О - нулевая подматрица размера s1 × t1 , s1 + t1 = n, С - имеет размер (n - s1 ) × t1 , D -

имеет размер s1 × (n - t) . Значит, матрицы С и D - квадратные и имеют порядок (t1 × t1 ) и (s1 × s1 ) соответственно. Согласно определению перманента имеем per B = per A и,

per B = per C per D и поэтому из per А = 0 следует, что либо per C = 0, либо per D = 0.

Пусть per C = 0. По предположению индукции в С найдется нулевая подматрица размера

u × v, где u + v = t1 + 1. Пусть она расположена в строках с номерами i1 , … , iu и столбцами с номерами j1 , … , jv . Рассмотрим подматрицу B, состоящую из строк

i1 , … , iu , t1 + 1, … , n и столбцов j1 , … , jv . Это нулевая подматрица размера (u + n - t1 ) × v,

где u + n - t1 + v = n + +1. Итак, в матрице B указана нулевая подматрица размера s × t, где s + t = n + 1. Так как матрицы А и B отличаются перестановкой строк и столбцов, то теорема доказана. ♦

Рассмотрим теперь важный частный случай матрицы А. Обозначим через А(k, n) - матрицу из элементов 0,1 размера n × n с k единицами к каждой строке и каждом столбце (k > 0).

Теорема 3. Для любой матрицы А(k, n) справедливо per А(k, n) > 0.

♦ Допустим противное, что per А(k, n) = 0. Тогда по теореме 2 существует нуле-

вая подматрица размера s × t, где s + t = n + 1. Тогда, переставляя строки и столбцы матрицы А(k, n) получим матрицу

где О - нулевая (s × t)-матрица.

Подсчитаем число единиц в матрицах B и D. Поскольку A(k, n) имеет k единиц в каждой строке и каждом столбце, то в каждом столбце B и каждой строке D имеется точно k

единиц. Всего в А(k, n) имеется n k единиц, поэтому nk ≥ tk + sk = (t + s)n. Таким обра-

зом, n ≥ t + s, что невозможно, т.к. s + t = n + 1 Из данного противоречия следует спра-

ведливость утверждения. ♦ Аналогично доказывается

Теорема 3а. Пусть А - (0,1)-матрица размера n× m (n≤ m). Тогда perА = 0 в том и только в том случае, когда содержит нулевую подматрицу размера s× t, где s+t=m+1.

4. Рассмотрим теперь приложение рассматриваемых вопросов к построению ла-

тинских квадратов. Латинским (n × m)-прямоугольником над множеством X={x1 ,…,xm }

называется (n× m) -матрица из элементов X, в которой каждая строка есть n-перестановка X, а каждый столбец есть m-перестановка множества X. При n=m латинский прямоугольник называется латинским квадратом.

Ясно, что при n=1 число латинских 1× m прямоугольников равно m!. При n=2 после того, как выбрана первая строка, в качестве второй можно взять любую переста-

новку, противоречащую выбранной. Число таких перестановок Dm , поэтому число 2× m -

латинских прямоугольников равно m! Dm .

Возникает естественный вопрос в связи с индуктивным построением латинских квадратов. Пусть мы построили латинский (n× m)-прямоугольник (n< m). Можно ли его расширить до ((n+1)× m) -прямоугольника добавлением (n+1)-й строки?

Справедлива

Теорема 4. Всякий латинский (n× m) -прямоугольник n

♦ Пусть X={x1 ,…,xm } и L- латинский (n× m)-прямоугольник с элементами из X. Рассмотрим набор множеств A1 ,… ,Am где Ai - элементы i -го столбца латинского прямоугольника L. Пусть А - матрица инцидентности системы множеств A1 ,… ,Am . Она имеет размер m× m , и каждая строка матрицы А содержит точно n единиц, поскольку Ai = n, i = 1, m . Каждый элемент xi X может появиться в столбцах L не более m раз, иначе нашлась бы строка, в которой этот элемент встретится дважды. Общее число элементов

L равно m n, поэтому каждый элемент xi X появляется в столбцах точно n раз. Отсюда следует, что и каждый столбец матрицы А содержит точно n единиц. Рассмотрим теперь матрицу A , полученную заменой каждой единицы на нуль и каждого нуля на единицу.

Матрица A есть матрица инциденций системы множеств X1 , … , Xn , где Xi = X\Ai ,

i = 1, m . Она содержит по m - n единиц в каждой строке и в каждом столбце. По теореме

> 0. Пусть ai1

… a mi

≠ 0 . Тогда имеем xi X1 ,K , xi

Xm и все элементы

xi ,K , xi

попарно различны. Строка

xi ,K , xi

может быть взята в качестве (n + 1)-ой

для латинского (n × m)-прямоугольника L. Продолжая эту процедуру, получим латин-

ский квадрат. ♦

Обозначим l n - число латинских квадратовпорядка n, с элементами из множества X = {1, 2, … , n}, у которых элементы первого столбца и первой строки идут в естественном порядке. Приведем таблицу нескольких известных значений числа l n :

5. Матрица A = (aij ) размера n × n с действительными, неотрицательными элементами называется дважды стохастической , если

μ(n ) определена для всех натуральных чисел n и принимает значения в зависимости от характера разложения числа n на простые сомножители:

μ(n ) = 1 если n свободно от квадратов (т.е. не делится на квадрат никакого простого числа) и разложение n чётного числа сомножителей;
μ(n ) = − 1 если n свободно от квадратов и разложение n на простые множители состоит из нечётного числа сомножителей;
μ(n ) = 0 если n не свободно от квадратов.

По определению также полагают μ(1) = 1 .

Свойства и приложения

Функция Мёбиуса мультипликативна: для любых взаимно простых чисел a и b выполняется равенство μ(a b ) = μ(a )μ(b ) .

Сумма значений функции Мёбиуса по всем делителям целого числа n , не равного единице, равна нулю

Style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/1bee8d0f6bd91176912a8cedc63e174b.png" border="0">

Отсюда, в частности, следует, что для всякого непустого конечного множества количество различных подмножеств состоящих из нечётного числа элементов равно количеству различных подмножеств состоящих из чётного числа элементов - факт, применяемый в доказательстве .

Функция Мёбиуса связана с функцией Мертенса отношением

Функция Мертенса в свою очередь тесно связана с задачей о нулях дзета-функции Римана , см. статью гипотеза Мертенса.

Обращение Мёбиуса

Первая формула обращения Мёбиуса

Для арифметических функций f и g ,

g (n ) =	∑	f (d )
	d \| n

тогда и только тогда, когда

Вторая формула обращения Мёбиуса

Для вещественнозначных функций f (x ) и g (x ) , определеных при ,

тогда и только тогда, когда

Здесь сумма интерпретируется как .

Wikimedia Foundation . 2010 .

Смотреть что такое "Функция Мебиуса" в других словарях:

Функция Мёбиуса μ(n) мультипликативная арифметическая функция, применяемая в теории чисел и комбинаторике, названа в честь немецкого математика Мёбиуса, который впервые рассмотрел её в 1831 г. Содержание 1 Определение 2 Свойства и приложения … Википедия

Вид преобразований на комплексной плоскости (серая) и сфере Римана (чёрная) Содержание 1 Определение 2 Алгебраические свойства … Википедия

Дробно линейная функция функция вида где z = (z1,...,zn) комплексные или вещественные переменные, ai,b,ci,d комплексные или вещественные коэффициенты. Часто термин «дробно линейная функция» используется для её частного случая преобразования… … Википедия

Ряд Мёбиуса функциональный ряд вида Этот ряд был исследован Мёбиусом, который нашел для этого ряда формулу обращения: где μ(s) функция Мёбиуса … Википедия

МЕТОДЫ ВРАЧЕБНОГО ИССЛЕДОВАНИЯ - І. Общие принципы врачебного исследования. Рост и углубление наших знаний, все большее, и большее техническое оснащение клиники, основанное на использовании новейших достижений физики, химии и техники, связанное с этим усложнение методов… … Большая медицинская энциклопедия

Патологическое состояние, развившееся во время родов и характеризующееся повреждениями тканей и органов ребенка, сопровождающимися, как правило, расстройством их функций. Факторами, предрасполагающими к развитию Р. т.н., являются неправильное… … Медицинская энциклопедия

Функция Мебиуса  (n ), гдеn – натуральное число, принимает следующие значения:

Функция Мебиуса позволяет записать функцию Эйлера в виде суммы:

Суммирование идет по всем делителям n(а не только по простым делителям).

Пример. Вычислимφ (100), используя функцию Мебиуса.

Все делители 100 – {1, 2, 4, 5, 10, 20, 25, 50, 100}.

(2) = (-1) 1 = -1 (у двойки один простой делитель – 2)

(4) = 0 (4 делится на квадрат двойки)

(5) = (-1) 1 = -1 (у 5 один простой делитель – 5)

(10) = (-1) 2 = 1 (у 10 два простых делителя – 2 и 5)

(20) = 0 (20 делится на квадрат двойки)

(25) = 0 (25 делится на квадрат пятерки)

(50) = 0 (50 делится и на 2 2 , и на 5 5)

(100) = 0 (100 делится и на 2 2 , и на 5 5)

Таким образом,

Свойство функции Мебиуса: .

Например, n =100, {1, 2, 4, 5, 10, 20, 25, 50, 100}.

16 Теорема о числе способов выбора k-элементов, среди которых нет двух соседних, из n элементов, расположенных в ряд. Доказать с помощью получения рекуррентной формулы.

17 Число сочетаний с повторениями

Число r -сочетаний с повторениями изn -множества равно

– доказательство с помощью рекуррентной формулы.

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

Рекуррентная формула r -го порядка – формула вида

a n = f (n , a n- 1 , a n- 2 , … , a n-r ).

Формула выражает при n>r каждый член последовательности {a i } через предыдущиеr членов. Построение рекуррентной формулы состоит из следующих шагов.

1. Выработка начальных условий исходя из каких-либо очевидных соотношений.

Обозначим черезf (n,r ). Очевидно, что

2. Логические рассуждения. Зафиксируем какой-либо элемент во множествеS . Тогда относительно любогоr -сочетания с повторениями изn -множестваS можно сказать, содержит ли оно данный зафиксированный элемент или нет.

Если содержит , то остальные (r -1) элемент можно выбратьf (n ,r -1) способами.

Если не содержит (в выборке этого элемента нет), тоr -сочетание составлено из элементов (n -1)-множества (множествоS за исключением данного зафиксированного элемента). Число таких сочетанийf (n -1,r ).

Т.к. эти случаи взаимоисключающие, то по правилу суммы

3. Проверка формулы на некоторых значениях и вывод общей закономерности .

1) Вычислим f (n ,0) . Из (2) следует

Тогда f (n ,0)=f (n ,1)-f (n -1,1). Из (1)f (n ,1)=n, f (n -1,1)=n -1.

Следовательно, f (n ,0)=n -(n -1)=1=.

2) f (n ,1) =f (n ,0)+f (n -1,1) = 1+n- 1 =n ==.

3) f (n ,2) =f (n ,1)+f (n -1,2) =n +f (n -1,1)+f (n -2,2) =n +(n -1)+f (n -2,1)+f (n -3,2) = … =

= n +(n -1)+…+2+1 =.

(сумма арифметической прогрессии)

4) f (n ,3) =f (n ,2)+f (n -1,3) =+f (n -1,2)+f (n -2,3) =++f (n -2,2)+f (n -3,3) = … =

(сумма геометрической прогрессии)

5) f (n ,4) =

На основе частных случаев можно предположить, что

4. Проверка начальных условий с помощью полученной формулы.

что согласуется с (1) #

19, 20) Число бинарных деревьев с n вершинами равно C(n), где C(n) – это n-ое число Каталана.

Количество бинарных деревьев из n вершин называется числом Каталана, которое обладает множеством интересных свойств. N-ое число Каталана считается по формуле (2n)! / (n+1)!n!, которая растёт экспоненциально. (В Википедии предложено несколько доказательств, что это форма числа Каталана.) Число бинарных деревьев данного размера 0 1 1 1 2 2 4 14 8 1430 12 208012 16 35357670

Подстановка

Перейти к: навигация , поиск

Это статья о подстановке как о синтаксической операции над термами . Возможно, вас интересует перестановка .

В математике и компьютерных науках подстановка - это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной .

Определения и обозначения

Для подстановки не существует универсальной, согласованной нотации, равно как и стандартного определения. Понятие подстановки варьируется не только в рамках разделов, но и на уровне отдельных публикаций. В целом, можно выделить контекстную подстановку и подстановку «вместо» . В первом случае место в терме, где происходит замена, задаётся контекстом , то есть частью терма, «окружающим» это место. В частности, такое понятие подстановки используется в переписывании . Второй вариант более распространён. В этом случае подстановка обычно задаётся некоторой функцией из множества переменных в множество термов. Для обозначениядействия подстановки , как правило, используют постфиксную нотацию . Например, означает результат действия подстановкина терм.

В подавляющем большинстве случаев требуется чтобы подстановка имела конечный носитель, то есть, чтобы множество было конечным. В таком случае её можно задать простым перечислением пар«переменная-значение» . Поскольку каждую такую подстановку можно свести к последовательности подстановок, замещающих всего по одной переменной каждая, не ограничивая общности можно считать, что подстановка задаётся одной парой «переменная-значение» , что обычно и делается.

Последнее определение подстановки является, видимо, самым типичным и часто используемым. Однако и для него не существует единой общепринятой нотации. Наиболее часто для обозначения подстановки a вместо x в t используется запись t [a /x ], t [x :=a ] или t [x ←a ].

Подстановка переменной в λ-исчислении

В λ-исчислении, подстановка определяется структурной индукцией. Для произвольных объектов ,и произвольной переменнойрезультат замещения произвольного свободного вхождениявсчитаетсяподстановкой и определяется индукцией по построению :

(i) базис: : объектсовпадает с переменной. Тогда;

(ii) базис: : объектсовпадает с константой. Тогдадля произвольных атомарных;

(iii) шаг: : объектнеатомарный и имеет вид аппликации. Тогда;

(iv) шаг: : объектнеатомарный и является-абстракцией. Тогда [;

(v) шаг: : объектнеатомарный и является-абстракцией, причем. Тогда:

для иили;

Подстановка переменной в программировании

Подстановка переменной (англ. substitution ) в аппликативном программировании понимается следующим образом. Для вычисления значения функции f на аргументе v применяется запись f(v) }, где f определена конструкцией f(x) = e . Запись f(v) в этом случае означает, что в выражении e происходит замещение , или подстановка переменной x на v . Выполнение замещения происходит в соответствии с семантикой вычислений .

Подстановка переменной (англ. assignment ) в программировании понимается как присваивание . Оператор присваивания является проявлением эффекта «бутылочного горлышка» фон Нейманна для традиционных языков программирования . От этого свободны аппликативные вычислительные системы .

http://math.nsc.ru/LBRT/u3/bard/fails/Brenner_Evans.pdf

21 Производящие функции. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний без повторений.

Производящие функции: 1)Z-преобразования 2)генератриса 3)порождающая функция 4)производящая функция последовательности {a r } на базисе {g r } – функция f при разложении которой в ряд по функциям фиксированного базиса {g r } образуется данная последовательность коэффициентов {a r } …………*)

Данный ряд – формальный. Название формальный означает, что мы формулу *) трактуем как удобную запись нашей последовательности – в данном случае несущественно, для каких (действ и комплексных) значений он сходится. Роль t сводится к тому чтобы различать коэффициенты последовательности А0,А1,…Аr….поэтому в теории производящих функций никогда не вычисляют значения таого ряда для конкретного значения переменной t. Выполняются лишь только некоторые операции на таких рядах, а затем определяются только некоторые операции на таких рядах а затем определяются коэффициенты при отдельных степенях переменной t.

Обычно в качестве

22 Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний с повторениями.

Производящая ф-я для :

Правило построения

1)Если эл-т типа i может входить в сочетания K 1 или K 2 или… K i раз, то ему соотв множитель

3)Остается найти коэф. при

экспоненциальная производящая ф-я для размещений правило построения

25) К комбинаторным числам также относятся числа Стирлинга первого и второго рода. Эти числа определяются как коэффициенты в равенствах

и имеют простой комбинаторный смысл - равно числу элементов группы подстановок являющихся произведениями ровно k непересекающихся циклов, а равно числу разбиений n- элементного множества на k непустых подмножеств. Очевидно, что. Аналогичная сумма чисел Стирлинга второго рода называется n -м числом Белла и равна числу всех разбиений n -элементного множества. Для чисел Белла справедлива рекуррентная формула.

При решении комбинаторных задач часто оказывается полезна формула включений-исключений

позволяющая находить мощность объединения множеств, если известны мощности их пересечений. Воспользуемся формулой включений-исключений для получения явной формулы для чисел Стирлинга второго рода.

Числа Стирлинга первого рода

Материал из Википедии - свободной энциклопедии

Перейти к: навигация , поиск

Числа Стирлинга первого рода (без знака) - количество перестановок порядка n с k циклами .

Определение

Числами Стирлинга первого рода (со знаком) s(n, k) называются коэффициенты многочлена :

где (x ) n - символ Похгаммера (убывающий факториал ):

Как видно из определения, числа имеют чередующийся знак. Их абсолютные значения задают количество перестановок множества, состоящего из n элементов с k циклами .

Рекуррентное соотношение

Числа Стирлинга первого рода задаются рекуррентным соотношением:

s (n ,n ) = 1, для n ≥ 0,

s (n ,0) = 0, для n > 0,

для 0 < k < n .

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

Для n =1 это равенство проверяется непосредственно. Пусть перестановка (n -1)-го порядка распадается на k циклов. Число n можно добавить после любого числа в соответствующий цикл. Все полученные перестановки - различные и содержат k циклов, их количество (n -1)·s (n -1, k ). Из любой перестановки (n -1)-го порядка, содержащей k -1 цикл, можно сформировать единственную перестановку n порядка, содержащую k циклов, добавив цикл образованный единственным числом n . Очевидно, что эта конструкция описывает все перестановки n -го порядка, содержащие k циклов. Тем самым равенство доказано.

Пример

Первые ряды:

В комбинаторике числом Стирлинга второго рода из n по k , обозначаемым или, называется количество неупорядоченныхразбиений n -элементного множества на k непустых подмножеств.

Рекуррентная формула

Числа Стирлинга второго рода удовлетворяют рекуррентному соотношению:

Для n ≥ 0,

Для n > 0,

Явная формула