Файл: Учебное пособие ульяновск 2018 msc2010 05 Combinatorics ббк 22. 176 Удк 519. 1 В313 Рецензенты.pdf

101
вытекает рекурсия, вполне определяющая значения двоич- ного веса ν (n), n ≥ 0
:
X
n ≥ 0
z
ν (n)
· t n
= (1 + zt) ·
X
m ≥ 0
z
ν (m)
· t
2m
=
=
X
m ≥ 0
z
ν (m)
· t
2m
+
X
m ≥ 0
z
ν (m)+1
· t
2m+1
;
ν (2m + 1) = ν (m) + 1 ,
ν (2m) = ν (m) ,
ν (0) = 0 .
7.15. Замечание. Предыдущие соотношения позволяют пе- реразложить гильбертову производящую функцию последо- вательности ν (n), n ≥ 0
:
H
ν
(t) =
X
n ≥ 0
ν (n) · t n
=
=
X
k ≥ 0
ν (2k) · t
2k
+
X
k ≥ 0
ν (2k + 1) · t
2k+1
=
=
X
k ≥ 0
ν (k) · t
2k
+
X
k ≥ 0
ν (k) + 1
· t
2k+1
=
= H
ν
(t
2
) +
X
k ≥ 0
ν (k) · t
2k+1
+
X
k ≥ 0
t
2k+1
=
= H
ν
(t
2
) + t·H
ν
(t
2
) +
t
1 − t
2
= (1 + t)·H
ν
(t
2
) +
t
1 − t
2
;
Умножим это равенство на (1 − t) и получим:
(1 − t) · H
ν
(t) =
t
1 + t
+ (1 − t
2
) · H
ν
(t
2
) =
=
t
1 + t
+
t
2 1 + t
2
+ (1 − t
4
) · H
ν
(t
4
) =
=
t
1 + t
+
t
2 1 + t
2
+
t
4 1 + t
4
+ · · · =
X
d ≥ 0
t
2
d
1 + t
2
d

102
Производящая функция H
ν
(t) аналитически выражается через N (t, z) (см. определение 7.12, стр. 96):
H
ν
(t) =
X
n ≥ 0
∂
∂z z
ν (n)
z = 1
· t n
=
∂
∂z
N (t, z)
z = 1
;
H
ν
(t) =

N (t, z) ·
∂
∂z ln N (t, z)

z = 1
=
= N (t, 1)·
∂
∂z ln N (t, z)

z=1
= N (t, 1)·
∂
∂z ln
Y
k ≥ 0

1+zt
2
k
z=1
=
= N (t, 1) ·
X
k ≥ 0
∂
∂z ln

1+zt
2
k
z=1
=
1 1 − t
·
X
k ≥ 0
t
2
k
1 + t
2
k
Из этого уже известного равенства вытекает, что
H
ν
(t) =
1 1 − t
·
X
s ≥ 0
(−1)
s
· T
1
t s+1
.
Утверждения этой главы можно распространить с двоич- ного случая при хороших формулировках. Например, таково обобщение Леммы 7.13 (здесь G
(2)
(t) = T
1
(t)):
7.16. Лемма. Пусть P = (p
1
, . . . , p k
) – набор разных простых чисел, I = (i
1
, . . . , i k
) – целочисленный мультииндекс. Если
⊥ означает взаимную простоту, а P
I
= p i
1 1
· · · · · p i
k k
, тогда
G
P
(t) :=
X
I ≥ 0
t
P
I
=
X
n ⊥ P
µ(n) ·
t n
1 − t n

103 8. АЛГЕБРАИЧЕСКАЯ КОМБИНАТОРИКА
К алгебраической комбинаторике можно отнести любые ал- гебраические подсч¨
еты. Например, – вычисления в группах,
кольцах, алгебрах и модулях; изучение действий групп на множествах и алгебраических структурах; поиск характерис- тик линейных операторов. Из необъятного множества задач здесь будет упомянуто малое. В этой главе основное поле k является подполем комплексных чисел C.
Начн¨
ем с алгебраического обобщения комбинаторной лем- мы Пойа. Е¨
е исходная формулировка и применения сообщены в книгах ([34, гл. 15, с. 209-231], [18, Пойа, с. 36-138; де Бр¨ейн,
с. 229-255]).
8.1. Определение. Пусть A – k-пространство и на него ди- агонализируемо действует коммутативная группа H:
ω
A
: H → Aut k
(A) ,
т.е., A имеет базис из собственных векторов a действия H:
ω
A
(h)(a) = h(a) = χ(h) · a ,
∀ h ∈ H .
Тогда функциональные множители χ принадлежат группе характеров X(H) := Hom (H, k
∗
) исходной группы H. По- рождая базисными векторами A одного характера χ подпро- странства A
χ
= {a ∈ A | h(a) = χ(h) · a , ∀ h ∈ H}, получим весовое разложение A:
A ∼
= ⊕
χ ∈ X(H)
A
χ
Если пространство A является k-алгеброй, мы считаем, что действие H сохраняет умножение:
ω
A
: H → Aut k−alg
(A) .

