Cтраница 4
Существует класс задач перечисления, которые можно решить с использованием степенной группы в качестве группы конфигураций. Рассмотрим степенную группу ВА, действующую на RD. Число конфигураций ( классов эквивалентности функций, определяемых группой ВА) можно найти из теоремы Пойа ( см. Харари и Палмер [8]); это было сделано де Брейном [1] и [2] в иной формулировке. Формулу (15.54) можно легко приспособить для перечисления функций в соответствии с их весами. [46]
Таким образом, элементы 0 и 1 из множества Y используются для указания соответственно на существование или отсутствие ребра в графе. Рассмотрим степенную группу ВА, у которой А 5 ( Р2) и В Szt Ясно, что графы, представимые двумя функциями, эквивалентны относительно дополнительности тогда и только тогда, когда эти две функции принадлежат одной и той же орбите рассматриваемой степенной группы ВА. Поэтому если подстановка ( а; ( 0) ( 1)) из этой группы преобразует функцию / в функцию g, то / и g представляют изоморфные графы. А если / преобразуется в g подстановкой ( а; ( О, 1)), то две функции представляют взаимно дополнительные графы. Следовательно, число ар / - вершинных графов, подсчитываемых с точностью до их взаимной дополнительности, равно числу орбит указанной выше степенной группы. [47]
Степенная группа 2) ( обозначается ВА) действует на множестве Vх всех функций, отображающих X в Y. Будем всегда предполагать, что степенная группа действует на множестве, состоящем более чем из одной функции. [48]
Если S - подкольцо R, то группу G называют S - onpedeленной, если существует мальцевская база группы G, в которой умножение и возведение в степень задаются многочленами с коэффициентами из S. Пусть G и Я-произвольные - степенные группы. [49]
Группа А индуцирует группу А, множество объектов которой состоит из всех расширений орграфа D0, являющихся ациклическими орграфами и имеющих ровно по п вершин с нулевыми полустепенями захода. Это представление группы А может быть сделано явным, если использовать ограниченную степенную группу; но так как подобный подход мы применяли довольно часто, то приведенного указания вполне достаточно. Такое обилие переменных может показаться излишним, но их наличие сделает наши формулы менее беспорядочными. [50]