Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 139
Текст из файла (страница 139)
Если вершины в одном цикле красные, а в другом — синие, то имеются две возможности выбора синих вершин; тогда в другом цикле вершины должны быть красные. Запишем эту структуру в форме ЬЬ+ 26т + тт (Ь вЂ” синий, г — красный), где знак + можно читать как "или". Для удобства запишем эту структуру как Ьг+2Ьт+тг. Заметим, что алгебраически это (Ь+т)г.
Другой цикл задается сг, что представляет один цикл длины 2. Поскольку это единственный цикл длины 2, то в нем обе вершины должны быть окрашены в красный или обе — в синий. Запишем эту структуру как ЬЬ+ тт, или Ьг -ь тг. Поскольку структура раскраски двух вершин есть (6+ т)г, а для других двух вершин эта структура есть Ьг+т', то структура раскрасок, не изменяющихся при перестановке бы может быть описана как (Ь+ т)г(Ьг + тг). Допустим, что имеется цикл с" . Это произведение и циклов длины т.
Пусть В представляет раскраску цикла красным, а В представляет раскраску цикла синим. Таким образом, ЮВ" г представляет раскраску г циклов красным и и — г циклов — синим. Количество способов раскраски г циклов красным и и — 1' циклов синим равно количеству вариантов выбора г циклов из и циклов для окраски в красный цвет. Это равно С(п, г) = (").
Поэтому будем использовать запись (")В'В" г для обозначения раскрасок сг красными и п — г' синими циклами. Но это не что иное, как коэффициент при ЮВ" г в разложении (Л + В)". Таким образом, можно представить раскраски цикла с„", как (В+В)". Поскольку каждая раскраска цикла состоит из раскраски т вершин, положим В = т и В = Ь Теперь структуры раскрасок для с" можно описать выражением (т + Ь"')". В результате для каждой перестановки получим следующее множество раскрасок, которое назовем перечнем раскрасок для перестановки.
РАздел 49.2. теорема поев 795 меняют С. Поскольку каждая перестановка переводит раскраску в раскраску с той же цикловой структурой, то в сумму наших перечней раскраски, эквивалентные С и описываемые той же структурой, вошли (С( раз. Таким образом, для определения перечня неэквивалентных структур раскрасок мы определяем общий перечень инвариантных раскрасок как (С! = 8 и для нашего перечня структур раскрасок получаем 1 8 -(8 4+8"ь+ 15 'ь'+8 ь'+8ь4) = '+ 'ь+2 'ь'+ ь'+ь". Для получения полного перечня структур мы брали инвариантные раскраски из цикловой структуры каждой перестановки, а затем суммировали их. Можно было сначала сложить цикловые структуры, как в колонке 2 приведенной выше таблицы, а затем для получения такого же результата перевести циклы в раскраски.
Таким образом, для суммы с4 + 2сг|сг + Зсг ~+ 2с4 получаем полный перечень структур ( 4+Ь4)+2( +Ь)г( г+Ьг)( Ь)г+8( г Ьг)г+2( 4 Ь4) что после раскрытия скобок и приведения подобных членов равно 4+8 3~+18 гьг+8 ьз+8Ь4 Таким образом, если сумма циклов имеет вид а1с" ,+ агс" ,+ азс1' +. + а„с'„", то перечень неэквивалентных структур раскрасок имеет вид Рс(т-,ь тг, Ь.
т™, Ь„) 1 = — (а1(т + Ь)»1 + аг(тг + Ьг)»» +... + а (т» + Ь»)е ) !Я~ Если бы мы использовали три цвета: красный (т), белый (4о) и синий (Ь), то перечень неэквивалентных структур раскрасок имел бы вид р (т + и + Ь, тг + 4ог + Ьг, т» + ш» + Ь») . В общем случае имеет место следующая теорема. ТЕОРЕМА 19.5. (Теорема Пойа о подсчете) Если задано множество Я, цикловой индекс Рс(сысг,,,,,с„) и цвета йыйг,йз,.,.,й, то перечень неэквивалентных структур раскрасок имеет вид ПРИМЕР 19.6. Снова рассмотрим двухцветные раскраски квадрата с использованием только вращений. Пусть С = (1,р,,рг,рз).
В таком случае получаем таблицу 786 ГЛАВА 19. Перечисление иветов р ( + б 2 + 62 3 + бз 4 + 64) (( + б)4 + ( 2 + бг)2+ 2( 4 + 64)) 4 = т4 + тзь+ 2тгбг + -ьз + 64 что дает совпадение перечня неэквивалентных структур раскрасок с уже рассмотренным случаем, в котором была использована вся группа симметрий.
П ПРИМЕР 19.7. Пусть о — вершины треугольника, а С вЂ” группа симметрий треугольника. Найдем перечень неэквивалентных структур раскрасок. Пусть р1 = (123) и рг = (132) — вращения вершин. Пусть бг = (1)(23), бг = (13)(2) и бз = (12)(3) — отражения, а 1 = (1)(2)(3) — тождественное преобразование. В таком случае имеем таблицу з Р (т + Ь тг + бг тз + бз) Ит + б)з + 3(тг + бг)(т + б) + (тз 4 бз)) 6 = тз+ тгб+ тбг+ бз ° УПРАЖНЕНИЯ В приведенных ниже заданиях допускается, что все вращения и отражения возможны.
1. На браслете пять бусинок. Если их нужно раскрасить двумя цветами, то сколько раскрасок существует? Сколько существует трехцветных раскрасок? 2. Сколькими способами можно раскрасить клетки шахматной доски 3 х 3? 3. Сколько существует способов раскраски равностороннего треугольника тре- мя цветами? РАЗДЕЛ 10.2. Теорема Пода 787 4. Сколько существует способов раскраски куба двумя цветами? 5.
Сколько существует способов раскраски правильного пятиугольника двумя цветами? 6. Сколько существует способов раскраски правильного пятиугольника тремя цветами? 7. Сколько существует способов раскраски правильного восьмиугольника двумя цветами? 8. Найдите структурный перечень двухцветных раскрасок браслета с семью бусинками. 9. Найдите структурный перечень двухцветных раскрасок прямоугольника, который не является квадратом.
10. Найдите структурный перечень трехцветных раскрасок равностороннего треугольника. 11. Найдите структурный перечень двухцветных раскрасок пятиугольника. 12. Найдите структурный перечень двухцветных раскрасок тетраэдра. 13. Найдите структурный перечень двухцветных раскрасок шахматной доски размера 3 х 3. 14. Найдите структурный перечень двухцветных раскрасок восьмиугольника.
15. Десять кеглей выставлены в треугольник стандартным образом. Найдите структурный перечень двухцветных раскрасок этих кеглей без ограничений на движения. Найдите структурный перечень при условии, что разрешены только вращения. РЯЗДЕЛ 20. 7. Кольца и области целостности 789 8. Для всех к, у и з из Л выполняются следующие законы дистрибутивности: х (у + з) = (х . у) + (х . з) (у + з) к = (у х) + (з к). Если во множестве Л существует элемент 1 (мультипликативная единица, или нейтральный элемент относительно умножения) такой, что 1.г = т 1 = г для всех г из Л, то множество Л называется кольцом с единицей.
Если т.г' = г' г для всех т и г' из Л, то множество Л называется коммутативным кольцом. Заметим, что кольцо Л является группой относительно сложения и полу- группой относительно умножения. Примером колец относительно обычных операций сложения и умножения могут служить целые, действительные, рациональные и комплексные числа. Другими примерами колец являются множество (и х п)- матриц для фиксированного целого числа и и множество полиномов — оба относительно обычных операций сложения н умножения.
Среди перечисленных выше колец только матрицы не образуют коммутативное кольцо. ОПРЕДЕЛЕНИЕ 20.2. Областью целостности называется коммутативное кольцо с единицей, не совпадающей с О, так что из условия аЬ = О следу- ет а =О или 6=0. Множества целых, рациональных и действительных числа являются областями целостности. Множество (2 х 2)-матриц не является областью целостности, поскольку О О О О О О т.е. произведение двух ненулевых матриц может быть нулевой матрицей. Области целостности обладают свойством сокращения относительно умножения, которое означает, что если аЬ = ас и а ф О, то 6 = с.
Это очень важно, т.к. кольца не обязательно содержат взаимно обратные элементы, поэтому не всегда возможно умножить обе части уравнения аЬ = ас на а ' и получить Ь = с. Доказательство следующей теоремы оставляем читателю. ТЕОРЕМА 20.3. Пусть Л вЂ” коммутативное кольцо с единицей. Кольцо Л является областью целостности тогда и только тогда, когда из аЬ = ас следует, что Ь = с для всех 6, с и ненулевых элементов а из Л.
Теперь проверим, является ли множество классов вычетов Е„ кольцом или областью целостности. Нетрудно убедиться, что Е„ всегда является кольцом. Ранее было показано, что У„ удовлетворяет всем законам кольца, за исключением законов дистрибутивности. Выполнение законов дистрибутивности также легко показать. Рассмотрев, однако, Яв, можно обнаружить, что [3[ 0 [2[ = [О[, и, следовательно, множество Ув не является областью целостности. На самом деле, если 790 Г71АВА 20. Кольце, областц целостности и поля число и не простое, например, и = ро, то (р] О [д] = [0], поэтому У„не будет областью целостности.
Если и — простое число, то для заданного целого числа а ~ 0 (глоб и), не равного нулю, из теоремы 10.6 следует, что сравнение ах = 1 (глоб и) имеет решение, например, а'. Следовательно, имеем [а] О [а') = [Ц, и для каждого элемента существует обратный элемент. Поэтому, если а6 = 0 и а ф О, то Ь = а 'аЬ = а '0 = О.
Таким образом, если и — простое число, то множество У„ — область целостности. В случае, когда число и не является простым, рассмотрим подмножество Л = ([х]:х — взаимно простое с и). Легко показать, что это множество образует группу относительно умножения. Произведение двух целых чисел, взаимно простых с и, является числом, взаимно простым с и. Единица, 1, есть число, взаимно простое с и; и если число Ь вЂ” взаимно простое с и, то сравнение Ьх = — 1 (гаог1 и) имеет единственное решение, поэтому для элемента [6] существует обратный элемент. Однако, относительно сложения множество Л не образует даже полугруппу, поскольку сумма двух чисел, взаимно простых с и, не обязательно является числом, взаимно простым с и.
ОПРЕДЕЛЕНИЕ 20.4. Пусть Л и Л' — кольца и пусть 7': Л вЂ” Л' — функция из Л в Л'. Функция )' называется гомоморфизмом колец тогда и только тогда, когда У[а+ 6) = У(а) + Г(Ь), Г[а Ь) = ) (а) Г(Ь) для всех а,Ь Е Л. Сложение и умножение в соответствующих кольцах одинаково определены. Если гомоморфизм колец Г:  — Л' — инъекция, то его называют мономорфизмом. Если гомоморфизм колец Г: Л вЂ” Л' — сюръекция, то его называют зицморфизмом.
Гомоморфизм колец У; Л вЂ” Л' называют изоморфизмом, если функция Г: Л вЂ” Л' — биекция. Обычно при описании гомоморфизма из кольца Л с единицей в кольцо Л' с единицей требуется, чтобы мультипликативная единица кольца Л отображалась на мультипликативную единицу кольца Л'. Например, рассмотрим кольцо целых чисел г, и кольцо г = ([0], [Ц, [2), (3], [4], (5], [6]) классов вычетов по модулю 7. Предположим, что функция У: г, — Ут определена соотношением 1(а) = [а]; другими словами, 1(а) — класс эквивалентности целых чисел, сравнимых с а по модулю 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