104
Весовое разложение является X(H)-градуировкой A, по- скольку для всех однородных a, b ∈ A и h ∈ H имеем:
h(a·b) = h(a)·h(b) = χ
a
(h)·a · χ
b
(h)·b = (χ
a
· χ
b
)(h)·a·b ,
A
χ
a
· A
χ
b
⊆ A
χ
a
· χ
b
Привед¨
енная конструкция отчасти обратима: если A граду- ирована коммутативной группой ∆, тогда группа характеров
X(∆) диагонализируемо действует на A:
φ (a
δ
) = φ (δ) · a
δ
,
φ ∈ X(∆) , a
δ
∈ A
δ
, A = ⊕
δ ∈ ∆
A
δ
При наличии умножения в A, действие X(∆) сохраняет его:
φ (a
δ
· a
δ
0
) = φ (a
δ · δ
0
) = φ (δ · δ
0
) · a
δ · δ
0
=
= φ (δ) · φ (δ
0
) · a
δ
· a
δ
0
= φ (a
δ
) · φ (a
δ
0
) .
8.2. Замечание. Этим способом можно описать все абелевы групповые градуировки объекта A. Необходимо найти мак- симальные абелевы подгруппы H ≤ Aut(A), действующие диагонализируемо на A, и тогда все градуировки на A фак- торизуются с X(H).
Итак, по условию, действие H расщепляется на скалярные компоненты. При h ∈ H и χ ∈ X(H) имеем разложение:
ω
A
(h) |
Aχ
= χ(h) · id
Aχ
Поэтому представление ω
A
зада¨
ется мультипликатором:
Ω
A
= ⊕
χ ∈ X(H)
id
Aχ
· χ : H × A → A ,
который для конечномерной A или конечной H можно счи- тать элементом End (A) ⊗ k [X(H)], а в более общем случае –
некоторым символическим оператором.

105 8.3. Определение. Если dim A
χ
< ∞ при всех χ, то в по- полнении групповой алгебры k [[X(H)]] определ¨ен след Ω
A
,
называемый рядом Гильберта X(H)–градуированного A:
H
A
= tr (Ω
A
) =
X
χ ∈ X(H)
dim A
χ
· χ .
Ряд Гильберта определения 2.5 со стр. 13 возникает при k = C и H ∼
= S
1
∼
= { w ∈ C
|w| = 1 }. Тогда группа характеров X(H) ∼
= Z мультипликативно реализуется возве- дениями в целочисленную степень t n
: w → w n
Далее мы предполагаем конечномерность компонент всех рассматриваемых объектов: ∀ χ ∈ X(H)
dim A
χ
< ∞ .
Поскольку для X(H)–градуированных k–линейных объек- тов A и B имеются изоморфизмы:
Ω
A ⊕ B
∼
= Ω
A
⊕ Ω
B
,
Ω
A ⊗ B
∼
= Ω
A
⊗ Ω
B
,
мы получаем известные свойства рядов Гильберта:
H
A ⊕ B
= tr (Ω
A ⊕ B
) = tr (Ω
A
) + tr (Ω
B
) = H
A
+ H
B
,
H
A ⊗ B
= tr (Ω
A ⊗ B
) = tr (Ω
A
) · tr (Ω
B
) = H
A
· H
B
Теперь пусть другая, не обязательно абелева, но конеч- ная группа G действует на A, сохраняя X(H)–градуировку и, при наличии,– мультипликативную структуру. Это озна- чает перестановочность действия G и Ω
A
. Тогда определено линейное усреднение по G:
P = |G|
−1
·
X
g ∈ G
g : A → A
G
Его называют оператором Рейнольдса. Он идемпотентен и проектирует A на подпространство G–инвариантов A
G

