График мебиуса формула. Функция Мёбиуса
μ(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 Свойства и приложения … Википедия
Функция Мёбиуса μ(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,
Явная формула
Пример
Начальные значения чисел Стирлинга второго рода приведены в таблице:
Свойства
Биективным отображением называется отображение, обладающее признаками инъективности и сюръективности одновременно.
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( |
||||||||||
♦ Пусть (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′ |
d′ |
||||||||||||
d′ |
n > d′ |
||||||||||||
Но согласно (1) имеем ∑ |
|||||||||||||
µ (d′ ) = |
n = d′ |
||||||||||||
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′ |
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 ) |
|||||
где суммирование производится по всем 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) матрица инцидентности |
|||||||
множеств 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 |
|||||||||
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 |
||||
(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 с действительными, неотрицательными элементами называется дважды стохастической
, если Лемма.
Доказательство
.
Для утверждение очевидно. Пусть и − каноническое разложение числа . Тогда, учитывая, что делители имеют вид , где , ,…, ; , получаем поскольку Теорема.
(Аддитивная формула обращения Мёбиуса
.) Пусть и − функции натурального аргумента . Тогда, если Доказательство
.
Имеем Пусть . Тогда прификсированном пробегает все значения делителей числа . Это означает, что знаки суммирования в последней двойной сумме можно поменять местами, т.е. Теперь, учитывая, что получаем Имеется другая форма доказанной теоремы: Теорема
.
(Мультипликативная формула обращения Мёбиуса
.) Пусть где символ обозначает произведение, распространенное на все делители числа . Доказательство
: Примеры использования формулы обращения Мёбиуса
: Задача о числе кольцевых последовательностей. См.: Холл М. Комбинаторика. М.: Мир, , § . Число неприводимых многочленов заданной степени над конечным полем из элементов. См.: Берлекэмп Э. Алгебраическая теория кодирования. − М.: Мир, 1970, Гл. 3. Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. В -х т. М.: Гелиос, . Т. , § . Для самостоятельного изучения
: Обращение Мёбиуса на частично упорядоченных множествах. Принцип включения-исключения как частный случай формулы обращения Мёбиуса. См.: Холл М. Комбинаторика. М.: Мир, , § ; Бендер Э., Гольдман Дж. О приложениях обращения Мёбиуса в комбинаторном анализе. В кн.: Перечислительные задачи комбинаторного анализа. М.: Мир, 1971. С. - . Сравнения для чисел сочетаний
Пусть − простое число. Лемма.
Доказательство
. При числитель в формуле Следствие.
Доказательство
. Лемма.
Пусть , , , − неотрицательные целые числа, причем , . Тогда Доказательство
. Имеем С другой стороны, Сравнивая коэффициенты при одинаковых степенях , получаем требуемый результат. ∎ − представления неотрицательных целых чисел и по основанию . (Здесь любое целое, при котором , ). На множестве неотрицательных целых чисел определим отношение частичного порядка (отношение предшествования
) , полагая , тогда и только тогда, когда Теорема Лукаса ( ).
Доказательство
. Согласно предыдущей лемме, где , . Применяя лемму повторно к надлежащее число раз, получаем требуемый результат. ∎ Замечание.
Теорема не верна для непростых . Например (см. Берлекэмп, с. ), Следствие
. II. Алгебраические структуры
II. 1. Множества с бинарными операциями. Группоиды, полугруппы, моноиды
Бинарной алгебраической операцией
(или законом композиции
) на непустом множестве S
называется отображение :
, сопоставляющее паре , элементов , однозначно определённый элемент , . На множестве может быть задано много операций . (Если, например, конечно, то число способов равно , где − число элементов в .) Желая выделить одну их них, например, , пишут , . Такой объект называют бинарной алгеброй
, или группоидом
. Вместо , часто пишут , а саму операцию обозначают каким-либо символом ( , , , и т.п.). Замечание.
Наряду с бинарными операциями рассматривают более общие -арные операции (унарные при , тернарные при и т.д.). Связанные с ними алгебраические структуры (системы) составляют предмет исследования т.н. универсальных алгебр. Бинарная операция на множестве называется ассоциативной
, если , для любых , , . Группоид с ассоциативной операцией называют полугруппой
. Пример неассоциативного группоида.
На множестве определим операцию как . Операция неассоциативна: , но . Теорема.
Если бинарная операция на множестве ассоциативна, то значение выражения не зависит от расстановки в нём скобок. Доказательство.
При , или утверждение очевидно. Для достаточно, применяя индукцию, показать, что для любых , . По предположению индукции расстановка скобок в Не существенна; в частности, . Если , то . Если , то К такому же виду приводится и правая часть доказываемого равенства (1). ∎ Элемент называется нейтральным
относительно операции , если для любого . Полугруппу , с элементом называют моноидом
(или полугруппой с единицей
) и обозначают , , . В полугруппе (группоиде) может быть не более одного нейтрального элемента: если , − нейтральные элементы, то Группоид (полугруппу) , называют подгруппоидом
(подполугруппой
) группоида (полугруппы) , , если И для любых , . В этом случае говорят, что подмножество замкнуто относительно операции
. Моноид , , называют подмоноидом
моноида , , , если выполняется и . Элемент моноида , , называется обратимым
, если найдётся элемент такой, что (очевидно, что тогда и обратим). Если таким же свойством обладает и элемент , т.е. , то из равенств следует, что элемент является на самом деле единственным (по отношению к ). Это позволяет говорить об обратном
элементе , к(обратимому) элементу , со свойствами: , .
Если , − обратимые элементы моноида , , , то их произведение − также обратимый элемент, поскольку , . Очевидно, что − обратимый элемент. Следовательно, имеет место Теорема.
Множество всех обратимых элементов моноида , , замкнуто относительно операции ∗ и образует подмоноид в , , . Группы
Определение группы.
Моноид , , , все элементы которого обратимы, называется группой.
Другими словами, группа − это множество с бинарной операцией , для которых выполняются следующие аксиомы: . (Замкнутость операции
.) , . . (Ассоциативность операции
.) ,
. (Существование нейтрального элемента
.) ∃ .
. (Существование обратного элемента
.) .
Замечание.
Возвращаясь к введённым выше алгебраическим структурам, мы наблюдаем среди них следующую иерархию: пара , является группоидом
, если выполняется аксиома ; полугруппой
, если выполняются аксиомы и ; моноидом
, если выполняются аксиомы , и ; группой
, если выполняются аксиомы , , и . Естественным образом определяются степени элементов с очевидными свойствами: ( раз), ; , ( , , . Переставлять элементы в выражении , вообще говоря, нельзя (т.е. ). Если , то элементы называются перестановочными
, или коммутирующими
. Если любые два элемента группы коммутируют, то группа называется коммутативной
, или абелевой
(в честь норвежского математика Риль Хенрика Абеля ( - )). Операция в группе чаще всего обозначается либо символом (сложение), либо символом (умножение). При этом группа называется соответственно аддитивной
или мультипликативной
, её нейтральный элемент − соответственно нулём
() или единицей
(). В аддитивной группе элемент, элемент, обратный к элементу , называется противоположным
и обозначается , а вместо пишут . В мультипликативной группе вместо обычно пишут , опуская символ операции. Примеры аддитивных групп.
1) , , , , , , , – аддитивные группы кольца и полей , , . Пишут просто , , , . 2) Любое кольцо по сложению − абелева группа. В частности, кольцо многочленов ,…, ] и кольцо матриц , порядка над полем − абелевы группы. 3) Любое векторное пространство над полем относительно сложения − абелева группа. 4) , 1,…, − полная система наименьших неотрицательных вычетов по модулю с операцией сложения по модулю . Примеры мультипликативных групп.
1) , , − мультипликативные группы полей , , . 2) − множество обратимых элементов любого кольца с единицей относительно умножения. В частности, = ; , − множество обратимых матриц из . 3) − всех (вещественных и комплексных) корней , , 1,…, , − мнимая единица, уравнения − мультипликативная абелева группа. 4) − множество вращений правильного -угольника в плоскости и в пространстве − некоммутативная группа (при ). Далее чаще используется мультипликативная форма записи операции. Группа обычно обозначается одной буквой без указания операции. Множество всех элементов группы называется основным множеством группы
и обозначается той же буквой . Если основное множество конечно, то группа называется конечной
; в противном случае она называется бесконечной
. Число элемент конечной группы называется её порядком
. Группа порядка 1 называется единичной
, или тривиальной
. О бесконечной группе говорят, что она имеет бесконечный порядок
. Для обозначения порядка группы (мощности основного множества) используются равноправные символы Card (кардинальное число), и (). Если , − подмножества (основного множества) группы, то полагаем , , . Подгруппой
группы называется подмножество в само являющееся группой относительно той же операции, что и в . Другими словами, подмножество является подгруппой тогда и только тогда, когда ( единица в ) и замкнуто относительно умножения и взятия обратного, т.е. , (на самом деле здесь даже равенства). Если − подгруппа в , то пишут ; если при этом , то называется собственной
подгруппой и это обозначается как .