Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 59
Костин В. А.. Конкретная математика. Лекции 2004.
Санкт-Петербургский государственный
университет
Математико-механический факультет
В. А. Костин
Конкретная математика
(Лекции 2004, фрагменты)
Санкт-Петербург
2004
09.05.2004
Докажем, что число счастливых 2n-значных трамвайных билетов равно
.
Билет считается счастливым, если сумма первых n цифр его номера равна сумме n последних цифр, например, билет с номером 764395 – счастливый шестизначный билет.
Упражнение. Докажите, что функция от параметра n, вычисляющая число счастливых 2n-значных трамвайных билетов, примитивно рекурсивна.
Доказательство (леммы).
Рассмотрим равенство (1+z+…+z9)n=, тогда аi определяет количество n-значных чисел, сумма цифр которых равна i.
Нам нужно вычислить .
Имеем (1+z+…+z9)n(1+z-1+…+z-9)n==,
тогда b0=.
(1+z+…+z9)n(1+z-1+…+z-9)n==.
Известно, что =.
Пусть z=ei=cos+isin, тогда b0===.
Преобразуем =
=
==.
Таким образом,
b0===.
При доказательстве тех или иных комбинаторных тождеств часто используется одно или одновременно два из следующих правил:
Правило суммы. Если объект А может быть выбран m способами, а объект В другими n способами, то выбор “либо А, либо В” может быть осуществлен m+n способами.
Правило произведения. Если объект А может быть выбран m способами и после каждого из таких выборов объект В в свою очередь может быть выбран n способами, то выбор “А, и В” в указанном порядке может быть осуществлен mn способами.
Примеры. На основе этих правил в курсе математического анализа легко были получены формулы для числа k-перестановок и числа k-сочетаний из n объектов, а именно
= n(n-1)…(n-k+1)
=
Упражнение. Докажите, что число k-перестановок из n объектов с повторениями равно nk.
Задача. Доказать, что число k-сочетаний из n объектов с повторениями равно .
Решение (Л. Эйлер): Пусть X={1,2,…n} и рассмотрим любое из k-сочетаний с повторениями с1с2…сk этих n чисел (считаем, что в сочетании с1с2…сk элементы выписаны в неубывающем порядке). Естественно, что в каждом сочетании вследствие возможности неограниченных повторений любые рядом стоящие элементы могут быть одинаковыми. Ввиду этого обстоятельства строим с помощью соотношений
d1=c1+0; d2=c2+1;…; di=ci+i-1;…; dk=ck+k-1
последовательность элементов d1d2…dk следовательно, при любых элементах ci элементы di всегда различны. Ясно, что отображение с1с2…сk в d1d2…dk биективно. Число последовательностей из элементов di равно числу k-сочетаний без повторений из элементов от 1 до n+k-1, т. е. .
Производящие функции для сочетаний.
Для примера рассмотрим три объекта, обозначенные x1, x2, x3. Образуем произведение
(1+x1t)(1+ x2t)(1+x3t).
Перемножив и разложив это произведение по степеням t, получим
1+(x1+x2+x3)t+(x1x2+x1x3+x2x3)t2+x1x2x3t3,
или
1+а1t+а2t2+а3t3,
где а1, а2, а3 – элементарные симметрические функции трех переменных x1, x2, x3. Эти симметрические функции определяются вышеприведенным выражением. Можно заметить, что число слагаемых каждого коэффициента аm (m=1,2,3) равно числу сочетаний из трех элементов по k. Следовательно, число таких сочетаний получается приравниванием каждого xi единице, т. е.
(1+t)3=
Для случая n различных объектов, обозначенных x1, . . . , xn ясно, что
(1+x1t)(1+ x2t) . . . .(1+xnt)=
=1+a1(x1,. . ., xn)t+ a2(x1,. . ., xn)t2+. . .+ an(x1,. . ., xn)tn
и
(1+t)n==;
поэтому выражение (1+t)n называют перечисляющей функцией сочетаний из n различных объектов. Этот результат можно также обосновать следующими комбинаторными рассуждениями:
В произведении (1+x1t)(1+ x2t) . . . .(1+xnt) каждый множитель является биномом, который благодаря наличию в нем слагаемых 1 и xi указывает на возможность наличия или отсутствия в каждом из сочетаний элемента xi. Это произведение порождает сочетания, так как коэффициент при tm в нем получается выбором “1” в n-m из n двучленных множителей и в m оставшихся после такого выбора множителях - членов вида xit всеми возможными путями. Эти коэффициенты по самому их определению являются m-сочетаниями. Каждый элемент в любом сочетании может появляться не более одного раза, ибо любой множитель состоит только из двух слагаемых.
Обобщая эти комбинаторные рассуждения, для случая, когда прежние множители вида 1+xit заменяются множителями вида 1+xt+xt2+ … +xtj, построим производящую функцию для сочетаний, в которых элементы xi могут содержаться 0,1,2,…,j раз. Более того, множители производящей функции можно совершенно независимо друг от друга приспосабливать к любым требованиям задачи. Так, например, если xk должно всегда входить четное число раз, но не более чем 2k раз, то k-й множитель следует выбирать в виде
1+xt+xt4+ … +xt2k .
Таким образом, производящая функция для любой задачи описывает не только виды элементов, но и виды искомых сочетаний.
Пример. Для сочетаний с неограниченным повторением элементов n и без ограничения на число появлений любого элемента перечисляющей производящей функцией будет
(1+t+t2+. . .)n
или, что же самое
(1-t)-n = ==.
Упражнение. 1. Постройте производящую функцию для сочетаний с повторениями, в которых каждый элемент входит, по крайней мере, один раз.
2. Постройте производящую функцию для сочетаний с повторениями, в которых любой элемент обязательно появляется в сочетании, но только четное число раз.
Производящие функции для перестановок.
В случае коммутативных алгебраических операций произведения х1х2 и х2х1 одинаковы. Поэтому производящую функцию, описывающую перестановки, невозможно построить так, как это было сделано для сочетаний. В случае n различных элементов из соотношения p(n,m)=”число m-перестановок” вытекает, что (1+t)n = , т. е. в разложении выражения (1+t)n число p(n,m) является коэффициентом при . Этот факт указывает пути обобщения.
Если какой-либо элемент может появляться 0,1,…,k раз или если существует k элементов данного вида, то множитель 1+t в левой части равенства заменяется множителем 1+t++…+. Это объясняется тем, что число перестановок из n элементов, p из которых одного вида, q другого и т. д., равно
.
Это число оказывается коэффициентом при в произведении
, n=p+q+…,
что в точности соответствует необходимым требованиям.
Определение и простейшие свойства производящих функций.1
Определение. Обычной производящей функцией для последовательности a0,a1,… называется формальная сумма
A(t)=a0+a1t+a2t2+ … antn+… . (1)
Экспоненциальной производящей функцией для той же последовательности называется сумма
Е(t)=a0+a1t+a2t2/2!+ … antn/n!+… . (2)
В связи с этими определениями необходимо сделать несколько замечаний. Во-первых, элементы последовательности a0,a1,…, как видно, из самих обозначений, упорядочены, но не обязательно должны быть различны. Во-вторых, переменная t производящей функции никак не определена.
На производящих функциях можно определить формальные операции, такие как сложение, умножение, дифференцирование и интегрирование по t, и выявить зависимости в этой алгебре, в частности путем приравнивания коэффициентов при степенях tn после выполнения этих операций. С этой точки зрения неуместно ставить вопрос о сходимости соответствующих рядов.
Алгебра степенных рядов A(t), определяющих производящие функции, известна под именем алгебры Коши, а алгебра степенных рядов E(t), определяющих экспоненциальные производящие функции, известна как символическое исчисление Блиссара. В статистике функция E(t) фигурирует как производящая функция моментов; E(t) используется также в теории чисел.
В комбинаторике неизбежно возникают производящие функции, отличные от А(t) или E(t), например, сумма вида
G(t)= a0f0(t)+a1f1(t)+a2f2(t)+ … anfn(t)+…, (*)
для которой единственным требованием является линейная независимость функций f0(t), f1(t),…(для того чтобы сделать выражение однозначным). A(t) и E(t) являются частными случаями этого выражения.
Наконец, для любителей операций над непрерывными переменными следует отметить, что аналогом обычной производящей функции с одной переменной служит несобственный интеграл
А(t)=
Этот факт, по-видимому, более известен для случая экспоненциального ядра е-tk, т. е. для преобразования Лапласа
А(t)=
Выражение, включающее в себя как частные случаи оба приведенные выше интеграла и степенные ряды, представляет собой интеграл Стильтьеса
А(t)=,
в котором t – параметр. Чтобы получить сумму (1), в качестве функции F(t,k) выбираем ступенчатую функцию. Эта функция имеет скачки при к=0,1,2,…; скачок в точке k равен tk.
Некоторые простейшие производящие функции.
|
ak |
A(t) |
E(t) |
|
ak |
(1-at)-1 |
Exp at |
|
k |
t(1-t) |
t exp t |
|
k(k-1) |
2t2(1-t)-3 |
t2 exp t |
|
k2 |
t(t+1)(1-t)-3 |
t(t+1) exp t |
|
c |
(1+t)n |
- |
|
n(n-1)…(n-k+1) |
- |
(1+t)n |
Упражнение. Докажите справедливость приведенных формул.
Элементарные соотношения между обычными производящими функциями.
Обозначим через A(t), B(t), C(t) производящие функции, соответствующие последовательностям (ак), (bк), (cк), тогда в качестве непосредственного следствия из самого определения последовательности (а) получаем две пары соотношений; в каждой паре выполнение одного из соотношений влечет за собой выполнение второго
Сумма ак=bк+cк
A(t)=B(t)+C(t)
Произведение ак=bкc0+bк-1c1+…+b1cк-1+b0cк
A(t)=B(t)C(t)
Последовательность (ак) называется сверткой (bк) и (cк), если A(t)=B(t)C(t). Сумма и произведение обладают свойствами коммутативности и ассоциативности.
Для экспоненциальных производящих функций соответствующие соотношения определяются следующим образом:
Пусть E(t), F(t), G(t) экспоненциальные производящие функции, соответствующие последовательностям (eк), (fк), (gк), тогда
Сумма eк=fк+gк
E(t)=F(t)+G(t)
Произведение eк=fкg0+fк-1g1+…+f1gк-1+f0gк
E(t)=F(t)G(t)
Решение линейных рекуррентных уравнений.
Пример. Найдем производящую функцию к числам Фибоначчи: F0=F1=1, Fn+2=Fn+Fn+1, n0.
Производящая функция F(t) для последовательности F(0),F(1),F(2),… удовлетворяет уравнению
F(t)==1+t+=
1+t+t2+t=
1+t+t2F(t)+x(F(t)-1)= 1+(t+t2)F(t),
т. е. F(t)=(1-t-t2)-1.
Найдя корни уравнения 1-t-t2=0, получаем разложение
1-t-t2=(1-аt)(1-bt), где а=(1+5)/2, b==(1-5)/2.
Используя метод неопределенных коэффициентов, найдем
=+
т. е.
F(t)=A(1-at)-1+B(1-bt)-1=A+B=tk
и
Fk=+
Замечание. этот метод можно перенести на произвольное линейное уравнение с постоянными коэффициентами.
Задача 1. Пусть задана последовательность Фибоначчи
F0=F1=1, Fn+2=Fn+Fn+1, n0.
Рассмотрим множество последовательностей из нулей и единиц длины n, в которых нет двух рядом стоящих единиц. Пусть таких последовательностей A(n). Тогда А(n)=Fk+1.
Доказательство.
Имеем А(0)=1, так как существует только одна – пустая, такая последовательность; А(1)=2, так как существует две такие последовательности – ‘0’ и ‘1’.
Заметим, что число последовательностей длины n, у которых на n месте находится нуль, равно А(n-1).
Все последовательности длины n+1 могут быть построены из последовательностей длины n приписыванием к каждой из них на n+1 место нуля и, кроме того, тем из них, которые на n месте имеют ноль, можно также приписать единицу. Таким образом, А(n+1)=A(n)+A(n-1)=Fn+1+Fn=Fn+2.
Задача 2. n>0 А(n)==.
Доказательство.
А(n) можно получить следующим образом:
Заметим, что каждая такая последовательность длины n может содержать не более [(n+1)/2] единиц. Подсчитаем, сколько существует последовательностей, содержащих k единиц, 0k[(n+1)/2]. Если последовательность имеет к единиц, то она содержит n-k нулей. Рассмотрим последовательность из n-k нулей. Тогда в этой последовательности имеется n-k+1 мест для расстановки k единиц. Т. е. общее число требуемых последовательно
стей длины n,содержащих k единиц, равно . Таким образом,
A(n)= .
Производные сложных функций (Формула Бруно)
Сложная функция – это функция от функции. Ей можно придать стандартную форму экспоненциальной (или обычной) производящей функции, воспользовавшись ее производными. Выражая производную сложной функции через ее компоненты, приходим к некоторой совокупности полиномов – полиномов Белла, – характерных для многих комбинаторных и статистических задач.
Положим
А(t)=f[g(t)] (1)
и
A(t)=An, [f(u)]u=g(t)=fn, g(t)=gn, где Dt=d/dt, Du=d/du
Затем последовательным дифференцированием (1) получим
А1=f1g1
А2=f1g2+f2
А3=f1g3+ 3f2g2g1+f2
В общем виде можно записать
Аn=f1An1+ f2An2+…+f2Ann=
=An,k(g1, g2,… gn) (2)
Отметим, что коэффициенты An,k зависят только от производных g1, g2,… gn и не зависят от fk. Следовательно, они могут быть определены специальным выбором f; удобно положить f(u)=exp(au), где а – постоянная. Тогда
fk=аk exp(ag), g=g(t)
и
e-ageag=ΣAn,k(g1, g2,… gn)ak=
An(a, g1, g2,… gn), (3)
где вторая строка – сокращенная запись первой
В этих обозначениях (2) принимает вид
Аn=An(a, g1, g2,… gn), fk≡fk, (2a)
где
А0=f0=A(t)
Соотношение (3) полностью определяет полиномы An(a,g1,g2,…gn) и с помощью (2а), – производные An. Можно заметить, что в обозначениях Белла
An(1, y1, y2,… yn)=Yn(y1, y2,… yn)=e-yey,
y≡y(x).
С целью получения явного выражения для полиномов Белла обозначим кратко
An(a, g1, g2,… gn)
через Аn(a) и используем формулу Лейбница для дифференцирования произведения
Аn+1(a)=e-agDn(Deag)=
=a-agaDn(g1 eag)=
=а(e-agDn-keag)Dkg1=
=аAn-k(a)gk+1=
=ag(A(a)+g)n; (A(a))k≡Ak(a), gk≡gk (4)
Частными случаями соотношения (4) при А0(a)=1 являются соотношения
А1(a)=ag1
А2(a)=ag2+ag1А1(a)=ag2+a2
А3(a)=ag3+ 2ag2А1(a)+ag1А2(a)= ag3+ 3a2g2g1+a3,
что согласуется с результатами, предшествующими (2)
Далее, соотношение (4) влечет за собой соотношение для экспоненциальной производящей функции
exp(uA(a))=(a)un/n!=
=exp(a[ug1+u2g2/2!+…])=
=exp(aG(U), (5)
в котором
G(u)=exp(ug) – g0, gn≡gn
Дифференцированием (5) и приравниванием коэффициентов при un получаем (4).
Наконец, раскрывая (5) с помощью полиномиальной теоремы и приравнивая коэффициенты при un получаем искомую формулу
Аn(a)= , (6)
в которой k1 +k2+…+kn=k и сумма берется по всем решением в неотрицательных целых числах уравнения k1 +2k2+…+nkn=n, или по всем разбиениям n. Отсюда, имея в виду (2а), получаем соотношение, известное как формула Бруно
Аn=Аn(f)= (5а)
Замечание. Если A(t) разлагается в ряд Тейлора, т. е. если
A(t+u)=exp(uA(t)), An(f)≡An(f),
то
=An(f) при t=0,
A(t)= exp(uA0), (A0)n≡.
Числа Стирлинга первого и второго рода.
Обозначение. (t)n=t(t-1)…(t-n+1).
Числа Стирлинга определяются следующим образом. Положим
(t)0=t0=s(0,0)=S(0,0)=1
(t)n=t(t-1)…(t-n+1)=, n>0 (1)
tn=, n>0. (2)
Тогда s(n,k) и S(n,k) называются числами Стирлинга соответственно первого и второго рода. Заметим, что числа обоих рядов отличаются от нуля только для k=1,2,…,n, n>0 и что (t)n является обычной производящей функцией для s(n,k), тогда как tn является новым типом производящей функции для входящей в уравнение (*) функции fk(t), равной (t)k.
Упражнение. Докажите, что совокупность функций {(t)0,(t)1,…,(t)n} линейно независима.
Для заданного n или k числа Стирлинга первого рода s(n,k) могут иметь тот или иной знак, действительно
(-t)n=(-1)nt(t+1)…(t+n-1),
тогда из (1) немедленно следует, что (-1)n+ks(n,k) всегда положительно. Кроме того, учитывая вид производящей функции Сn(t), получаем С(n,k)=(-1)n+ks(n,k). Т. е модули чисел Стирлинга первого рода s(n,k) определяют число перестановок n-го порядка с k циклами.
Рекуррентные соотношения для чисел Стирлинга первого рода s(n k) вытекают из соотношения для факториалов (t)n=(t-n+1) (t)n-1, т.е.
s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k).
Для чисел Стирлинга второго рода, используя (2), находим
tn==t=
и
S(n+1,k)= S(n,k-1)+k S(n,k). (3)
С числами Стирлинга второго рода можно связать разбиения конечных множеств, а именно:
Пусть Х={1,2,…,n}, рассмотрим всевозможные разбиения Х на k блоков. Множество таких разбиений будем обозначать Пk(X), пусть u(n,k)=|Пk(X)|, тогда
u(0,0)=1 u(n,k)=u(n-1,k-1)+ku(n-1,k). (4)
Доказательство.
Разобьем Пk(X) на два различных класса:
Мощность первого класса равна u(n-1,k-1). Т. е. такова, каково число разбиений множества {1,2,…,n-1} на k-1 блоков.
Мощность другого класса составляет ku(n-1,k), так как каждому разбиению множества {1,2,…,n-1} на k блоков соответствует в этом классе в точности k разбиений, образованных добавлением элемента n поочередно к каждому блоку.
Следствие. Сравнивая (3) и (4), получаем S(n,k)=u(n,k), т. е.
Числа Стирлинга 2-го рода S(n,k) определяют число разбиений n-элементного множества на k дизъюнктных блоков.
Исходя, из соотношения 3 легко построить таблицу для чисел Стирлинга 2-рода при небольших значений n и k:
|
n\k |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
3 |
0 |
1 |
3 |
1 |
0 |
0 |
0 |
|
4 |
0 |
1 |
7 |
6 |
1 |
0 |
0 |
|
5 |
0 |
1 |
17 |
25 |
10 |
1 |
0 |
|
6 |
0 |
1 |
31 |
65 |
15 |
1 |
0 |
Теорема. Числа Стирлинга 2-го рода удовлетворяют тождеству
S(n,k) = , k≥2
Доказательство
Обозначим ) всех множество разбиений Х={1,2…,n} на k дизъюнктных подмножеств. Это множество распадается на различные классы, соответствующие разным подмножествам множества Х, которые являются блоками, содержащими элемент n. Отметим, что каждого b-элементного множества BХ, содержащего элемент n, существует в точности S(n-b,k-1) разбиений множества X на k блоков, содержащих B в качестве блока. Действительно, каждое такое разбиение однозначно соответствует разбиению X\B на k-1 блоков. b-элементное множество BХ, содержащее элемент n, можно выбратьспособами; таким образом,
S(n,k) = ==
Число Белла βn определяется как число разбиений n-элементного множества, т. е. βn=||=, другими словами
βn=
Теорема. Справедливо следующее тождество: βn=.
Доказательство.
Принимаем β0=1. проведем комбинаторное доказательство тождества, аналогичное предыдущему.
Множество всех разбиений множества Х={1,2,…,n+1} можно разбить на различные классы в зависимости от блока В, содержащего элемент n+1, или – что равнозначно – в зависимости мощности Х\В. Для каждого множества Х\В {1,2,…,n} существует в точности || = β|х\в| разбиений множества Х, содержащих В в качестве блока. Группируя наши классы в зависимости от мощности множества Х\В, получаем требуемое тождество.
Теорема. Пусть |X|=n, |Y|=k, то число всех функций f:XY и f(X)=Y, равно Sn,k=k!S(n,k).
Доказательство.
Зафиксируем конкретное разбиение Х на k дизъюнктных подмножеств, тогда существует k! вариантов отображений, при которых каждому элементу разбиения сопоставляется биективно элемент Y. Каждое конкретное разбиение можно выбрать S(n,k) способами.
Представление перестановок в циклической форме.
Во многих приложениях удобно представлять перестановки в циклической форме.
Пример. Разложение перестановки на циклы.
Пусть f=<5 7 3 1 6 4 2>=, тогда эту перестановку можно записать так
1à5à6à4
2à7
3
Каждый цикл выписан на отдельной строчке. Внутри цикла следующим выписывается элемент перестановки, являющийся образом в f текущего, т. е. xàf(x). Образ последнего элемента совпадает с первым. В этом примере первым в каждом цикле выписан элемент с наименьшим номером внутри цикла, a циклы расположены в порядке возрастания первых элементов
Рассмотрим некоторые свойства разложений на циклы и введем дополнительные обозначения.
Пусть перестановка f содержит k циклов следующего вида:
, для i=1,...,k,
Каждому такому циклу соответствует перестановка fi = [], называемая также циклом длины ni, которая определяется следующим образом:
fi()=,...,fi()=; fi(x)=x для xÏ {}.
Перестановку f можно представить в виде суперпозиции циклов
f = .
Например, f = <7 5 1 4 2 3 6>, тогда f = [1,7,6,3]×[2,5]×[4].
Замечание. 1. Элементы внутри одного цикла можно циклически переставлять местами.
Например: [1,7,6,3]=[7,6,3,1]=[6,3,1,7]=[3,1,7,6].
Теорема 1. Общее число циклов во всех n! перестановках
n-го порядка равно n!´Hn, где Hn=.
Доказательство. Пусть все n! перестановок записаны в циклической форме. Зафиксируем i, 1£i£n, и рассмотрим, сколько циклов длины i встречается во всех этих перестановках.
Заметим, что конкретный цикл [a1,...,ai] встречается в (n-i)! перестановках, так как это число способов, которыми можно переставить оставшиеся n-i элементов. Число различных возможных циклов [a1,...,ai] есть n´(n-1)´¼´(n-i)/i, так как элемент a1 можно выбрать n способами, элемента a2 - (n-1) способами и т. д.; а среди n´(n-1)´¼´(n-i+1) циклов из a1,...,ai фиксированных элементов появляется i раз, как [а1,...,аi], [a2,...,ai,a1],...,[ai,a1,...,ai-1]. Поэтому общее число циклов из i элементов во всех n! перестановках есть n´(n-1)´¼´(n-i+1)/i, взятое (n-i)! раз, т. е. n!/i.
Суммируя по всем i, получаем общее число циклов во всех n! перестановках =n!´Hn.
Определение. Будем говорить, что перестановка, представленная в виде разложения на циклы, находится в канонической форме, если:
а) обязательно записываются все циклы;
б) в каждом цикле первым записывается элемент с наименьшим значением;
в) циклы располагаются в порядке убывания значений первых элементов.
Например, f=[3 1 6 7]×[5 4] представляется как [4 5]×[2]×[1 6 7 3].
Скобочная структура в канонической форме может быть опущена, так как первым элементам циклов соответствуют левосторонние минимумы ( ak, ikn, является левосторонним минимумом f, если ak<ai, 1i<k).
В приведенном примере перестановка f может быть записана как (4 5 2 1 6 7 3), где круглые скобки указывают, что перестановка представлена в канонической циклической форме.
Упражнение. Пусть f=<a1 ... an>, g=(a1 ... an),n1. Докажите, что fg.
Рассмотрим производящую функцию Сn(t)=, определяющую число перестановок n-го порядка, имеющих k циклов, т. е. С(n,k) определяет число перестановок n-го порядка, имеющих k циклов. Тогда
C(0,0)=1,
C(n,0)=0, при n>0,
C(n,k)=0, при к>n,
Для n>0, C(n,k)=С(n-1,k-1)+(n-1)C(n-1,k) или Cn(t)=(t+n-1)Cn-1(t).
Докажем последнее утверждение.
Все ниже рассматриваемые перестановки представлены в канонической циклической форме. Заметим, что если максимальное число в такой перестановке расположено на первом месте, то оно образует отдельный цикл (так как оно является левосторонним минимумом и следующее за ним число также левосторонний минимум). Если же оно расположено на любом другом месте, то оно входит в какой-то цикл длины, большей единицы. Перестановка n-го порядка, содержащая k циклов, может быть получена либо добавлением n на первое место в перестановку (n-1)-го порядка, содержащую k-1 цикл, либо добавлением n в перестановку(n-1)-го порядка, содержащую k циклов, на любое место со второго до n-го.
Следствие. Учитывая, что C1(t)=t, получаем
Cn(t)=t(t+1)…(t+n-1).
Цикловые классы (типы).
Определение. Будем говорить, что перестановка P{1,2,…,n} имеет тип <>, если P имеет k1 циклов длины 1, имеет k2 циклов длины 2, и т. д. Заметим, что = n.
Пусть С(k1, k2,…, kn) есть число перестановок из n элементов типа k=<>.
Выясним, какова формула, определяющее общее число таких перестановок. Для того чтобы найти эту формулу выберем произвольную перестановку типа k и переставим ее элементы всеми возможными n! способами. Имеется две причины, в силу которых не все получившиеся в результате этой операции перестановки оказываются различными: (а) все циклы, в которых входят одни и те же элементы в одном и том же циклическом порядке, не отличаются друг от друга; (b) относительное расположение циклов в перестановке несущественно.
Как уже отмечалось, r-цикл может начинаться с любого из входящих в него r элементов, и, следовательно, имеется возможность (в силу a) получить r дубликатов этого цикла. Общее число дубликатов составит . Далее, если число r-циклов равно kr, то их можно переставлять kr! способами, поэтому (в силу b) окажется дубликатов k1!· k2!·…· kn!.
Следовательно,
С(k1, k2,…, kn)=, где k1 +2k2+…+nkn=n. (1)
Примеры.
|
тип |
перестановки |
число |
|
<> |
(123); (132) |
2 |
|
<> |
(12)(3); (13)(2); (1)(23) |
3 |
|
<> |
(1)(2)(3) |
1 |
2. Число перестановок типа <> равно n!/n= (n-1)!
Эта формула проверяется с помощью следующего соображения: в n-цикле первым элементом по условию является 1, а для расстановки оставшихся n-1 элементов существует (n-1)! возможностей.
3. Единственная перестановка типа <> совпадает с тождественной перестановкой.
Производящая функция чисел С(k1, k2,…, kn) должна иметь вид многочлена от многих переменных, так как n видов циклов должны независимыми. Этот факт выражается соотношением
Сn(t1, t2,…, tn)=ΣС(k1, k2,…, kn)
Следовательно, с учетом (1)
Сn(t1, t2,…, tn)= (2)
Сумма (2) берется по всем неотрицательным целым числам от k1 до kn таким, что k1 +2k2+…+nkn=n, или, что то же самое, по всем разбиением числа n. Функция Сn(t1, t2,…, tn) называется цикловым индикатором (указателем) симметрической группы.
Для первых значений n имеем:
С1(t1) =t1
С2(t1, t2)=+t2
С3(t1, t2, t3)=+3t1t2+2t3
С4(t1, t2, t3, t4)= +6t2+3+8t1t2+6t4
Удобно принять С0=1.
Из сопоставления соотношений (2) и (6) следует
Сn(t1, t2,…, tn)=An(1; t1, t2, 2! t3,…, (n-1)!tn)=
= Yn(t1, t2, 2! t3,…, (n-1)!tn) (3)
Последнее выражение является следствием соотношения (2а) при соответствующем изменении буквенных обозначений. В силу (5), это то самое, что и основное порождающее тождество:
exp(uC)= (t1, t2,…, tn)un/n!= exp(ut1+u2t2/2+u3t3/3+…) (3a)
весьма удобное для дальнейшей работы.
Свойства Сn(t1, t2,…, tn)
Это согласуется с (3а), так как
exp(ut1+u2t2/2+u3t3/3+…) =exp(log(1-u)-1 )=(1-u)-1 =1+u+u2+…
следует из 1, учитывая (2)
3.Введенная ранее производящая функция числа перестановок n-го порядка Cn(t) может быть получена из Сn(t1, t2,…, tn), если все tr приравнять t, т.е.
Сn(t)=Сn(t, t,…, t)
Следовательно, из (3а) имеем
exp(uC(t))= = exp(t(u+u2/2+u3/3+…) = exp(t·log(1-u)-1=(1-u)-t=
=1+ (4)
что согласуется с ранее полученными результатами для Сn(t).
Перестановки без единичных циклов
Каково число перестановок из n элементов, каждая из которых состоит из k циклов, отличных от единичных.
Ясно, что ответ на этот вопрос по самому определению функции Сn дается коэффициентом при tk в выражении для Сn(0, t,…, t), или для краткости dn(t). На основании соотношения (3а)
exp(ud(t))= = exp(t(u2/2+u3/3+…) =(1-u)-t exp(-tu) (5)
откуда, сравнивая с (4), получаем
dn(t)= Cn-k(t)(-t)k , (6)
где C0(t)=1, Cn(t)=t(t+1)…(t+n-1), n>0, как и ранее.
Тогда если
dn(t)=,
то соотношение для коэффициентов, вытекающее из (6), окажется следующее:
d(n,k)= (-1)j C(n-j,k-j) (7)
Ввиду (7) числа d(n,k) называются присоединенными числами Стирлинга первого рода. Следует отметить, что соотношением, двойственным соотношению (6), полученным умножением (5) на etu и приравниванием коэффициентов при un является
Cn(t)= dn-j(t)(t)j.
Последний результат соответствует любопытному представлению чисел Стирлинга
С(n,k)= (-1)j d(n-j,k-j). (8)
Теперь полученный ответ формально является полным, однако существуют более простые зависимости. Так путем дифференцирования (5) по u получаем [ при обычном условии d(t)n≡dn(t)], что
d(t)exp(ud(t))=−t exp(ud(t))+t(1−u)-1exp(ud(t)) (9)
или
(1−u)d(t)exp(ud(t))=tu exp(ud(t)).
Это соответствует соотношению
dn+1(t)=n dn(t)+ntdn-1(t), (10)
что в свою очередь соответствует простому рекуррентному соотношению
d(n+1,k)=nd(n,k) +nd(n-1,k-1), (11)
которое также может быть получено простым комбинаторным рассуждением.
Разбиение чисел.2
Пусть n – натуральное число и n=b1+b2+…+bk, где k, b1,b2,…,bk>0, при этом будем считать суммы эквивалентными, если они отличаются только порядком слагаемых. Класс эквивалентных сумм можно представить однозначно последовательностью a1,a2,…,ak, где a1≥a2≥…≥ak, и числа a1,a2,…,ak являются числами b1,b2,…,bk, упорядоченными по невозрастанию. Каждую такую последовательность a1,a2,…,ak будем называть разбиением числа n на k слагаемых.
Замечание. Если в сумме b1+b2+…+bk порядок слагаемых считается существенным, то такие представления числа n обычно называются композицией числа n на k слагаемых.
Число разбиений числа n на k слагаемых будем обозначать P(n,k), а число всех разбиений числа n (на произвольное число слагаемых) – через P(n). Очевидно,
P(n)=, n>0.
Положим, P(0,0)=P(0)=1.
Теорема 1. P(n,k) равно числу разбиений числа n c наибольшим слагаемым равным k.
Доказательство.
Рассмотрим способ представления разбиения числа в виде диаграмм Ферреса (Феррера):
Она состоит для разбиения n= a1+a2+…+ak из k строк, i-я строка содержит ai точек.
Пример 16=6+4+4+2
· · · · · · · · · ·
· · · · · · · ·
· · · · · · · сопряженное разбиение
· · · · ·
·
·
Каждому разбиению числа n однозначно соответствует сопряженное разбиение этого числа, которое получается транспонированием диаграммы Ферреса. Отсюда следует, что транспонирование диаграммы Ферреса определяет взаимно однозначное соответствие между разбиениями числа n на k слагаемых и разбиением числа n с наибольшим слагаемым, равным k.
Теорема 2. Число разбиений числа n на попарно различные слагаемые равно числу разбиений числа n на нечетные слагаемые.
Доказательство (соответствие Глейшера).
Установим взаимно однозначное соответствие между разбиениями, о которых идет речь в теореме.
Пусть n разбито на нечетные слагаемые b1,b2,…,bp, где bi появляется в разбиении ri раз, 1≤i≤p. Положим ri=… (q1>q2>….).
Произведем замену ri слагаемых bi на попарно различные слагаемые
bi bi …
т. е.
ri bi= bibi …,
Повторяя эту замену для каждого i, 1≤i≤p, и упорядочивая слагаемые по невозрастанию, получаем в результате разбиение числа n на попарно различные слагаемые. (Здесь использована теорема об однозначном представлении каждого натурального числа в виде произведения нечетного числа на степень числа два.)
Пример.
26=7+5+5+3+3+1+1+1: 7·20+5·21+3·21+1·(21+20)=7+10+6+2+1=10+7+6+2=1
И обратно,
Пусть n=b1+b2+…+bk, где 0 <bk,…<b1, тогда bi= p·2q, 1≤i≤p.
Заменяем каждое bi на 2q слагаемых p, затем упорядочиваем по невозрастанию, получаем разбиение n на сумму нечетных слагаемых.
Таким образом, описанное преобразование определяет взаимно однозначное соответствие между разбиениями на нечетные слагаемые и разбиениями на попарно различные слагаемые.
Теорема 3. Число разбиений числа n, в котором ни одно из слагаемых не превосходит k, равно числу разбиений числа n+k на k слагаемых, т. е. P(n+k,k).
Доказательство.
Пусть δ – разбиение числа n, в котором ни одно из слагаемых не превосходит k, a δ′ сопряженное с δ, тогда δ′ содержит не более k слагаемых. Пусть δ′=(b1,b2,…,), k′≤k, тогда разбиение (k,b1,b2,…,) является разбиением числа n+k ровно на k слагаемых. Заметим, что (k,b1,b2,…,) определяется однозначно через δ.
Пусть ε= (b1,b2,…,bk) разбиение n+k на k слагаемых, а ε′ – разбиение сопряженное с ε′. Пусть ε′=(k,b1,b2,…,), тогда (b1,b2,…,), разбиение числа n, при этом (b1,b2,…,) определяется однозначно. Теорема доказана!
Теорема 4. Число разбиений числа а–с равно с b–1 частями, не превосходящими с, равно числу разбиений числа a–b с c–1 – частями, не превосходящими b.
Доказательство.
Рассмотрим графическое представление типичного разбиения первого типа и преобразуем это разбиение следующим образом: добавим новую строку из c точек, затем удалим первый столбец (который теперь имеет b точек) и произведем сопряжение полученного разбиения:
сразу видно, что такое последовательное преобразование представляет собой взаимно однозначное соответствие между этими двумя типами разбиений и, следовательно, доказывает теорему.
В качестве примера рассмотрим случай a=14, b=5, c=4:
4+4+1+1→3+3+3
4+3+2+1→4+3+2
4+2+2+2→5+2+2
3+3+3+1→4+4+3
3+3+3+2→5+3+1
Введем производящие функции, которые применяются в некоторых задачах, связанных с разбиением чисел.
Пусть n=a1+a2+…+ak, тогда <λ1, λ2,…, λn>, где λi=|{(j:aj=i)&(1≤j≤k)}|. Имеем, очевидно,
,
и каждая последовательность<λ1, λ2,…, λn>, (λ1, λ2,…, λn≥0), отвечающая этому условию однозначно определяет разбиение числа n, содержащее λi слагаемых равных i, 1≤j≤n.
Обозначим, Ph(n) – число разбиений числа n на слагаемые не превышающие h, а P(n) определяет число всех разбиений числа n.
Теорема 4. Производящая функция для последовательности Ph(0), Ph(1), Ph(2),… равна
(1+t+t2+t3+…)(1+t2+t4+t6+…)…(1+th+t2h+t3h+…)=(1-t)-1(1-t2)-1…(1-th)-1.
Доказательство.
Согласно определению произведения h рядов с правой стороны является суммой слагаемых вида ··…· (λi – номер члена выбранного из i-го ряда). Таким образом, коэффициент при tn равен числу последовательностей <λ1, λ2,…, λn>, таких что , а, следовательно, в соответствие с предыдущими замечаниями он равен Ph(n).
Аналогичным образом доказывается следующая теорема:
Теорема 6. Производящая функция для последовательности P(0), P(1), P(2),… равна
(1+t+t2+t3+…)(1+t2+t4+t6+…)…(1+th+t2h+t3h+…)…=1-th)-1.
Замечание. В этом месте следовало бы строго определить ряд, являющийся бесконечным произведением рядов F1(t)·F2(t)·F3(t)·… . Обозначим In(t) “частичное” произведение F1(t)·F2(t)·…·Fn(t) и через pn – наименьшую ненулевую степень с ненулевым коэффициентом в Fn(t). Положим, что коэффициент при нулевой степени в каждом из рядов Fn(t) равен единице, и что pn=∞ (оба эти условия выполнены в условии теоремы). Тогда коэффициент при tn в Im(t) один и тот же для всех m, больших некоторого числа mn. Именно этот коэффициент принимается как коэффициент при tn в ряде, определенном бесконечным произведением F1(t)·F2(t)·F3(t)·… .
Техника производящих функций позволяет провести простые доказательства некоторых свойств разбиений числа. Приведем в качестве примера другое доказательство теоремы 2.
Пусть R(t) – производящая функция для разбиений на попарно различные слагаемые, тогда
R(t)=(1+t)(1+t2)(1+t3) ·…·(1+tk)·… ,
а производящая функция для разбиений на нечетные слагаемые равна
N(t)=(1-t)-1(1-t3)-1·…·(1-t2k-1)-1·… .
(заметим, что оба произведения абсолютно сходящиеся при 0<t<1 )
Пользуясь зависимостью 1+tk=(1-t2k)/(1-tk), получаем
R(t)= …=…=N(t)
Теорема 7. Пусть Pe(D,n) (соответственно Pо(D,n)) число разбиений n на четное (соответственно нечетное) число различных частей3. Тогда
Pe(D,n)− Pо(D,n)=
Доказательство.
Мы попытаемся установить взаимно однозначное соответствие между разбиениями, перечисляемыми функцией Pe(D,n), и разбиениями, перечисляемыми функцией Pо(D,n). Для большинства целых n наша попытка увенчается успехом; однако, если n является одним из пятиугольных чисел , то это и составит единственный исключительный случай.
Введем два параметра разбиения α= (a1,a2,…,ak): s(α)=ak (наименьшая часть разбиения α) и σ(α) – наибольшее j, для которого aj=a1-j+1 (при αD – число членов в монотонно убывающей последовательности с разницей между соседними членами, равной 1, начинающейся с a1 и состоящей из первых частей разбиения α). Графически эти параметры описываются очень просто:
α=(7 6 4 3 2) α=(8 7 6 5 )
. . . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . σ(α)=2 . . . . . . σ(α)=4
. . . . . . . .
. . s(α)=5
s(α)=2
Преобразуем разбиение следующим образом.
Случай 1. s(α) ≤ σ(α). В этом случае увеличение на единицу каждую из s(α) наибольших частей α и отбрасываем наименьшую часть. Таким образом
α=(7 6 4 3 2 ) → (8 7 4 3),
т. е.
. . . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . → . . . .
. . . . . .
. .
Случай 2. s(α) > σ(α). В этом случае, наоборот, уменьшаем на единицу каждую из σ(α) наибольших частей α и образуем наименьшую часть величины σ(α). Таким образом
α=(8 7 4 3) → (7 6 4 3 2),
т. е.
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . → . . . .
. . . . . .
. .
Описанная процедура в обоих случаях меняет четность числа частей разбиения; замечая, что к разбиению можно применять лишь один из этих случаев, видим, что такое отображение устанавливает взаимно однозначное соответствие. Однако имеются определенные разбиения, для которых это отображение не работает, например, α=(8 7 6 5). К нему нужно было бы применять случай 2, но получаемое посредством него новое разбиение уже содержит одинаковые части, т. е. не принадлежит нашему множеству D. Итак, случай 2 не работает, когда разбиение имеет вид σ(α)=r, s(α) =r+1, и в этом случае само разбиваемое число, очевидно, равно
(r+1)+(r+2)+…+2r=r(3r+1).
С другой стороны, случай 1 не работает, когда разбиение имеет r частей, σ(α)=r, s(α) =r, а само разбиваемое число, очевидно, равно
r+(r+1)+…+(2r-1)=r(3r-1).
Таким образом, если n не является пятиугольным числом, то Pe(D,n)=Pо(D,n), а если n= r(3r1), то Pe(D,n) = Pо(D,n)+(-1)r
Следствие 1.(Пентагональная теорема Эйлера).
1-tn) = 1+(1+tm)= .
Доказательство.
=1++=1++=1+(1+tm)=1+ Pe(D,n) - Pо(D,n))tn.
Для полноты доказательства нужно еще показать, что
1+ Pe(D,n) - Pо(D,n))tn.= 1-tn).
Теперь
1-tn)= …
как и в доказательстве формулы теоремы 5. Заметим, каждое разбиение с различными частями подсчитывается с весом , который равен +1, если это разбиение имеет четное число частей, и -1 в случае нечетного числа частей. Следовательно,
1-tn)= …=1+ Pe(D,n) - Pо(D,n))tn
и тем самым имеем требуемое.
Следствие 2.( Эйлер). Если n>0, то
P(n)–P(n–1)–P(n–2)+P(n–5)+P(n–7)+…
…+(-1)m P(n–m(3m-1)/2)+(-1)m P(n–m(3m+1)/2)=0, (*)
где P(M)= 0 для всех отрицательных M.
Доказательство.
Пусть аn обозначает левую часть равенства (*). Тогда
=[1+(1+tm)]= 1-tn)-1∙ 1-tn)=1,
где предпоследнее равенство сразу следует из 6 и следствия1. поэтому аn = 0, для n>0.
Следствие 2 представляет собой весьма эффективный алгоритм для вычисления P(n).
Значения P(n) растут очень быстро с ростом n. Имеем:
P(1)=1; P(2)=2; P(3)=3; P(4)=5; P(5)=7; P(6)=11; P(10)=42; P(20)=627; P(50)=204 226; P(100)=190 569292; P(200)=3 972 999 029 388.
Однако, имеется точная формула для P(n) – результат, выведенный Харди и Рамануджаном и усовершенствованный Радемахером. Этот результат относится к одному из высших достижений теории разбиений:
Теорема (Харди – Рамануджана – Радемахера).
P(n)=, (1)
где
Аk(n)=h,ke-2πinh/k
и ωh,k – корень 24k-й степени из единицы, определяемый специальным образом.
Это необычайное тождество, котором левой частью служит простая арифметическая функция P(n), а в правой – бесконечный ряд, включающий в себя π, квадратные корни, комплексные корни из единицы и производные гиперболических функций, являет собой не только чисто теоретическую формулу для P(n), но формулу, обеспечивающую действительно быстрое вычисление.4 (Для малых значений n можно, конечно, пользоваться рекуррентностью из приведенной ниже пентагональной теоремы Эйлера.) Кроме того, довольно просто показать, что каждый член бесконечного ряда в (1) есть O(exp{π(2n)1/2/k}). Следовательно, первый член k=1 дает нам асимптотическую формулу для P(n); замечая, что A1(n)=1, без особых трудностей получаем, что при n→∞
P(n)≈.
Задачи.
1. (Саббарао). Число разбиений числа n, в которых части встречаются дважды, трижды или по пять раз, равно числу разбиений n на части, сравнимые с 2, 3, 6, 9, 10 по модулю 12.
2. Число разбиений числа n, в которых могут повторяться только нечетные части, равно числу разбиений n в которых нет части, встречающейся более чем три раза.
3. (Сильвестр). Число разбиений числа n с различными нечетными частями равно числу разбиений n, которые являются самосопряженными (т. е. совпадают со своим сопряжением).
4. (Эйлер). Абсолютное значение излишка числа разбиений n с нечетным числом частей над числом разбиений n с четным числом частей равно числу разбиений n на различные нечетные части.
Композиции чисел.
Теорема 8. Пусть C(m,n) обозначает число композиций числа n точно с m частями, тогда C(m,n)=.
Доказательство 1.
Рассуждение, используемое в доказательстве теоремы 4, можно легко применить для доказательства того, что
= (t1+ t2+ t3+ t4+…)m==tm==.
Приравнивая коэффициенты при tn в крайних членах этой цепочки равенств, получаем требуемое.
Доказательство 2.
Введем графическое представление для композиций числа n. C композицией (a1a2…am) числа n связываем m сегментов интервала [0, n]; первый сегмент имеет длину а1, второй – длину а2 и т. д. Например, композиция (3 2 3 1 2) числа 11 представим в виде
0←1─2→3←4→5←6─7→8↔9←10→11
Заметим теперь, что можно построить каждую из С(m,n) композиций числа n c m частями, выбирая m-1 чисел из n-1 первых целых как конечные точки для таких m сегментов, разделяющих интервал [0, n]. Поскольку таких выборов может быть , видим, что C(m,n)=.
Простота теоремы 6 позволяет получать чисто асимптотические выражения для некоторых функций разбиений, связывая их с функциями композиций. Например,
Теорема 9. (Эрдеш – Ленер). Пусть РM(n) обозначает число разбиений числа n ровно с М частями, тогда при n→∞
РM(n)≈ , если M=o(n1/3).
Задачи
1.Пусть Fn – n-е число Фибоначчи F0=0, F1=1, Fn=Fn-1+Fn-2, n>1. Показать, что число композиций n, в которых нет единиц, равно Fn-1.
2. В более общем виде – Пусть kFn – определяется по правилу;
kF0=…=kFk-2, kFk-1=1, kFn=kFn-1+kFn-k.
Показать, что число композиций n, в которых все части ≥ k, равно kFn-1.
3. Из задачи 2 следует, имеется 2n-1 композиций числа n.
4. пусть Сk(m,n) обозначает число композиций n точно с m частями, каждая из которых не меньше k. Тогда
Сk(m,n)=
5. Из задач 2 и 4 следует, что
= kFn-1
Принцип включения и исключения.
Пусть A1,…,An некоторые подмножества (необязательно различные) конечного множества Х.
Теорема 1.(Принцип включения и исключения).
-+-…(-1)n-1||
Доказательство
Применим математическую индукцию по n.
Для n=1 терема очевидно справедлива!
Предположим, что для произвольных A1,…,An-1 выполняется
||=-+-…(-1)n-2||
Применяя эту формулу к сумме
,
получаем
||=-+…(-1)n-2||,
а отсюда
||==+|An|-||=
-+-…(-1)n-1||.
Покажем несколько применений принципа включения и исключения
Теорема 2. Пусть |X|=n, |Y|=k, то число всех функций f:XY и f(X)=Y, равно
Sn,k=
Доказательство
Пусть У={y1,…,yk} и Ai={f : f:XY & yif(X)}, тогда
f(X)Yf
Множество всех f:XY имеет мощность kn. Определим , пусть 1p1…pik пересечение есть множество всех функций f:XY таких, f(X), a, следовательно, мощность этого пересечения ровно (m-i)n. Согласно теоремы 1 имеем
Sn,k=kn-||=kn- =
Эта формула дает простое выражение для вычисления чисел Стирлинга 2го рода
S(n,k)= Sn,k=
Рассмотрим вопрос об определении числа “беспорядков” на множестве {1,…,n}
Определение. Под беспорядком на множестве {1,…,n} будем понимать произвольную перестановку f этого множества, такую что f(i)i для 1in.
Пусть Dn – множество всех беспорядков на {1,…,n} и
Ai={fSn: f(i)=i}, i=1,…,n.
Заметим, что fDn f Ai для i{1,…,n}, следовательно
|Dn|=|Sn|-+-+…(-1)n-1||
Для произвольной последовательности 1p1…pin пересечение является множеством таких перестановок f, для которых f(pj)=pj для 1jn, и значит, ||=(n-i)!. Заметив, что последовательность 1p1…pin можно выбрать способами, получаем в итоге
|Dn|== =n!( )
Отметим, что сумма в скобках является начальным членом ряда е-1=. Это означает, что беспорядки составляют е-1=0.36788… всех перестановок.
Перечисление графов5
1.1 Число способов, которыми можно пометить граф.
Граф G порядка p состоит из конечного непустого множества V=V(G), содержащего p вершин, и множества X из q неупорядоченных пар различных вершин; при таком определении автоматически исключаются петли (ребра, соединяющие вершину с ней самой) и кратные (параллельные) ребра. Пара x={u,v}, принадлежащая множеству X, называется ребром графа G и говорят, что ребро соединяет вершины u b v. Вершины u и v называют при этом смежными; вершина u и ребро х, так же как вершина v и ребро x, называются инцидентными друг другу. Граф с р вершинами и q ребрами называется (p,q)-графом.
Значительно удобнее и нагляднее представлять графы диаграммами. Рассмотрим граф G, выбранный случайным образом, с множеством вершин V={v1, v2, v3, v4} и множество ребер
Х={ { v1, v2,}, { v2, v3,}, { v3, v4,}, { v4, v1,}, { v1, v3,}}
Его изображение диаграммой дано на рис. 1. На этой диаграмме буквами
v1 v2
v3 v4
рис. 1 Граф с четырьмя вершинами и пятью ребрами
обозначены только вершины. Пять ребер графа G представлены отрезками прямых, которые соединяют на рисунке соответствующие пары вершин.
В помеченном графе порядка р вершинам приписываются целые числа от1 до р. Например, граф, изображенный на рис. 1 может быть помечен шестью различными способами, которые указаны на рис 2.
1 4 1 4 1 3 2 4 2 3 3 2
3 2 2 3 2 4 1 3 1 4 1 4
рис. 2 Шесть различных распределений пометок в графе
Возникают два естественных вопроса. Первый: “Сколько существует помеченных графов порядка р?” Второй: “Сколько существует графов порядка р?” Первый мы обсудим сейчас, а на второй будет исследоваться позже.
Мы ответим на первый вопрос, незначительно обобщив задачу следующим образом: Найти число помеченных графов с данным числом вершин и ребер. Пусть Gp(t) – многочлен, у которого коэффициент при tk равен числу помеченных графов порядка p, имеющих ровно k ребер (Gp(t) - производящая функция для помеченных графов с заданным числом вершин и ребер). Если V – множество из р вершин, то существует различных неупорядоченных пар этих вершин. В каждом помеченном графе с множеством вершин V любая пара вершин является либо смежной, либо нет. Следовательно, число помеченных графов с k ребрами равно.
Теорема. Производящая функция Gp(t) для помеченных графов порядка р задается соотношением
Gp(t)== (1+ t)m, где m= (1)
Так как Gp(t)=(1+ t)m и число Gp помеченных графов порядка р равно Gp(1), то
Gp= . (2)
Для р=3 существует восемь помеченных графов порядка 3 и только четыре (непомеченных) графа этого порядка. Существует 64 помеченных графов порядка 4 и только 11 графов порядка 4. (Проверьте приведенные данные!).
Возникает вопрос: “Сколькими способами можно пометить данный граф?” Чтобы ответить на этот вопрос, мы должны рассмотреть симметрии, или автоморфизмы, графа:
Взаимно однозначное отображение α множества V(G) на множество V(G1), сохраняющее смежность, обычно называется изоморфизмом. G=G1, то α является автоморфизмом графа G. Совокупность всех автоморфизмов графа G, обозначаемая Г(G), образует группу, называемую группой графа G. Таким образом, элементы группы Г(G) являются подстановками (перестановками), действующими на множестве V. Например, граф G, изображенный на рис. 1, имеет в точности четыре автоморфизма, так что Г(G) содержит следующие перестановки, записанные здесь с использованием обычного представления в виде произведения циклов:
(v1)(v2)(v3)(v4), (v1)(v3)( v2v4), (v1 v3)(v2)(v4), (v1 v3)( v2v4).
Пусть s(G)=│ Г(G)│ - порядок группы Г(G), обозначающий число симметрий графа G. Тогда ответ на задачу распределения пометок, поставленную выше, содержится в следующей теореме.
Теорема. Число способов распределения пометок в данном графе порядка р равно
(G)=p!/ s(G). (3)
Доказательство этого утверждения будет приведено позже. Для иллюстрации теоремы мы просто заметим, что граф G на рис. 1 имеет p!/ s(G)=4!/ 4=6 распределений пометок и шесть различных помеченных графов на рис. 2.
Хотя эта теорема сформулирована только для графов. Подобные утверждения справедливы для любых конечных структур с заданными группами автоморфизмов, таких, как графы с корнями, орграфы, и т. п.
Ориентированный граф, или орграф, D порядка p состоит из конечного непустого множества V=V(D), различных p объектов, называемых вершинами, вместе с заданным множеством X содержащим q упорядоченных пар различных вершин из множества V. Пара x=(u,v), принадлежащая множеству X, называется дугой орграфа D и, говорят, что u смежна к вершине v; вершина u и дуга х являются инцидентными друг другу, так же как вершина v и дуга x. Полустепенью исхода вершины u называется число дуг, для которых вершина u является первой вершиной; полустепенью захода вершины u называется число дуг, для которых вершина u является второй вершиной. Для орграфа также возможно представление в виде диаграммы, которой мы будем обращаться, как с самим орграфом.
В помеченном орграфе порядка р вершинам приписываются целые числа от 1 до р, и группа орграфа D, обозначаемая Г(D), состоит из всех подстановок множества вершин V(D) орграфа D, сохраняющая смежность. Так как число помеченных орграфов порядка р, имеющих в точности k ребер, равно ,то получаем следующие результаты:
Теорема. Производящая функция Dp(t) для помеченных орграфов порядка р задается соотношением
Dp(t)== (1+ t)p(p-1), (4)
Очевидно, что Dp(t )=Gp2(t), так что Dp(1)=2p(p-1)=Gp2(1)
В круговом турнире заданное множество игроков ведут игру, правилами которой запрещен ничейный исход. Любые два игрока встречаются между собой только один раз, и лишь один из них одержит победу. Следовательно, турнир представляет собой орграф, в котором каждая пара вершин соединяется только одной дугой.
Упражнение. Докажите, что число помеченных турниров порядка р, равно.
1.2 Связные графы.
Пусть G – граф и v0, v1, v2,…, vn – последовательность вершин графа G, такая, что вершина vi смежна с вершиной vi+1 при i = 0, 1, …,n-1. Такая последовательность вместе с n ребрами { vi, vi+1}, 0≤i≤n-1, называется маршрутом длины n. Если ребра в маршруте различные, то он называется цепью. Если в маршруте различны все вершины (а следовательно, и ребра), то называется простой цепью. Связным графом называется граф, в котором любые две различные вершины простой цепью.
Число помеченных связных графов порядка 4 может быть вычислено тривиальным образом и равно 38.(Проверьте!).
Подграф H графа G имеет V(H)V(G) и X(H)X(G). Компонента графа представляет собой максимальный связный подграф. Граф с корнем (и корневой граф) имеет одну выделенную вершину, называемую корнем. Два корневых графа называют изоморфными, если существует взаимно однозначная функция, отображающая множество вершин одного графа на множество вершин другого графа, которая сохраняет не только смежность вершин, но и корни 6. Аналогичное требование накладывается и при описании корневых помеченных графов. Это понятие можно сейчас использовать для получения следующей рекурсивной формулы. Пусть Сp – число связанных помеченных графов порядка р.
Теорема. Число Сp связанных помеченных графов удовлетворяет соотношению
Сp= -Ck. (5)
Доказательство.
Заметим, что если в помеченном графе делать корнями разные вершины, то получатся разные корневые помеченные графы. Следовательно, число корневых помеченных графов, в которых порядка p равно pGp. число корневых помеченных графов, в которых корень находится в компоненте, содержащей в точности k вершит равно kCk.
Суммируя эти произведения по k от 1 до p, мы опять получаем выражение для корневых помеченных графов, а именно
СkGp-k.
Для дальнейших построений нам потребуется важное свойство экспоненциальных производящих функций для графов:
Для всякого к =1,2,3…обозначим через аk число способов, которым можно пометить все графы порядка k, обладающие некоторым свойством P(a), пусть a(t)= экспоненциальная производящая последовательности аk. Предположим также, что b(t)= другая экспоненциальная производящая функция для класса графов, удовлетворяющих свойству P(b).
Следующая лемма дает полезную интерпретацию коэффициентов произведения а(t)∙b(t) этих двух производящих функций.
Лемма пересчета помеченных графов. Коэффициент при tk/k! в а(t)∙b(t) равен числу упорядоченных пар (G1,G2) двух непересекающихся графов, где G1 обладает свойством P(a), где G2 обладает свойством P(b), k – Число вершин в G1G2 и пометки от 1 до k распределены на графе G1G2.
Для иллюстрации этой леммы положим, что С(t) – экспоненциальная производящая функция для помеченных связных графов: C(t)=
Тогда С(t)∙С(t) является производящей функцией для упорядоченных пар связных графов. Разделив этот ряд на 2, получаем производящую функцию для помеченных графов, имеющих в точности две компоненты. Аналогично, Сn(t)/n! имеет при tk/k коэффициент, равный числу помеченных графов порядка k, содержащих в точности n компонент. Если через G(t) обозначим экспоненциальную производящую функцию для помеченных графов, то
G(t)= . (6)
Таким образом, мы имеем следующее экспоненциальное соотношение между
G(t) и С(t), найденное Риделлом (1951).
Теорема. Экспоненциальные производящие функции G(t) и С(t) для помеченных графов и для помеченных связных графов удовлетворяют соотношению
1+ G(t)=eС(t). (7)
Замечание. 1. Это равенство остается справедливым и для мультиграфов.
Риордан получил следующее рекуррентное соотношение для Ср:
Сp=(2k-1)CkCp-k. (8)
Кроме того, очевидно, что если известна экспоненциальная производящая функция для некоторого класса графов, то экспоненциальная производящая функция для соответствующих связных графов получается формальным логарифмированием первого ряда, точно так же как в теореме для всех графов.
Поэтому мы можем сформулировать следующий общий результат.
Следствие. Если /m!=exp(/m!), то для m≥1
am=Am -akAm-k. (9)
Задачи 1. Построить производящую функцию для связных помеченных орграфах;
2.найти перечислительную формулу для помеченных (p,q)-графов, не имеющих изолированных вершин.
1.3 Эйлеровы графы
Степенью вершины v (обозначается deg v) в графе G называется число ребер, инцидентных вершине v. Граф, каждая вершина v, которого имеет четную степень, называется четным. Эйлеров граф – это связный четный граф.
Пусть Wp – число помеченных четных графов порядка p. Тогда справедлива следующая теорема:
Теорема. Число помеченных четных графов порядка p равно числу помеченных графов порядка p-1:
Wp=.
Доказательство.
Чтобы доказать этот результат, мы сейчас установим взаимно однозначное соответствие между этими двумя графов. Рассмотрим произвольный граф порядка p-1. Граф G должен иметь четное число вершин нечетной степени. Добавим к нему вершину v, которой припишем пометку p. Наконец, из графа G и вершины v строим граф G′, имеющей нечетную степень. Этот граф G′ является помеченным четным графом порядка p. Легко видеть, что описанное соответствие является взаимно однозначным и что каждый помеченный четный граф порядка p может быть получен таким способом из некоторого помеченного графа порядка p-1.
Чтобы получить формулу для числа помеченных эйлеровых графов, мы будем использовать производящие функции. Итак, пусть W(t) – экспоненциальная производящая функция для помеченных четных графов, такая что
W(t) =tp/p! (10)
Далее, пусть Up – число помеченных эйлеровых графов порядка p, так что
U(t) =tp/p! (11)
является соответствующей экспоненциальной производящей функцией.
Теорема. Экспоненциальная производящая функция U(t) для помеченных эйлеровых графов удовлетворяет соотношениям
U(t) =ln(W(t)+1) (12)
и
Up= -Uk. (13)
Формула (12) следует из того факта, упомянутого после равенства (8), что если известна производящая функция для произвольного класса графов, то производящая функция для соответствующих связных графов получается с помощью формального логарифмирования первого ряда. Рекуррентное соотношение (13) для Up является следствием формул (12) и (9).
Для нескольких первых членов ряда U(t) имеем равенство
U(t)=t+t3/3!+ 3t4/4!+ 38t5/5!+… (14)
Упражнение. Проверьте справедливость равенства (14).
К несколько более трудной относится задача – определение числа помеченных эйлеровых графов с заданным числом вершин и ребер, установленный Ридом.
Теорема7. Многочлен wp(t), у которого коэффициент при tq равен числу помеченных графов имеющих p вершин четной степени и q ребер, задается формулой
wp(t)= . (15)
Для малых значений p находим, что (проверьте):
W1(t)= w2(t)=1 w3(t)=1+t3 w4(t)=1+4t3+ 3t4.
1.7 Деревья
Деревом называется связный граф, не имеющий циклов. Известно, что всякое нетривиальное дерево имеет не менее двух висящих вершин (вершины степени 1). Это Следует из того, что если T – дерево с p вершинами и q ребрами, то
q=p-1.
Теорема.(Кэли 1897). Число p помеченных деревьев порядка p равно
p=pp-2.
Доказательство.
Первый подход (Кэли) Установим соответствие между помеченными деревьями и функциями, отображающими множество из p-2 объектов в множество из p объектов. Например, если p=5, то существует 53 функций из {a,b,c} в {v1, v2, v3, v4, v5}. Эти функции перечисляются многочленом
(v1+ v2+ v3+ v4+ v5)3. (16)
Слагаемые этого многочлена сопоставляются функциям естественным образом. Например, соответствует постоянной функции f(x)=v4, слагаемое отвечает трем функциям, которые отображают только один элемент в v1, два других – в v3, 6v2v3v5 дает шесть функций, отображающих по одному элементу в v2, v3 и v5. Теперь, умножая многочлен на v1v2v3v4v5 и получая
(v1+ v2+ v3+ v4+ v5)3 v1v2v3v4v5 (17)
устанавливаем тем самым соответствие между слагаемыми из этого произведения и помеченными деревьями порядка 5. Это соответствие с использованием слагаемого=v1v2v3v4v5) выглядит так
Заметим, что в деревьях, соответствующих слагаемому , степень вершины, помеченной числом k, равна показателю степени у vk. Справедливость этого высказывания может быть установлена и в общем случае. Следовательно, число помеченных деревьев, у которых вершины, помеченные числом k, имеют степень dk, равно полиномиальному коэффициенту
. (18)
Кэли проиллюстрировал это соответствие для p=6 и не стал рассатривать другие случаи, заметив: “Сразу видно, что доказательство, данное для этого частного случая, применимо при любом значении p”.
Второй подход (Прюфер 1917). Пусть дерево с n вершинами, помеченными числами 1, …,n. Свяжем с этим деревом последовательность натуральных чисел i1,…,in-2 , построенную следующим образом:
1)положим j=0;
2)повторим следующий процесс n-2 раза:
увеличим значение j на единицу; найдем в дереве лист, помеченный натуральным числом с наименьшим значением. Пусть это значение kj, и пусть отцом листа kj является вершина, помеченная числом ij. Выберем значение ij в качестве j-ого элемента последовательности. Удалим в дереве ребро (ij,kj).
После исполнения этого алгоритма начальное дерево преобразуется в дерево, состоящее из одного ребра либо (in-2,n), либо, в случае in-2=n, – из ребра (n,n-1).
а) b)
1 7 1 7
8 2 3 2 8 3
5 5
6 6
4 4
Заметим, что в приведенном алгоритме, построенный им код определен однозначно.
Рассмотрим алгоритм восстановления дерево по его коду Прюфера i1,…,in-2. Для этого
Если вершина ij-1 (исключая j=1) еще не включена в дерево, то строим в нем ребро (ij,ij-1); в противном случае строим ребро (ij,m), где m наибольший номер вершины еще не включенной в дерево.
Упражнение. Восстановите деревья по кодам Прюфера, полученным в предыдущем упражнении.
Замечание. Пусть задана произвольная последовательность натуральных чисел i1,…,in-2, каждое из которых из промежутка 1..n. Тогда, по приведенному алгоритму, для этой последовательности может быть построено помеченное дерево, при этом двум разным последовательностям соответствуют два разных дерева.
Таким образом, теорема Кэли следует из установленной биекции.
Третий подход (Пойа 1937). Экспоненциальная производящая функция для числа помеченных корневых деревьев может быть задана выражением
y =p t p/p!. (19)
Пойа нашел функциональное уравнение для у, как функции от t, и затем для нахождения tp применил формулу обращения Лагранжа.
Это функциональное уравнение для y будет сейчас выведено. Из леммы пересчета помеченных графов следует, что yn/n! является экспоненциальной производящей функцией для n-множеств помеченных корневых деревьев. Эти n-множества соответствуют в точности тем корневым деревьям, в которых корень имеет степень n и не помечен. Более точно, это соответствие получается так: сначала добавляем к каждому n-множеству новую вершину, не помечая ее, а затем соединяем эту новую вершину с каждым из старых корней. Умножение выражения yn/n! на t отвечает приписыванию пометки новому корню и включению его в число пересчитываемых вершин. Таким образом, t yn/n! перечисляет корневые помеченные деревья, в которых корень имеет степень n. Суммируя по n, получаем
y =yn/n!, (20)
и, следовательно, мы приходим к функциональному уравнению
y= tey (21)
чтобы найти решение (20), выразив y как функцию от x, мы применим весьма полезный частный случай формулы Лагранжа.
Формула обращения Лагранжа (частный случай)8. Если функция (y) аналитична в некоторой окрестности точки y=0 и (0)0, то уравнение
t=y/(y) (22)
имеет единственное решение, задаваемое производящей функцией
y = (23)
коэффициенты которой определяются по формуле
ck = (1/k!){(d/dy)k-1((y))k}y=0. (24)
Применяя эту формулу обращения к уравнению (21), где (y)=ey, находим
y =tk/k!, (25
и, сравнивая это выражение с (19), снова получаем формулу для p.
Четвертый подход (Кирхгоф 1847) Более интересный и полезный результат, обычно называемый “Матричная теорема о деревьях” содержится в работе Кирхгофа 1847 года. Число помеченных деревьев может быть быстро получено как простое следствие этого результата.
Пусть А=(G)+aij – матрица смежности графа G. обозначим М(G) матрицу, которая получается из –A с помощью подстановки на место i-го диагонального элемента в ней числа deg vi, для каждого i.
Теорема. (Матричная теорема о деревьях для графов). Для всякого связного помеченного графа G все алгебраические дополнения матрицы М(G) равны друг другу и их общее значение представляет собой число остовных деревьев графа G.
Для иллюстрации этой сформулированного утверждения рассмотрим
М(G)=, M(G)= −= 3.
Теорема Кэли является следствием применения матричной теоремы о деревьях к полном графу Kp. В самом деле, алгебраическое дополнение M(Kp) равно
−= pp-2
( Для вычисления определителя. Вычитаем первую строку из каждой другой и прибавляем последние р-2 столбцов к первому. Получается верхняя треугольная матрица, определитель которой равен pp-2.)
Доказательство (Матричной теоремы о деревьях для графов9)
Лемма 1. Пусть B – произвольная числовая nn-матрица, в каждой строке которой и в каждом столбце сумма элементов равна нулю:
=0, i=1,…,n; =0, j=1,…,n.
Тогда алгебраические дополнения всех элементов матрицы B равны между собой. (В частности, этим свойством обладает матрица Кирхгофа произвольного графа.
Доказательство
Очевидно, что rank B<n. если rank< n-1, то алгебраические дополнения всех элементов матрицы равны 0. Пусть rank= n-1 и С – присоединенная матрица для матрицы B, т. е. элемент Cij равен алгебраическому дополнению Aij
элемента Bij в матрице B, i=1,…,n; j=1,…,n. Известно, что BC=(det B)E, где E – единичная матрица. В наших условиях det B = 0, ВС = 0 – нулевая матрица. Следовательно, для столбца матрицы C с номером j, j=1,…,n, верны равенства
Bi1C1j+ Bi2C2j+…+ BinCnj=0, i=1,…,n,
т.е.
Bi1Аj1+ Bi2Аj2+…+ BinАjn=0, i=1,…,n,
Эти равенства можно рассматривать как систему линейных однородных уравнений с матрицей B относительно неизвестных Аj1, Аj2,…, Аjn. Так как rank B = n-1, то все решения системы пропорциональны. Но вектор (1,…,1) удовлетворяет системе, поэтому
Аj1= Аj2=…=Аjn j=1,…,n.
Учитывая, что CB = 0, аналогично получаем
А1i= А2i=…=Аni i=1,…,n.
Следовательно,
Аij= Аkl, i, j, k, l=1,…,n.
Определение. Пусть G – (n, m)-граф, n m-матрица I =I(G) называется матрицей инцидентности графа G, если I удовлетворяет условиям:
Для неориентированных графов
Ikl=
Для ориентированных графов
Ikl=
Пусть G – неориентированный граф. Превратим каждое его ребро в дугу, придав ему одну из двух возможных ориентаций. Полученный ориентированный граф называется ориентацией графа G. Непосредственно проверяется
Утверждение Если М(G) – матрица Кирхгофа графа G, а I – матрица инцидентности какой-либо его ориентации H (нумерация вершин в H та же, что и вG), то М(G)=I Itr ( здесь tr – операция транспонирования матрицы).
Лемма 2. Пусть H – (m+1, m)-граф, I – матрица инцидентности какой-либо его ориентации, M – произвольный минор порядка m матрицы I. Тогда
Доказательство
Прежде всего заметим, что можно произвольно менять нумерации вершин и ребер графа Н, от этого рассматриваемый минор может лишь изменить знак.
Пусть а – вершина, соответствующая строке матрицы I, не вошедшей в минор M. Если граф H не является деревом, то он несвязен. Пусть K={1,2,…,k} – его область связности, не содержащая вершины a. С помощью подходящей перенумерации ребер графа H матрицу I приведем к клеточно-диагональному виду I=diag[ I1,I2], где I1 – матрица инцидентности компоненты H(K). Минор M содержит все первые к строк матрицы I, сумма которых равна нулевой строке. Следовательно, M=0.
Пусть теперь H – дерево. Заново перенумеруем вершины и ребра графа Н следующим образом. Одной из концевых вершин v, отличных от вершины a, а также ребру инцидентному вершине v, присвоим номер 1. Далее рассмотрим дерево T1= H-v. если его порядок больше 1, то одной из его концевых вершин u, отличных от a, а также инцидентному ей ребру присвоим номер 2. Рассмотрим дерево T2= T1 –u. Итерируя этот процесс, получим новые нумерации вершин и ребер дерева H, причем вершина a будет иметь номер m+1. Матрица I при этом помет вид
.
(Здесь символ * обозначает те элементы или блоки матрицы, значения которых не влияют на ход рассуждений.) Минор М, остающийся после удаления последней строки этой матрицы, равен 1.
Для доказательства теоремы Кирхгофа мы также воспользуемся формулой Бинэ – Коши, доказательство которой обычно приводится в любом достаточно полном курсе по теории матриц10. Пусть A и В – n m- и m n- матрицы соответственно, С=АB и n≤m. Минор порядка n матрицы B назовем соответствующим минору порядка n матрицы A, если множество номеров строк первого из них и номеров столбцов второго совпадают.
Формула Бинэ – Коши. Определитель матрицы C равен сумме произведений каждого минора порядка n матрицы A на соответствующий минор матрицы B.
Доказательство теоремы Кирхгофа.
Пусть I – матрица инцидентности какой-либо его ориентации (n,m)-графа G. Имеем
М(G)=I∙Itr. (*)
Поскольку G – связный граф, m≥n-1. Если B – подматрица, остающаяся после удаления из М(G) последних строки и столбца, С – подматрица, остающаяся после удаления из I последней строки, то в силу (*) B=C∙Ctr. Алгебраическое дополнение Аnn равно det B. Из формулы Бинэ – Коши теперь следует, что Аnn равно сумме квадратов всех миноров порядка n-1матрицы С. Согласно, леммы 1 каждый такой минор М равен 1, если остовной подграф графа G, ребра которого соответствуют столбцам, вошедшим в M, является деревом, и нулю в противном случае. Следовательно, Аnn равно остовных деревьев в графе G. Поскольку алгебраические дополнения всех элементов матрицы М(G) равны (лемма 2), то теорема доказана.
Теорема Пойа.
1. Пример: раскраска узлов бинарного дерева11
Рассмотрим полное бинарное дерево с семью узлами и всевозможные различные варианты раскраски его узлов белым или черным цветом в предположении, что мы не отличаем «левое» от «правого». На следующем примере приведены различные представления одной и той же раскраски дерева:
В противоположность этому каждая из следующих картинок представляет собой отличную от других раскраску дерева:
Чтобы уяснить, какое же множество объектов подлежит пересчету, определим множество S представлений. Каждой картинке такого типа, как показанные выше, поставим в соответствие функцию из области D семи узлов в область R двух цветов:
D= {1,2,3,4,5,6,7},
R= {Б, Ч},
RD={f│f: D→R}.
Заметим, что RD состоит из 27=128 элементов, называемых представлениями. Например, приведенные выше представления f3 и f4 соответствуют функциям
f3(1) = f3(3) = f3(5) = f3(7) =Б, f3(2) = f3(4) = f3(6) = Ч
и
f4(1) = f4(3) = f4(5) = f4(6) =Б, f4(2) = f4(4) = f4(7) = Ч.
На множестве RD всех функций, отображающих D в R, определим отношение эквивалентности и каждый класс эквивалентности отождествим с одним из подлежащих пересчету объектов (раскрасок дерева).
Интуитивно ясно, f3 и f4 должны принадлежать одному классу эквивалентности относительно . Почему это так? В области D существует подстановка , которая переставляет двух сыновей узла 3, а именно узлы 6 и 7, и две функции f3 и f4 отличаются только «по модулю », т. е. f4 = f3, или, что эквивалентно, функция f4 получается применением сначала подстановки к D и последующим отображением D на R посредством функции f3. Поскольку мы не отличаем «левое» от «правого» и только переставляет левого и правого сыновей узла 3, две функции такого же типа, как f3 и f4 должны быть эквивалентны.
В таком случае наша первая задача при определении отношения эквивалентности состоит в выписывании группы всех подстановок, относительно которых раскраски эквивалентны. Эта группа, которую мы обозначим G, порождается перестановками:
1=(1)(23)(46)(57),
2=(1)(2)(3)(45)(6)(7),
3=(1)(2)(3)(4)(5)(67);
и выглядит так
|
перестановка |
Циклическое представление |
Цикловой индекс |
|
тождественная |
(1)(2)(3)(4)(5)(6)(7) |
|
|
1 |
(1)(23)(46)(57) |
|
|
2 |
(1)(2)(3)(45)(6)(7) |
|
|
3 |
(1)(2)(3)(4)(5)(67) |
|
|
23=32 |
(1)(2)(3)(45)(67) |
|
|
12=31 |
(1)(23)(4567) |
t1t2t4 |
|
13=21 |
(1)(23)(4756) |
t1t2t4 |
|
123 |
(1)(23)(47)(56) |
Определим основное, используемое в теореме Пойа:
Определение. Если дана группа подстановок G, то цикловым индексом PG группы G называется полином относительно переменных t1, t2, t3 …, который представляет собой среднее арифметическое цикловых индексов, взятыз по всем подстановкам группы G. В нашем примере
PG=1/8(+2+2+2 t1t2t4+).
В данном случае теорема Пойа утверждает:
Число классов эквивалентности на множестве RD, отображающих D в R, при отношении эквивалентности , индуцированном группой подстановокG на множестве D, получается сопоставлением значения R (мощности множества R) каждой переменной ti в цикловом индексе PG группы G. В нашем примере R = 2, и отсюда получаем
PG=1/8(27+25+27+24+25)=42
Упражнение. Проверьте путем систематического конструирования, что в нашем примере число различных раскрасок действительно равно 42.
2. Цикловой индекс группы подстановок.12
Пример1. Пусть S – множество вершин куба, так что m=S =8, и пусть G – множество всех тех подстановок S, которые могут быть получены вращением куба. Всего 64=24 таких вращений.
Их можно разбить на пять категорий.
(а) Тождественное.
(б) Три поворота на 180о вокруг прямых, соединяющих центры противоположных граней.
(в) Шесть поворотов на 90о вокруг прямых, соединяющих центры противоположных граней.
(г) Шесть поворотов на 180о вокруг прямых, соединяющих середины противоположных ребер.
(д) Восемь поворотов на 120о вокруг прямых, соединяющих середины противоположные вершины.
Поскольку 1+3+6+6+8=24, этот список полон.
Легко представить себе циклы множества S в каждом случае. В случае (а) – восемь циклов длины 1; подстановки типа (б) дают четыре цикла длины 2; в случае (в) два цикла длины 4; (г) дает четыре цикла 2; в случае (д) два цикла длины1 и два цикла длины 3. поэтому цикловой индекс таков:
PG=1/24(+9+6+8).
Пример2. Пусть S – множество ребер куба, так что m=12, и пусть G – множество всех 24 подстановок S, которые могут быть получены вращением куба.
Вращение те же, что и в примере 2. теперь надо посмотреть, что делают вращения с ребрами. Тождественное вращение - подстановка типа <>. Вращения (б) – типа <>, в случае (в) – тип <>, в случае (г) – тип <>, и в случае (д) – тип <>.
Поэтому имеем
PG=1/24(+3+6+6+8).
Пример 3. Опять возьмем вращения куба, но теперь пусть S – множество всех его граней. Наши пять категорий вращений дают подстановки типов <>, <>, <>, <>, <> соответственно, и поэтому
PG=1/24(+3+6+6+8). (1)
Пример 4. Пусть S – множество из m элементов и G – группа всех подстановок S; т. е. G – симметрическая группа степени m. Ее цикловой индекс согласно свойству циклового индикатора (см. § Цикловые типы), равен
Сm(t1, t2,…, tm)/m!=
или коэффициенту при um в разложении
exp(ut1+u2t2/2+u3t3/3+…) (2)
по степеням u.
Пример 5. Пусть S – некоторая конечная группа, m=S . Если а – фиксированный элемент множества S, то отображение s → as, как легко видеть, есть подстановка на множестве S. Обозначим ее через ga, мы замечаем, что если a пробегает все множество S, то такие подстановки ga образуют группу G. Имеем gagb=gab, поэтому G изоморфно самой группе G, изоморфизм определяется так gaa. Группа G называется представлением Кэли группы S.
Мы интересуемся ее цикловым индексом.
Если aS имеет порядок k(a), подстановка ga разбивает S на циклы, длины которых все равны k(a): если s – некоторый элемент S, то он принадлежит циклу, образованному из следующих элементов:
s→as→a2s→…→ak(a)s=s.
Отсюда следует, что m делится на k(a) и что подстановка ga разбивает S на m/k(a) циклов длины k(a).
Таким образом, мы получаем цикловой индекс:
PG=. (4)
Эта сумма может быть записана также так:
PG=, (5)
где d пробегает все делители m, а v(d) – это число элементов aS, порядок которых k(a)=d.
Пример 6. В качестве частного случая примера 5 возьмем следующую циклическую группу подстановок.
Пусть S – группа всех корней m-й степени из единицы e2ij/m, где j=1,…,m, i – мнимая единица.
Тогда для каждого aS отображение s→as является подстановкой S, группа этих подстановок - циклическая.
Если a=e2ij/m, то порядок элемента a равен k(a)=m/(m,j), где (m,j) - наибольший общий делитель m и j. Поэтому цикловой индекс
PG=
Второе выражение получается из (5)
PG=,
где - функция Эйлера, т. е. (d) – это число целых n, удовлетворяющих условию 1≤n≤d и (n,d)=1.
Пример 7. Пусть G группа подстановок множества S и пусть Н группа подстановок множества T. ST=, U=ST. Любому выбору gG и hH соответствует подстановка множества U, определенная так:
u→gu, если uS, u→hu, если uT.
Обозначим такую подстановку множества U через gh. Легко видеть, что эти подстановки образуют группу, порядок которой равен произведению порядков групп G и H. Эта группа называется прямым произведением групп G и H и обозначается GH.
Если gG и hH и если g имеет тип<> а h имеет тип <>, то gh имеет тип <>, так как каждый цикл в U лежит либо целиком в S, либо целиком в T. Отсюда член циклового индекса группы GH, соответствующий элементу gh, равен произведению члена в PG, соответствующего элементу g, и члена в PH, соответствующего h. Применив это ко всем членам PG и всем членам PH, получим формулу для произведения
PGH=PGPH
Замечание. Тип перестановки g позволяет делать некоторые выводы о перестановке и о степенях g2, g3,…, но мы очень мало можем сказать о типе произведения g1g2, исходя из типов сомножителей. Соответственно, хотя цикловой индекс может дать информацию о комбинаторных вопросах, касающихся группы подстановок, он мало говорит о мультипликативной структуре группы. В 1937г. Пойа привел пример двух неизоморфных групп подстановок с одинаковыми цикловыми индексами. Таким образом, цикловой индекс не всегда определяет группу однозначно.
Пойа берет две неизоморфные группы порядка p3, где p>2 простое, которые обладают тем свойством, что каждый элемент, кроме единичного, имеют порядок p.
В результате выражение (*) для циклового индекса представления Кэли дает один и тот же результат в обоих случаях.
3. Основная лемма.
Пусть G – конечная группа. Предположим, элементы G ведут себя, как подстановки множества S; это значит, что существует отображение G в симметрическую группу множества S. Другими словами gG мы поставим в соответствие подстановку множества S, которую обозначим через g. Предположим , что это отображение – гомоморфизм, т. е.
gg=gg (6)
для всех gG, gG. Заметим, что различные элементы G не обязательно соответствуют различным подстановкам.
В нашем случае G порождает отношение эквивалентности на элементах множества S. Два элемента s1, s2 множества S называются эквивалентными, записывается s1~s2, если существует gG, такой что gs1~s2. В самом деле:
1. s~s, для всех sS [так как формула (6) показывает, что если e – единичный элемент группы G, то е – тождественная подстановка, т. е. оставляющая на месте все точки S].
2. Если s1~s2, то s2~s1 [так как формула (6) показывает, что если g=g-1, то, g=(g)-1].
3. Если s1~s2, s2~s3 то s1~s3 [так как если gs1~s2, gs2~s3, то gg s1= g(g s1)= g(s2)=s3].
В нашем случае классы эквивалентности называют транзитивными множествами.
Лемма 1. Число транзитивных классов множества равно
,
где Gобозначает число элементов в группе G и для каждого g (g) обозначает число элементов множество S, остающихся инвариантными при подстановках g, т.е. число элементов sS, для которых gs=s.
Доказательство.
Рассмотрим все пары (g,s), для которых gG, sS, gs=s. Число n таких пар может быть вычислено двумя способами. Во-первых, для каждого фиксированного g можно подсчитать число элементов s, удовлетворяющих условию gs=s, отсюда число пар
n=.
С другой стороны, для каждого sS можно подсчитать число элементов g со свойством gs=s. Обозначив это число через (s), получим
=. (7)
Для фиксированного s элементы группы G, обладающие свойством gs=s, образуют подгруппу группы G, которую обозначим через Gs. Порядок этой группы равен (s).
Если si эквивалентно s, то число элементов g, таких, что gs=si равноGs. Это следует из того, что существует элемент hG, удовлетворяющий условию hs1=s, а теперь равенство gs=s1 означает то же самое, что и hgGs. Таким образом, если s1 и s фиксированы, то число возможностей для g равно как раз числу элементов в Gs.
Соответственно G может быть разбита на подмножества, каждое из которых состоит из Gsэлементов и соответствует ровно одному элементу того класса эквивалентности, в который входит s. Отсюда следует, что этот класс эквивалентности содержит G/Gsэлементов. Поэтому имеем
(s)=
Суммируя по s, получаем, что сумма чисел (s) для всех s, принадлежащих одному и тому же классу эквивалентности, равныG. Следовательно, сумма всех (s) равна взятому Gраз числу классов эквивалентности, т.е. формула (7) доказывает лемму.
4. Функции и классы.
Пусть D и R – конечные множества. Рассмотрим функции, определенные на D, со значениями в R; другими словами, рассмотрим отображения D в R. Множество всех таких функций обозначим через RD. Число элементов в множестве RD равно RD, поскольку если мы хотим построить функцию f, то мы имеем для каждого элемента dD Rвозможностей выбрать f(d), и эти выборы независимы.
Далее предположим, что нам дана группа G множества D. Эта группа вводит отношение эквивалентности в RD: две функции f1 и f2 (обе из RD) называют эквивалентными (обозначим f1~f2), если существует элемент gG, такой, что
f1(gd)= f2(d) для всех dD. (8)
Соотношение (8) может быть кратко записано так: f1g= f2, ибо f1g обозначает сложное отображение “сначала g потом f1”. Легко установить обычные условия эквивалентности: 1) f~f; 2) если f1~f2, то f2~f1; 3) если f1~f2 и f2~f3, то f1~f3. Первое условие следует из того, что тождественная подстановка принадлежит G; второе условие следует из того, что если gG, то обратная подстановка g-1 принадлежит G; и третье – из того, что если g1G, g2G, то g1g2G.
Таким образом, ~ есть отношение эквивалентности, с помощью которого RD разбивается на классы эквивалентности.
Пример 8. Пусть D – множество, состоящее из всех шести граней куба, и пусть G – группа всех подстановок D, которые могут быть получены вращениями куба (см. пример 3). Пусть R состоит из двух слов: красный и белый. Элемент fRD может быть рассмотрен как способ окрашивания куба (так что каждая грань красная, либо белая). Это может быть сделано 26 способами. Если два таких куба, расположенных параллельно окрашены различно, то может случиться, что один из них можно повернуть так, что кубы перестанут казаться различными. В этом случае они принадлежат одному классу эквивалентности.
В нашем примере десять классов эквивалентности, которые могут быть описаны следующим образом (в скобках – число функций в каждом классе эквивалентности): (а) все грани красные (1); (б) пять граней красные, одна белая (6); (в) две противоположные грани белые, остальные четыре красные (3); (г) две смежные грани белые, остальные четыре красные (12); (д) три грани, имеющие общую вершину, красные, остальные белые (8); (е) две противоположные и одна из оставшихся красные, три остальные белые (12); (ж), (з), (и), (к) получаются из (г), (в), (б), (а) заменой слов ‘красный’ на ‘белый’. В качеств примера заметим, что
1+6+3+12+8+12+12+3+6+1=26.
Пример 9. Пусть D – множество, состоящее из трех элементов {1,2,3}, и пусть G – симметрическая группа всех перестановок из D и пусть R состоит из двух элементов x и y. В этом случае восемь функций, а классов эквивалентности четыре. Классы эквивалентности можно обозначить символами x3, x2y, xy2, у3 соответственно. Например, x2y представляет класс отображений f, таких, что два из значений f(1), f(2), f(3) равны x и одно у. Класс эквивалентности x3 состоит только из одной функции, которая определена так:
f(1)=f(2)=f(3)=x.
Полезно рассмотреть также x и y как независимые переменные и поставить в соответствие каждой функции f произведение f(1)f(2)f(3), которое не зависит от порядка сомножителей. Другими словами, так как симметрическая группа дана, то говорить, что две функции f1 и f2 эквивалентны, – это то же, что сказать, что произведение f1(1)f1(2)f1(3) и f2(1)f2(2)f2(3) тождественны. Поэтому классы эквивалентности характеризуются возможными значениями произведений, а именно одночленами x3, x2y, xy2, у3.
5. Вес функции; вес класса эквивалентности
Опять возьмем конечные множества D и R и группу G постановок множества D. Каждому элементу множества R придадим вес. Этот вес может быть числом, или переменной, или вообще элементом коммутативного кольца, состоящего из рациональных чисел. Таким образом, мы можем образовывать суммы и произведения весов, произведения весов на рациональные числа, и эти операции удовлетворяют обычным законам ассоциативности, коммутативности и дистрибутивности. Вес, придаваемый элементу rR, обозначим через (r).
После того как выбраны эти веса мы можем определить вес W(f) функции fRD произведение
W(f)=[f(d)]. (9)
Если f1 и f2 принадлежат одному классу эквивалентности, то они имеют одинаковый вес. Это следует из того факта, что если f1g=f2, gG, то
[f1(d)]= [f1(gd)]= [f2(d)],
поскольку первое и второе произведение имеют одни и те же сомножители, разве что в другом порядке, и в силу коммутативности произведения весов.
Так как все функции, принадлежащие одному и тому же классу эквивалентности, имеют одинаковый вес, мы можем определить в качестве веса класса эквивалентности это общее значение. Таким образом, если F обозначает класс эквивалентности, обозначим вес его через W(F); использование символа W как для веса класс вряд ли вызовет путаницу.
Пример 10. Рассмотрим случай окрашивания куба из примера 8 и образуем кольцо всех многочленов от двух переменных x и y с рациональными коэффициентами. Множество R состоит из элементов красный и белый, которым мы придадим в качестве весов значения x и y соответственно. Десять классов эквивалентности (а), …, (к) имеют теперь веса
x6, x5y, x4y2, x4y2, x3y3, x3y3, x2y4, x2y4, xy5, у6
соответственно. Отсюда можно видеть, что различные классы эквивалентности не обязаны иметь различные веса.
Пример 11. В примере 9 множество R имело два элемента x и y. Если считать x и y переменными, то нет причин, запрещающих дать элементу x вес x, а элементу y – вес y. Теперь символы x3, x2y, xy2, у3 действительно стали весами классов. В этом случае вес характеризует класс: различные классы обладают различными весами.
Пример 12. Если взять (r)=1 для всех rR, то мы будем иметь W(f)=1 для всех функций W(F)=1 для всех классов эквивалентности.
6. Запас и перечень
Как и раньше, имеем множества D и R, и каждый элемент rR обладает весом. Считая R множеством, из которого выбираем значения для функций, назовем R запасом. Так как веса можно складывать, то существует сумма весов; эта сумма называется производящей функцией запаса или перечнем множества R:
Перечень R=. (10)
Пример 13. Терминология наводит на мысль, что перечень дает достаточно точное описание элементов R, однако это верно лишь отчасти. Пусть R – множество, содержащее три коробки мыла (назовем их м1, м2, м3), два пакета чая (назовем ч1, ч2,) и четыре бутылки вина (в1, в2, в3, в4). Если мы возьмем девять переменных м1, м2, м3, ч1, ч2, в1, в2, в3, в4 и придадим элементу м1 вес м1 и т. д., то перечень будет иметь вид
м1+м2+м3+ч1+ч2+в1+в2+в3+в4,
и значение суммы даст полную информацию о запасе. Лавочник обычно применяет более простую систему, так как он не интересуется мелкими различиями между полностью эквивалентными предметами. Он обозначает символами м, ч, в абстрактные понятия ‘коробка мыла’. ‘пакет чая’, ‘бутылка вина’. Затем он придаст всем элементам м1, м2, м3 один вес м; каждому из ч1, и ч2 – один вес ч, в1 и в2 – вес в, элементам в3 и в4 – вес ½в (так как в3 и в4 пол-бутылки, а разница между ними самими к делу не относится). Его перечень имеет вид 3м+2ч+3в. Иногда, впрочем, лавочник, или ревизор интерисуется значением запаса в долларах. Если он оценивает коробку мыла в 3, пакет чая в 1, бутылку вина в 2, а пол-бутылки в 1 доллар, то перечень примет вид 9+2+4+2=17. Теперь перечень просто число; он не дает информации о том, из чего состоит запас, кроме того факта, что его общая стоимость равна 17долларам. В конце концов у лавочника есть еще возможность обучить своего клерка считать: придавая каждому предмету перечня вес 1, можно получить значение перечня, равное общему числу предметов, т.е. 9.
7. Перечень функции
Пусть мы имеем конечные множества D и R и хотим рассмотреть множество RD всех отображений D в R. Каждый элемент rR имеет вес w(r); поэтому каждая функция fÎ RD имеет вес
W(f)=[f(d)].
Тогда перечень множества RD равен перечню множества R в степени, равной числу элементов множества D:
Перечень RD==D. (11)
Это можно увидеть следующим образом. ½D½-я степень может быть записана как произведение ½D½ сомножителей. Если в каждом сомножителе мы выделим один член и возьмем произведение таких членов. То получим один член полного выражения для произведения (которое содержитRD членов, т. е. столько, сколько существует способов выбора). Возьмем некоторое взаимно однозначное соответствие между сомножителями в (11) и элементами множества D; благодаря этому соответствию можно сказать, что выбор членов из каждого сомножителя может быть описан отображением f множества D в R. Функция f соответствует член
[f(d)]
из полного разложения для произведения. Так как этот член равен W(f), мы замечаем, что полное произведение равно сумме всех W(f), т.е. равно перечню множества RD.
Оценим теперь перечень некоторого подмножества S множества RD. Пусть D разбито на несколько непересекающихся компонент D1,…, Dk, так что
D= D1+…+Dk.
Рассмотрим множество S всех функций f, обладающих тем свойством, что f постоянна на каждой компоненте; функция может быть различной на различных компонентах, но не обязательно. Такие функции f можно рассматривать как сложные функции f=, где и определены следующим образом: – функция отображающая d на индекс той компоненты, которой принадлежит d, так что мы всегда имеем dD(d), а – отображение множества {1,…,k} в R. Заметим, что – фиксированная функция, а существует Rk возможностей.
Справедливо следующее соотношение:
Перечень S=. (12)
Это опять может быть получено при рассмотрении полного разложения произведения. Член этого разложения получается выбором одного члена в каждом сомножителе (12), а это означает выбор отображения множества{1,…,k} в R. Следовательно, такое отображение даст член
{[(1)]}… {[(k)]}=.
Если =f, то этот член равен в точности W(f), так как, очевидно,
{[(i)]}= {[(d)]}
и
[f(d)]=W(f).
Таким образом каждая функция fS получается в точности один раз. Следовательно, сумма весов W(f) для всех fS равна сумме всех членов в разложении произведения (12), что и доказывает справедливость (12).
Пример 14. три человека Ч1, Ч2, Ч3 распределяют между собой m фишек так, чтобы Ч1 получил такое количество фишек, что и Ч2. Сколькими способами это можно сделать? Мы интересуемся не отдельными фишками, а только тем, сколько фишек получает каждый человек. Иначе говоря, мы хотим получить функции f определенные на множестве D={ Ч1, Ч2, Ч3},с областью значений R={0,1,2,…} и ограничениями f(Ч1)=f(Ч2) и f(Ч1)+f(Ч2)+f(Ч3)=m. Положим {Ч1, Ч2}=D1, {Ч3}=D2.
Возьмем переменную x и предадим элементам 0,1,2,…множества R веса 1, x, x2, x3,… соответственно. Таким образом, функции, которыми мы интересуемся, имеют вес xm.
Из (12) перечень всех функций, постоянных на каждом Di, равен
(1 +x2+x4+…)(1+x+x2+ …). (13)
Искомое число есть коэффициент при xm в этом разложении. Поскольку
(1 - x2)-1(1 – x)-1=(1 + x)-1+(1 – x)-2+(1 – x)-1,
то для требуемого числа функций получаем
(m+1) + [1+(-1)m],
т. е. ½m +1, если m четно, и ½m+½, если m нечетно. Легко получить этот результат непосредственно: заметим, что требуемое число может быть интерпретировано как число представлений натурального числа m, в Виде суммы двух натуральных чисел, одно из которых четно.
То, что запас есть бесконечное множество, а перечень – сумма бесконечного ряда, не должно нас особенно волновать. Мы можем обрезать запас, заменив его множеством {0,1,2,…,m}, остальные элементы не будут играть никакой роли в задаче, в силу ограничения f(Ч1)+f(Ч2)+f(Ч3)=m. Более того, коэффициент при xm в (13) равен коэффициенту при xm в выражении
(1 +x2+x4 +…+x2m)( 1+x+x2+ …+xm).
8. Перечень классов эквивалентности, теорема Пойа
Снова рассмотрим конечные множества D и R и группу подстановок G множества D. Элементы R имеют вес (г), и, согласно (9), функция fÎ RD и класс F имеют веса W(f) и W(F). Вместо перечня функции , определенного в (11), будем теперь искать перечень множества всех классов эквивалентности. Этот перечень дается следующей теоремой
Теорема 1. (Основная теорема Пойа) Перечень классов эквивалентности равен
=PG{ (r)]2, w(r)]3,…}, (14)
где PG – цикловой индекс. В частности, если все веса выбраны равными 1, получаем
число классов эквивалентности = PG(R,R,R,…). (15)
Доказательство.
Пусть – одно из возможных значений, которое может принимать вес функции. Пусть S множество всех функций f, fÎ RD, удовлетворяющих условию W(f)=.
Если gG и f1=f2g, то f1 и f2 имеют одинаковый вес (см. п. 5). Отсюда если f1S, то f1g-1S. Таким образом, каждому элементу gG соответствует отображение g множества S в себя, определенное так:
gf=fg-1;
здесь g – подстановка, так как она имеет обратную .
Отображение g→g удовлетворяет условию гомоморфизма (6). Поэтому если gG, gG, то (6) выполняется, поскольку для каждого fS имеем
ggf=f(gg)-1, g(g)f=g(fg)-1= fg-1g-1, (gg)-1=g-1g-1.
Два элемента f1 и f2 из S эквивалентны в смысле п. 3 тогда и только тогда, когда они эквивалентны в смысле п. 4: существование элемента g группы G, такого, что gf2=f1, означает то же самое, что и существование элемента g группы G, такого, что f2=f1g. Следовательно, классы эквивалентности, поскольку они существуют в S, суть классы эквивалентности из п. 3. Тогда лемма 1 показывает, что число классов эквивалентности, поскольку они содержаться в S, равно
, (16)
где (g) обозначает число функций f, таких, что W(f)=, fg-1= f (или, что то же самое, f=fg).
Все классы эквивалентности, принадлежащие S, имеют вес ; поэтому если мы умножим (16) на и просуммируем по всем возможным значениям , то получим перечень классов эквивалентности
=.
Очевидно,
=
где означает, что суммирование происходит по всем fÎ RD, для которых f=fg. Отсюда
=. (17)
для того чтобы оценить заметим, что g – подстановка множества D, и поэтому D распадается на циклы, элементы которых циклически переставляются подстановкой g. Условие f=fg означает, что
f(d)=f(gd)= f(g2d)=…,
поэтому функция f постоянна на каждом цикле D. Обратно, каждая функция f, постоянная на каждом цикле, автоматически удовлетворяет условию f=fg, поэтому g(d) принадлежит тому же циклу, что и d. Таким образом, если циклы суть D1, D2,…, Dk, то сумма есть как раз перечень, полученный в п. 7, который выражается формулой (12).
Пусть <…> – тип подстановки g. Это означает, что среди чисел D1, D2,…, Dkчисло 1 встречается b1 раз, число 2 – b2 раз и т. д. Следовательно, имеем
=…. (18)
Число сомножителей конечно, но мы не будем стремиться записывать последний из них; в конце концов можно считать, что все bi, начиная с некоторого i равны нулю, и произведение бесконечного числа единиц равно также единице.
Выражения (18) может быть получено подстановкой
t1= t2=(r)]2, t3=w(r)]3,…
в произведении …, которое является членом, соответствующим g в GPG (см. п. 2). Суммируя по g и деля на G, мы заключаем, что значение 17 получено предыдущей подстановкой из PG(t1, t2, t3,…) и это доказывает теорему Пойа.
Пример 15. Рассмотрим пример 8. Здесь D – множество граней куба, G – группа вращений, R – множество двух цветов: красного и белого.
Согласно формуле (15), число способов окрашивания равно PG(2,2,2,…), а цикловой индекс PG был дан в примере 3. Мы получаем
(26+324+623+623+822)=10,
то же число, если проверить, было получено в примере 8.
Возникает вопрос: сколько классов эквивалентности окрашиваний имеют четыре красные грани и две белые.
Для этого дадим вес x красному цвету и y белому и найдем перечень классов эквивалентности; по формулам (14) и (1), он равен
[(x+y)6+3(x+y)2(x2+y2)+6(x+y)2(x4+y4) +6(x2+y2)3+8(x3+y3)2].
Коэффициент при x4y2 равен
(15+9+6+18+0)=2.
В самом деле, существует ровно два класса эквивалентности функций, при которых четыре грани окрашены в красный цвет [(c) и (d) в примере 9]. Для полного перечня классов эквивалентности мы легко получаем
x6+x5y+2x4y2+2x3y3+2x2y4+xy5+y6,
что согласуется с примером 10.
Литература
1. Дж. Риордан “Введение в комбинаторный анализ” ИЛ, М., 1962
2. В. Липский “Комбинаторика для программистов” M., Мир, 1988
3. Г. Эндрюс “Теория разбиений” M., Наука, 1982
4. Ф. Харари, Э. Палмер. “ Перечисление графов” М., Мир, 1977
5. В. А. Емеличев, В. А. Мельников, Сарванов В. И. Тышкевич Р. И. “Лекции по теории графов” M., Наука, 1990
6. Э. Рейнгольд, Ю. Невергельт, Н. Део “Комбинаторные алгоритмы. Теория и практика ” M., Мир, 1980
7. Сб. статей под редакцией Э. Беккенбаха “Прикладная комбинаторная математика”. М. Мир, 1968
1 Материал взят из книги Дж. Риордан ‘Введение в комбинаторный анализ’ ИЛ, М., 1962
2 Г. Эндрюс “Теория разбиений” M., Наука, 1982
3 В этих обозначениях индекс е у P означает четное (even) число частей разбиения, индекс о – нечетное (odd) число частей разбиения; D обозначает множество всех разбиений n на различные(different) числа .
4 Г. Эндрюс, Теория разбиений, М. Наука.1982
5Ф. Харари, Э. Палмер. “ Перечисление графов” М., Мир, 1977
6 Т. е. переводит корень переводит одного графа в корень другого.
7 Ф. Харари, Э. Палмер. “ Перечисление графов” М., Мир, 1977 сс. 24-26
8Теорема Лагранжа для кольца формальных степенных рядов полностью рассмотрена в книге: Я. Гульден, Д. Джексон, “Перечислительная комбинаторика”, М., Наука, 1990
9 В. А. Емеличев, В. А. Мельников, Сарванов В. И. Тышкевич Р. И. “Лекции пои теории графов” M., Наука, 1990
10 см. Ф.Р.Гантмахер “Теория матриц” М.: Наука, 1966”, стр. 20
11 Э. Рейнгольд, Ю. Невергельт, Н. Део “Комбинаторные алгоритмы. Теория и практика ” M., Мир, 1980
12 Н. Дж. Де Брейн: ‘Теория перечисления Пойа’. Сб. статей под редакцией Э. Беккенбаха “Прикладная комбинаторная математика”. М. Мир, 1968