106 8.4. Определение. Для оператора Φ ∈ End (A), сохраняю- щего весовое разложение A и поэтому перестановочного с Ω
A
,
определим формальный ряд
H
A
(Φ) := tr (Φ · Ω
A
) =
X
χ ∈ X(H)
tr (Φ |
Aχ
) · χ .
8.5. Лемма. В предыдущих обозначениях получаем:
H
A
= H
A
(id
A
) ;
H
A
G
= |G|
−1
·
X
g ∈ G
H
A
(g) .
Доказательство. Первое равенство следует из определений.
Второе вытекает из линейности следа:
H
A
G
= tr (Ω
A
G
) = tr (Ω
P (A)
) = tr (P · Ω
A
) =
= tr |G|
−1
·
X
g ∈ G
g · Ω
A
= |G|
−1
·
X
g ∈ G
tr (g · Ω
A
) =
= |G|
−1
·
X
g ∈ G
H
A
(g) .
Перейд¨
ем к формуле Бернсайда. Напомним е¨е начальный вид и взвешенное усиление Пойа (см. [34, гл. 15]).
Формула Бернсайда ([34, с. 212, Следствие 15.3(а)]) выра- жает количество орбит N
G
действия G на множестве M через циклические параметры действия элементов g:
N
G
= |G|
−1
·
X
g ∈ G
j
1
(g) ,
здесь j u
(g) – количество независимых циклов длины u образа элемента g ∈ G при гомоморфизме G → S
M
Пусть на взвешенном множестве M действует группа G,
сохраняя значение веса. Тогда любая G–орбита θ ⊆ M ле- жит в подмножестве элементов M одного веса. Вес орбиты

107
примем по этой принадлежности: ω (θ) := ω (m ∈ θ). Соглас- но результату Пойа, ([34, с. 211, теорема 15.3]) сумма весов орбит G–действия вычисляется по формуле:
X
ω (θ
i
) = |G|
−1
·
X
g ∈ G
X
m = g (m)
ω (m) .
Формула Бернсайда непосредственно следует из е¨е взве- шенного обобщения тривиализацией веса: ω (m) ≡ 1. Обоб- щ¨
енную же формулу Бернсайда легче доказывать в линеари- зированном градуированном виде.
8.6. Определение. Взвешенным абелевой группой ∆ мно- жеством M , как базисом, породим ∆–градуированное про- странство V =
k hM i k–линейных комбинаций m ∈ M . Тог- да действие G на M продолжается до е¨е представления в V .
Каждой G–орбите θ ⊆ M соответствует вектор
|θ|
−1
·
X
m ∈ θ
m = P (m
0
)
∀ m
0
∈ θ .
Такие вектора образуют базис подпространства G– инва- риантов V
G
, и поэтому мы имеем равенства:
X
ω (θ
i
) = H
V
G
,
X
m = g (m)
ω (m) = tr (g · Ω
V
) = H
V
(g) .
Тем самым, обобщ¨еннная формула Бернсайда непосредст- венно следует из леммы 8.5, а исходная формула Бернсайда получается из не¨
е св¨
ерткой с 1
X(∆)
∈ X(∆):
N
G
= hH
V
G
, 1
X(∆)
i = |G|
−1
·
X
g ∈ G
hH
V
(g) , 1
X(∆)
i =
= |G|
−1
·
X
g ∈ G
tr (g) ,

108
поскольку hΩ
V
, 1
X(∆)
i = id
V
, а правомерность св¨ертки обес- печена конечномерностью V , следующей из конечности M .
Перейд¨
ем к теореме перечисления Пойа. Сначала вспом- ним е¨е авторскую формулировку (см. [18, Пойа, с. 46-53; де
Бр¨
ейн, с. 229-231], [34, с. 213, Теорема 15.4], [12, с. 42]).
Пусть группа G действует на множестве D, а на множест- ве R задана весовая функция ω. Тогда G действует на R
D
–
множестве функций из D в R – по правилу:
(F · g)(d ) = F g (d )
,
∀ d ∈ D , ∀ g ∈ G , ∀ F ∈ R
D
Вес функции из D в R принимается равным произведению весов всех е¨
е значений:
W (F ) =
Y
d ∈ D
ω (d ) .
Пойа выразил C(X) – перечисляющий ряд для G–орбит на
R
D
через перечисляющий ряд c (X) для R и цикловой ин- декс действия G на D
Z(G; a
1
, . . . , a
|D|
) := |G|
−1
·
X
g ∈ G
|D|
Y
u = 1
a j
u
(g)
u формулой C(X) = Z(G; c (X)). Подстановку в цикловой ин- декс перечисляющего ряда Пойа описал в частном случае бинатурального взвешивания. Е¨е можно найти в указанных ранее книгах. Более общая ситуация идейно вытекает из кон- струкции Пойа, но требует дополнительных понятий, о кото- рых мы позаботлись заранее. Обобщение теоремы Пойа мы провед¨
ем и докажем в линейном случае.

