Лемма - бернсайд
Cтраница 2
Как и в случае графа Кр, формула для о ( G) может быть получена путем применения леммы Бернсайда. Получающееся при этом выражение можно упростить, используя специальный цикловой индекс, зависящий от переменных двух типов. [16]
Задача перечисления указанных орграфов представляет собой новый интересный тип задачи, которая, по-видимому, требует для своего решения подходящего обобщения леммы Бернсайда. [17]
Ограничивая эту группу на множество F функций /, представляющих турниры, а именно тех функций /, для которых / ( i, j) 7 t / ( /, 0 можем применить вариант (2.3.9) леммы Бернсайда. Тогда Т ( р) может быть выражено через число функций иэ множества F, которые неподвижны относительно подстановок, принадлежащих той же самой степенной группе. [18]
Ограничивая эту группу на множество F функций /, представляющих турниры, а именно тех функций /, для которых / ( i, j) Ф / ( j, i), можем применить вариант (2.3.9) леммы Бернсайда. Тогда Т ( р) может быть выражено через число функций из множества F, которые неподвижны относительно подстановок, принадлежащих той же самой степенной группе. [19]
Первое расширение леммы Бернсайда ( теоремы 4.2 ( а), 4.2 ( 6)) неявно содержалось в работе [5], второе ( теоремы 4.3 ( а), 4.3 ( 6)), по существу принадлежащее Редфилду [14], появилось в работе [9] как обобщение одной леммы бернсайдовского типа, использованной Виллиамсоном при доказательстве некоторой теоремы, аналогичной теореме Пона. У Виллиамсона функция t была мультипликативной функцией на группе. Совершенно иное применение будет дано в разд. [20]
Для подсчета числа непомеченных графов задачу переформулиро-вывают так, чтобы ответ можно было получить, найдя число орбит некоторой подходящей группы подстановок. Тогда можно воспользоваться леммой Бернсайда и выразить число орбит на языке числа объектов, неподвижных относительно подстановок из рассматриваемой группы. Каждой группе подстановок отвечает свой многочлен, называемый цикловым индексом. Это понятие может быть прослежено еще у Фробениуса как частный случай соответствующей формулировки в терминах групповых характеров. Редфилд [1], открывший цикловые индексы независимо, изобрел искусные схемы ( гл. [21]
Для подсчета числа непомеченных графов задачу переформулиро-вывают так, чтобы ответ можно было получить, найдя число орбит некоторой подходящей группы подстановок. Тогда можно воспользоваться леммой Бернсайда и выразить число орбит на языке числа объектов, неподвижных относительно подстановок из рассматриваемой группы. Каждой группе подстановок отвечает свой многочлен, называемый цикловым индексом. Это понятие может быть прослежено еще у Фробениуса как частный случай соответствующей формулировки в терминах групповых характеров. Редфилд [.1], открывший цикловые индексы независимо, изобрел искусные схемы ( гл. [22]
Такое сведение основывается на лемме Бернсайда ( известной еще Фробениусу), утверждающей, что число орбит ( транзитивных множеств) произвольной группы подстановок равно среднему арифметическому числа неподвижных точек всех элементов группы. [23]
 |
Суперпозиции двух циклов. [24] |
Этот результат можно обосновать, построив сначала группу подстановок, орбиты которой представляют собой классы матриц, подлежащие перечислению. Формула (7.1.7) следует затем из леммы Бернсайда ( см. (2.3.3)), которую надо применить к построенной группе. [25]
В этом разделе мы с более формальных позиций рассмотрим специальный случай теоремы Пойа, проиллюстрированный на примере из разд. Это доказательство включает результат, известный как лемма Бернсайда, который сам по себе представляет интересную технику подсчета. Хотя теорему Пойа легче использовать механически, лемма Бернсайда более ясно раскрывает математическую суть, на которой основана идея подсчета классов эквивалентности. [26]
 |
Граф и его группа. [27] |
Напротив, классическая теорема перечисления, принадлежащая Пойа, может быть рассмотрена как средство для перечисления функций, и поэтому ее много легче применять к большинству задач теории графов. В своей наибольшей общности теорема Пойа включает лемму Бернсайда и часто позволяет выражать полную производящую функцию для класса графов в терминах подходящего циклового индекса и многочлена, называемого перечисляющим рядом для фигур. Таким образом, именно общность, универсальность и легкость при его использовании делают метод Пойа наиболее мощным инструментом в перечислительном анализе. [28]
Группой вращений куба называется подгруппа группы всех его симметрии, состоящая из всевозможных вращений куба вокруг центра или осей симметрии. Доказать, что она транзитивна и, пользуясь леммой Бернсайда, определить ее порядок. [29]
В этом разделе мы с более формальных позиций рассмотрим специальный случай теоремы Пойа, проиллюстрированный на примере из разд. Это доказательство включает результат, известный как лемма Бернсайда, который сам по себе представляет интересную технику подсчета. Хотя теорему Пойа легче использовать механически, лемма Бернсайда более ясно раскрывает математическую суть, на которой основана идея подсчета классов эквивалентности. [30]
Страницы: 1 2 3