В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 10
Текст из файла (страница 10)
Найти числа Стирлинга второго рода:(a) S (n, n − 1) и(b) S (n, n − 2).2. Найти общие решения рекуррентных соотношений:(a) an+2 − 4an+1 + 3an = 0;(b) an+2 − a + n + 1 − an = 0;(c) an+3 + 3an+2 + 3an+1 + an = 0.3. Найти общее решение системы рекуррентных соотношенийan+1 = bn + 5,bn+1 = −an + 3.4. Решить рекуррентные соотношения:(a) an+2 − 2an+1 + 2an = 2n , a0 = 1, a1 = 2;(b) an+2 + an+1 − 2an = n, a0 = 1, a1 = −2;(c) an+2 − 4an+1 + 2an = 2n , a0 = 1, a1 = 2;(d) an+2 + an+1 − 6an = 5 · 2n+1 , a0 = 2, a1 = 1.5.
Пользуясь аппаратом производящих функций, вывести формулу суммы кубов первых n натуральных чисел.34ГЛАВА 1. КОМБИНАТОРИКА1.3Простейшие перечислительные задачиВводные замечания. В этом параграфе рассматриваются задачи, представляющие собой нахождение числа классовэквивалентности комбинаторных конфигураций. Чтобы пояснить это, рассмотрим пример. Найдем число раскрасокграней куба в два разных цвета (например, в белый и черный): всего (не учитывая симметрий куба) их 26 = 64.
Теперьотождествим раскраски, получающиеся друг из друга поворотами куба. Тогда все различные раскраски описываются вследующем списке:1. все грани белые (1 раскраска),2. одна грань белая, остальные — черные (1 раскраска),3. две грани белые, четыре — черные (2 раскраски: в одной белые грани имеют общее ребро, а в другой не имеют),4. три грани белые, три — черные (2 раскраски: в одной белые грани имеют общую вершину, а в другой не имеют),5. четыре грани белые, две — черные (2 раскраски: в одной черные грани имеют общее ребро, а в другой не имеют),6. пять граней белых, одна — черная (1 раскраска),7. все грани черные (1 раскраска).Таким образом, всего 10 классов эквивалентности и столько же соответствующих им неэквивалентных раскрасок.Чтобы обосновать многие из последующих рассуждений, сформулируем и докажем следующую теорему.Теорема 1.6 (Кэли). Любая конечная группа G изоморфна некоторой подходящей подгруппе симметрической группы Sn .
Док-во. Пусть |G| = n; G = {g0 = e, g1 , . . . , gn−1 }. Для любого g ∈ G рассмотрим подстановкуg0g1...gn−1gb =g · g0 g · g1 . . . g · gn−1b ⊆ Sn . Действительно,Она является инъективным отображением G → Gg · gi = g · g j =⇒ g−1 · g · gi = g−1 · g · g j =⇒ gi = g j .Таким образом, отображение gb является перестановкой, а, следовательно, и взаимно однозначным.
Осталось провеb выполняется равенство gb1 · gb2 = g\bрить только, что в G1 · g2 ∀ g1 , g2 , то есть G — группа. Действительно, пустьg0... y ...gn−1g1 ↔ gb1 =,g1 · g0 . . . z . . . g1 · gn−1g0... x ...gn−1g2 ↔ gb2 =,g2 · g0 . . . y . . . g2 · gn−1g0...gn−1g1 · g2 ↔ g\.1 · g2 =(g1 · g2 ) · g0 . . . (g1 · g2 ) · gn−1Тогда согласно определению композиции перестановокgb1 · gb2 (x) = gb1 (gb2 (x)) = gb1 (y) = z,g\1 · g2 (x) = (g1 · g2 ) (x) = g1 (g2 · x) = g1 · y = z.b установлено взаимно однозначное отображение, сохраняющее внутренний закон компоТаким образом, между G и Gзиции, то есть изоморфизм.Построенное в теореме 1.6 представление конечной группы называется левым регулярным представлением Кэли.Правое регулярное представление, которое может быть построено по аналогии, называется антиизоморфизмом.Теорема 1.7 (Лагранж). Пусть G = {α0 = e, α1 , .
. . , αn−1 } — некоторая конечная группа, а множество H ={β0 = e, β1 , . . . , βm−1 } ⊆ G — ее подгруппа (m 6 n). Тогда m | n. Док-во. Обозначив S0 = H, γ0 = e, рассмотрим множество G \ S0 . Если оно пусто, то теорема выполнена, в противном случае выбираем из него произвольный элемент γ1 .S0 γ0 = e :S1γ1 :S2γ2 :.........Skγk :β0 ,γ1 β 0 ,γ2 β 0 ,.....γk β 0 ,β1 ,γ1 β 1 ,γ2 β 1 ,.....γk β 1 ,...,...,...,.......,βm−1γ1 βm−1γ2 βm−1......γk βm−1(1.70)351.3. ПРОСТЕЙШИЕ ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИОбозначим S1 = γ1 βi , ∀ i = 0, m − 1 . Среди них нет одинаковых и S0 ∩ S1 = ∅: действительно, если γ1 βi = γ1 β j ⇒ βi =β j ⇒ i = j (домножением справа на γ1−1 ), а если γ1 βi = β j ⇒ γ1 = β j βi−1 ∈ H. Если (G \ S0 ) \ S1 = ∅, то теорема доказана:порядок группы равен удвоенному порядку подгруппы.
В противном случае выбираем произвольный γ2 ∈ (G \ S0 ) \ S1 иповторяем те же рассуждения. На k-ом шаге мы получаем набор Sk = {γk β0 , γk β1 , . . . , γk βm−1 }, причем все элементы внем различны и не встречались во множествах Si , ∀ i = 0, k − 1. Действительно пусть ` < k иγk βi = γ` β j ⇒ γk = γ` β j βi−1 = γ` βr ∈ S` ,| {z }∈Hно γk выбиралось из дополнения S` . Остановка этого процесса может произойти только в случае(· · · ((G \ S0 ) \ S1 ) \ · · · ) \ Sm = ∅,но тогда ` · m = n, где m — порядок H, что и требовалось доказать.Основные леммы.Определение 1.3.1. Индексом подгруппы H группы G называется число[G : H] =|G|.|H|Пусть N = {1, 2, . . .
, n}, G — подгруппа Sn . Введем следующее бинарное отношение на элементах множества N:a ∼ b (mod G) ⇐⇒ ∃ π ∈ G : π (a) = b.Легко проверить, что оно удовлетворяет аксиомам1. рефлексивности:π = e ∈ G =⇒ a ∼ a (mod G),2. симметричности:π ∈ G ⇐⇒ π −1 ∈ G =⇒ a ∼ b (mod G) ⇐⇒ b ∼ a (mod G),3.
транзитивности:π1 , π2 ∈ G =⇒ π1 · π2 = π ∈ G =⇒ (a ∼ b (mod G)) & (b ∼ c (mod G)) =⇒ a ∼ c (mod G).Иными словами, оно является отношением эквивалентности. Оно разбивает исходное множество N на классы эквивалентности. В двух крайних случаях G = Sn и G = {e} соответственно все элементы эквивалентны и никакие два неявляются эквивалентными.Определение 1.3.2. Орбитой элемента a ∈ N называется множествоOa = {b ∈ N | a ∼ b (mod G)} .Так как класс эквивалентности порождается любым своим представителем, допустимо обозначать через Oa орбитупроизвольного элемента a ∈ N.
Найдем ее. Пусть G = {α0 = e, α1 , . . . , αr−1 }, r = ` · m. Тогда среди элементов e (a) =α0 (a) , α1 (a) , . . . , αr−1 (a) могут быть повторы, но среди них содержатся все элементы, эквивалентные a и только они.То есть, множество этих элементов и составляет Oa . Далее, a ∼ b (mod G) ⇔ Oa = Ob ⇒ |Oa | = |Ob |.Определение 1.3.3. Стабилизатором элемента a называется множество элементовGa = {αi ∈ G | α i (a) = a} .Легко проверить, что Ga — подгруппа G.Утверждение 1.3.1.[G : Ga ] = |Oa |(|Ga | |Oa | = |G|) . Док-во. Пусть Ga = {β0 = e, β1 , . .
. , βm−1 }. Покажем, что среди элементов (1.70) не встречается одинаковых. Этиммы и покажем, что мощность орбиты является индексом стабилизатора.S0 γ0 = e :S1γ1 :S2γ2 :.........Skγk :.........S`γ` :β0 ,γ1 β 0 ,γ2 β 0 ,.....γk β 0 ,.....γ` β0 ,β1 ,γ1 β 1 ,γ2 β 1 ,.....γk β1 ,.....γ` β1 ,...,...,...,.......,.......,βm−1γ1 βm−1γ2 βm−1......γk βm−1......γ` βm−1e (a)γ1 (a)γ2 (a).....γk (a).....γ` (a)36ГЛАВА 1.
КОМБИНАТОРИКАПусть i > 1, k > s > 1. Тогдаγi β j (a) = βs (a) = a =⇒ γi βi ∈ Ga =⇒ γi ∈ Gaγk β j (a) = γs β j (a) =⇒ γk (a) = γs (a) =⇒ ∃ β ∈ Ga :γs−1 γk(противоречие)= β =⇒ k = s(противоречие.)Таким образом, действительно, Oa = ` + 1.Если a ∼ b (mod G), то |Ga | = |Gb | и между стабилизаторами этих двух элементов можно установить изоморфизм.Действительно, пусть π (a) = b, g ∈ Ga . Тогда πgπ −1 ∈ Gb .Лемма 1.3.1 (Бернсайд). Пусть N (G) — число орбит по группе G. ТогдаN (G) =1∑ λ1 (π) ,|G| π∈Gгде λ1 (π) — число неподвижных элементов перестановки π (первая координата вектора типа перестановки).
Док-во. Рассмотрим таблицу из нулей и единиц, строки которой соответствуют элементам N, а столбцы — перестановкам из G.Z GNZπ0........πm−1|G1 |11...........|G2 |21...................... 0 .................. 1 .......|Gn |n1...........λ1 (π0 ) . . . . . . . . λ1 (πm−1 )Элемент этой таблицы ti j для i = 1, n, j = 0, m − 1 определяется по следующему правилу:(0, π j (i) 6= i,ti j =1, π j (i) = i.Число единиц в i-ой строке есть порядок стабилизатора элемента i, а число единиц в j-ом столбце есть число неподвижных элементов j-ой перестановки. Обозначим через O i орбиту i-го класса эквивалентности для i = 1, N (G). Далее,в силу того, что мощности стабилизаторов эквивалентных элементов равны, а также того, что |Ga | |Oa | = |G| получаем,na | + · · · + |Ga | + |Gb | + · · · + |Gb | + · · · + |Gc | + · · · + |Gc | = |G| · N (G)∑ λ1 (π) = ∑ |Gi | = |G|{z} |{z}|{z}π∈Gi=1O1O2O N(G)=⇒ N (G) =где a из первого класса эквивалентности, b — из второго, c — из N (G)-го.1∑ λ1 (π) ,|G| π∈GВведем на N весовую функцию ω : N → R такую, что a ∼ b (mod G) ⇒ ω (a) = ω (b).
Весом орбиты назовем вес еепроизвольного представителя: W (Oa ) = ω (a). Тогда справедлива следующая лемма.Лемма 1.3.2 (Бернсайд, весовой вид).N(G)∑Wj=11Oj =∑ ∑ ω (a) .|G| π∈Ga=π(a) Док-во. Рассмотрим таблицу весов, аналогичную используемой в лемме 1.3.1.Z Gπ0NZ1ω (1)2ω (2).........nω (n). .
. πm−1...........................|G1 ||G2 |....|Gn |371.3. ПРОСТЕЙШИЕ ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИЭлементы этой таблицы определяются по правилу: wi j = ω (π j (i)) для i = 1, n, j = 0, m − 1. Отметим, что если i — неподвижный элемент перестановки π j , то wi j = ω (i). Воспользуемся теперь тем же приемом: перейдем от суммы по всемэлементам к сумме по классам эквивалентности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
