Лекции по прикладной алгебре. v2.0 (1127112), страница 23
Текст из файла (страница 23)
. . (6)t = (1234)(5)(6)t2 = (12)(34)(5)(6)T ype(g)h 6, 0, . . . ih 2, 0, 0, 1, 0, 0 ih 2, 2, 0, . . . iw(g)x61x21 x4x21 x22Прикладная алгебраТеория перечисления ПойаЗадачи310 / 432Решение (ТП-4, продолжение)Цикловой индексPG (x1 , . . . , x4 ) =1 5x1 + 2x1 x4 + x1 x22 .4Число различных раскрасок граней в 3 цвета:PG (3, . . . , 3) =1 513 + 2 · 32 + 3 3 =243 + 18 + 27 =44288= 72.=4Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-5)Сколько различных ожерелий можно составить из 7-ми бусиндвух цветов (красного и синего).Или: сколькими различными способами можно раскраситьвершины правильного семиугольника в два цвета?311 / 432Прикладная алгебраТеория перечисления ПойаЗадачи311 / 432Задача (ТП-5)Сколько различных ожерелий можно составить из 7-ми бусиндвух цветов (красного и синего).Или: сколькими различными способами можно раскраситьвершины правильного семиугольника в два цвета?РешениеГруппа симметрии правильного семиугольника — группадиэдра: D7 = h t, f i , t7 = f 2 = e , |D7 | = 2 · 7 = 14.D7 = h e, t, t2 , t3 , t4 , t5 , t6 , f, tf, t2 f, t3 f, t4 f, t5 f, t6 f i.Элемент группы get, t2 , .
. . , t6f, tf, . . . , t6 fT ype(g)h 7, 0, . . . ih 0, 0, 0, 0, 0, 0, 1 ih 1, 3, 0, . . . iw(g)x71x7x1 x32Прикладная алгебраТеория перечисления ПойаЗадачи312 / 432Решение (ТП-6)Цикловой индексPD7 (x1 , . . . , x7 ) =1 7x1 + 6x7 + 7x1 x32 .14Число различных раскрасок в r цветов —P (r, . . . , r) =1 7r + 6r + 7r4 .14Для r = 2 имеемP (2, . . . , 2) =128 + 12 + 1121 72 + 12 + 7 · 16 ==1414252== 18.14Прикладная алгебраТеория перечисления ПойаЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды313 / 432Прикладная алгебраТеория перечисления ПойаЧто надо знатьРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств314 / 432Прикладная алгебраТеория перечисления ПойаЧто надо знатьРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать315 / 432Прикладная алгебраТеория перечисления ПойаЧто надо знатьДействие группы на множестве: два определения. g-циклы,тип перестановки. Орбиты.Неподвижные точки группы преобразований: фиксатор истабилизатор. Лемма Бёрнсайда.Группы вращений платоновых тел. Примеры.Применение леммы Бёрнсайда для решениякомбинаторных задач. Примеры.Действие группы вращений куба на его элементы.Цикловой индекс: определение и свойства.
Вычислениечисла орбит через цикловой индекс. Примеры.Решения комбинаторной задачи об ожерельях.Теорема Редфилда-Пойа и её применение для решениякомбинаторных задач. Примеры.316 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды317 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множествРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств318 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать319 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множеств320 / 432Частично упорядоченные множества: определение и примерыОпределениеПару P = h P, 6 i, где P — непустое множество, а 6 —рефлексивное, антисимметричное и транзитивное бинарноеотношение на нём, называют частично упорядоченныммножеством (сокращённо ч.у.
множеством).Рефлексивность: x 6 x;Антисимметричность: (x 6 y) N (y 6 x) ⇒ x = y;Транзитивность: (x 6 y) N (y 6 z) ⇒ x 6 z.Примерыh P(M ), ⊆ i — классический пример ч.у. множества(упорядочивание множеств по включению, M 6= ∅);h N, 6 i и h N, | i — два упорядочивания одного множества.Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множествЧ.у. множество P = h P, 6 i — основные понятия:если (x 6 y) ∨ (y 6 x), то x и y сравнимы (x ∼ y), иначе онинесравнимы (x y);полный (линейный) порядок, если ∀x, y (x ∼ y);если в P нет ни одной пары различных сравнимых элементов,то это тривиально упорядоченное множество;x непосредственно предшествует y (y непосредственно следуетза x), если x 6 z 6 y ⇒ (z = x) ∨ (z = y) (x l y);{ x ∈ P | a 6 x 6 b } — интервал [ a, b ];defv1 6 . . . 6 vn = [v1 , . .
. , vn ] — цепь (n или n), а совокупностьпопарно несравнимых элементов — антицепь в P;цепь максимальная (или насыщенная), если при добавлении кней любого элемента она перестаёт быть цепью;если ∀x, y ( (x 6 y) ⇒ (y ≤ x) ), то ≤ — двойственныйdefпорядок на P , > = ≤ или 6d =>.321 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множеств322 / 432Диаграммы Хассе◦◦◦◦◦◦◦◦[[[◦◦[[ ◦[◦Рис. 4. Диаграммы 4-х нетривиальных непомеченных 3-элементныхч.у. множествПрикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествЧ.у.
множества: особые элементыОпределениеЭлемент u ∈ P ч.у. множества h P, 6 i называют:максимальным, если u 6 x ⇒ u = x,минимальным, если u > x ⇒ u = x,наибольшим, если x 6 u,наименьшим, если x > uдля любых x ∈ P .323 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множествЧ.у. множества: особые элементыОпределениеЭлемент u ∈ P ч.у. множества h P, 6 i называют:максимальным, если u 6 x ⇒ u = x,минимальным, если u > x ⇒ u = x,наибольшим, если x 6 u,наименьшим, если x > uдля любых x ∈ P .Элемент наибольший, если все другие элементы содержатся внём, и он максимальный, если нет элементов, содержащих его(аналогично для наименьшего и минимального элементов).323 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествОсобые элементы ч.у. множества: пример• — максимальные элементы;• — минимальный и наименьший элемент;Наибольший (1) и наименьший (0) — граничные элементы.В конечном ч.у. множестве имеется как минимум по одномумаксимальному и минимальному элементу.324 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествЧ.у.
множество h { 1, . . . , 18}, | i16[[ 12 [[ 8[[96 [4' 15 [AA '10''' 14'''[A''[[''['A'''A''A'A' 13' '3 hh 11 2 [57' 17Ahhhh [''A'hhhh[ AA'A'''hh 'A A''1811 — наименьший элемент, • — максимальные.325 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествРанжированные ч.у. множестваЦепное условие Жордана-ДедекиндаВсе максимальные цепи между двумя данными элементамилокально конечного ч.у.
множества имеют одинаковую длину.Если ч.у. множество удовлетворяет условиюЖордана-Дедекинда и имеет наименьший элемент 0, то можноопределить функцию ранга ρ:12ρ(0) = 0;a l b ⇒ ρ(b) = ρ(a) + 1.Такое множество должно иметь слои.Если множество ранжируемо, то любой его слой (но нетолько!) является антицепью.326 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествПорядковые гомоморфизмыОпределениеОтображение ϕ : P → P 0 носителей ч.у.
множеств P и P0называется соответственноизотонным (монотонным, порядковым гомоморфизмом),если x 6 y ⇒ ϕ(x) 6 ϕ(y);обратно изотонным, если ϕ(x) 6 ϕ(y) ⇒ x 6 y;антиизотонным, если x 6 y ⇒ ϕ(x) > ϕ(y).Если ϕ изотонно, обратно изотонно и инъективно, то этовложение или (порядковый) мономорфизмϕ(символически P ,→ P 0 ).Сюръективный мономорфизм — (порядковый) изоморфизмϕ∼ P 0 или P =∼ P 0 ).(символически P =Изоморфизм ч.у. множества в себя —(порядковый) автоморфизм.327 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