109 8.7. Теорема. Пусть V =
k hR i – градуированное простран- ство. Если G действует на множестве D , то она действует на пространстве V
⊗ |D|
перестановкой компонент. Множество
R
D
является k–базисом V
⊗ |D|
. Формула Пойа выражает ряд
Гильберта G–инвариантов V
⊗ |D|
через H
V
и Z(G):
H
(V
⊗ |D|
)
G
= tr (Ω
(V
⊗ |D|
)
G
) =
= Z G ; tr (Ω
V
), tr (Ω
2
V
), . . . , tr (Ω
|D|
V
)
=: Z(G ; H
V
) .
8.8. Замечание. Оказывается, подобное равенство выпол- няется и до усреднения по G, для каждого элемента g ∈ G
в отдельности, что обеспечивает доказательство предыдущей теоремы 8.7 и теоремы Пойа, в частности.
8.9. Определение. Если G действует на множестве D , то элемент g ∈ G получает цикловой тип j u
(g), u ≥ 1
, где j u
(g)
– количество циклов длины u в разложении g на независимые циклы. Определим цикловой индекс элемента g правилом:
Z(g ; a
1
, . . . , a
|D|
) :=
|D|
Y
u = 1
a j
u
(g)
u
Цикловой индекс действия группы G получается усредне- нием цикловых индексов е¨
е элементов:
Z(G ; a
1
, . . . , a
|D|
) = |G|
−1
·
X
g ∈ G
Z(g ; a
1
, . . . , a
|D|
) .
8.10. Лемма. В предыдущих обозначениях есть равенства:
Z(g ; H
V
) := Z g ; tr (Ω
V
), . . . , tr (Ω
|D|
V
)
=
=
|D|
Y
u = 1
tr (Ω
u
V
)
j u
(g)
= tr (g · Ω
V
⊗ |D|
) = H
V
⊗ |D|
(g) .

110
Доказательство. Неочевидным в этой цепочке равенств яв- ляется лишь предпоследнее. А его достаточно установить для циклической перестановки c, поскольку обе части равенства мультипликативны по разложению g в произведение незави- симых циклов в силу тождества tr (ϕ ⊗ ψ) = tr (ϕ) · tr (ψ).
Если же c – цикл длины d, то он оставляет на месте базис- ные элементы V
⊗ d вида v ⊗ · · · ⊗ v, переставляя остальные,
не дающие вклад в след c · Ω
V
⊗ d
. Следовательно,
H
V
⊗ d
(c) = tr (c · Ω
V
⊗ d
) = tr (Ω
d
V
) = Z(c ; H
V
) ,
что завершает доказательство леммы 8.10 и теоремы 8.7.
8.11. Замечание. Если g переставляет базис тривиально градуированного V , мы получаем важное равенство, относя- щееся к следующей части главы:
Z(g ; 1 − t) =
Y
u ≥ 1
(1 − t u
)
j u
(g)
= det ( id
V
− g · t ) .
Для примера рассмотрим действие группы на градуиро- ванной алгебре. Начн¨ем со свободного ассоциативно–ком- мутативного случая.
Пусть Y
χ
– базис V
χ
, тогда есть изоморфизм алгебр:
k [ ∪
χ ∈ X(H)
Y
χ
] ∼
= ⊗
χ ∈ X(H)
k [ Y
χ
] .
Здесь правая часть, по определению, состоит из тензоров ограниченной степени. Значит, симметризованная тензорная степень подчиняется правилу:
S (⊕
χ ∈ X(H)
V
χ
) ∼
= ⊗
χ ∈ X(H)
S (V
χ
) .
Для набора Φ
χ
∈ End (V
χ
) также имеем изоморфизм:
S (⊕
χ ∈ X(H)
Φ
χ
) ∼
= ⊗
χ ∈ X(H)
S (Φ
χ
).

111
Поэтому для Φ = ⊕ Φ
χ
, коммутирующего с Ω
V
, симметри- зация S (Φ) коммутирует с Ω
S(V )
8.12. Лемма. Пусть V ∼
= ⊕
χ ∈ X(H)
V
χ
– градуированное про- странство с конечномерными компонентами; Φ ∼
= ⊕ Φ
χ
, где
Φ
χ
∈ End (V
χ
). Тогда выполняется равенство:
H
S (V )
S (Φ)
= det ( id
V
− Φ · Ω
V
)

−1
Доказательство. Для φ ∈ End (W ), при dim (W ) < ∞ изве- стна интересная формула:
det ( id
W
− φ )

−1
= tr S (φ)
.
Она следует из инвариантности е¨е вида при расширении поля k и, по индукции, из одномерного случая:
det (1 − λ)

−1
= (1 − λ)
−1
=
X
k ≥ 0
λ
k
=
= tr (⊕
k ≥ 0
λ
k
) = tr S (λ)
,
и мультипликативности при расширении пространства W .
Поэтому при dim V
χ
< ∞ ∀ χ ∈ X(H) есть равенства:
H
S (V )
S (Φ)
= tr (S (Φ) · Ω
S(V )
) = tr S (Φ) · S (Ω
V
)
=
= tr S (Φ · Ω
V
)
= tr ⊗
χ ∈ X(H)
S (Φ
χ
· Ω
V
χ
)
=
=
Y
χ ∈ X(H)
tr S (Φ
χ
· Ω
V
χ
)
=
Y
χ ∈ X(H)
det (id
V
χ
− Φ
χ
· Ω
V
χ
)

−1
=
= det ( id
V
− Φ · Ω
V
)

−1 8.13. Замечание. Для φ ∈ End (W ), при dim (W ) < ∞
совершенно аналогично доказывается полезная формула:
ln det ( id
W
− φ )
= −
X
m > 0
tr (φ
m
)/m .

112 8.14. Следствие (Формула Ф.Э. Молина). В предыдущих предположениях о G и V имеются равенства:
H
(S (V ))
G
= tr (P · Ω
S (V )
) = |G|
−1
·
X
g ∈ G
H
S (V )
S (g)
=
= |G|
−1
·
X
g ∈ G
det ( id
V
− g · Ω
V
)

−1
При тривиальном действии группы G получаем:
H
S (V )
= H
(S (V ))
e
= tr (Ω
S (V )
) = det ( id
V
− Ω
V
)

−1
Аналогично, для любого n ≥ 1 выводятся формулы:
tr (Ω
n
S (V )
) = tr S (Ω
n
V
)
= det ( id
V
− Ω
n
V
)

−1
;
ln tr (Ω
n
S (V )
)
= − ln det ( id
V
− Ω
n
V
)
=
X
m ≥ 1
tr (Ω
nm
V
)
m
Из второй формулы обращением М¨ебиуса и экспонирова- нием можно получить равенство:
exp (H
V
) = exp tr (Ω
V
)
=
Y
n ≥ 1
tr (Ω
n
S (V )
)

µ(n)/n
Эти формулы проясняются в случае V = ⊕
m ≥ 1
V
m
. Тогда
H
V
= H
V
(t) = tr (Ω
V
) =
X
m ≥ 1
dim (V
m
) · t m
,
H
S (V )
= H
S (V )
(t) = det ( id
V
− Ω
V
)

−1
=
=

det ⊕
m ≥ 1
id
V
m
· (1 − t m
)


−1
=
Y
m ≥ 1
(1 − t m
)
− dim (V
m
)
,
exp H
V
(t)
=
Y
n ≥ 1
H
S (V )
(t n
)

µ(n)/n

113
Предыдущее равенство известно нам в частном случае:
e t
=
Y
n ≥ 1
(1 − t n
)
−µ(n)/n
Перейд¨
ем к свободному ассоциативному случаю. Обозначим знаком T функтор тензорной степени T (V ) := ⊕
m ≥ 0
V
⊗ m
Он совместим с X(H)–градуировкой на пространстве V . Тог- да для Φ ∈ End (V ), коммутирующего с Ω
V
, T (Φ) будет ком- мутировать с Ω
T (V )
. И мы получаем равенства:
H
T (V )
T (Φ)
= tr (T (Φ) · Ω
T (V )
) = tr T (Φ · Ω
V
)
=
= tr
M
m ≥ 0
(Φ · Ω
V
)
⊗ m
=
X
m ≥ 0
tr (Φ · Ω
V
)

m
= 1 − H
V
(Φ)

−1
В частности, получаем известную алгебраическую формулу:
H
T (V )
= (1 − H
V
)
−1
,
которая обобщается на “свободные инварианты”.
8.15. Следствие (Формула Дикса–Форманека). В предыду- щих предположениях, если действие группы G сохраняет гра- дуировку V , то выполняются равенства:
H
(T (V ))
G
= |G|
−1
·
X
g ∈ G
H
T (V )
T (g)
= |G|
−1
·
X
g ∈ G
1 − H
V
(g)

−1
Изложенное ранее приводит к свободному лиевому случаю.
Пусть L (V ) – свободная алгебра Ли над градуированным пространством V . Известно, что тогда универсальная об¨ер- тывающая алгебра U (L (V )) изоморфна свободной ассоциа- тивной алгебре T (V ). Если оператор Φ действует на V с сохранением X(H)–градуировки, тогда он продолжается до