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

75
Чтобы прояснить смысл расстановок скобок, мы зададим алгебраическую структуру на множестве конечных последо- вательностей со скобками. Мы обнаружим, что помимо не- линейных графических особенностей, правильным расстанов- кам скобок свойственны и числовые показатели. Так возника- ет комбинаторная задача подсч¨ета различных последователь- ностей с одинаковыми показателями и другими числовыми характеристиками.
6.1. Определение. Пусть X = {x
1
, . . . , x n
} – непустое ко- нечное множество. Оно порождает множество неассоциатив- ных мономов от X – конечных последовательностей символов x
i оснащ¨
енных скобками:
W (X) =
[
m≥1
W
m
(X) , где
W
1
(X) = X
и
W
k
(X) =
k−1
[
s=1
W
s
(X) × W
k−s
(X)
, при k ≥ 2 .
Множество W (X) называется свободным группоидом с не- ассоциативным умножением “×”. Из этого определения выте- кает рекуррентный критерий равенства мономов.
6.2. Лемма. w
1
= w
2
∈ W (X), если и только если выполне- ны два условия:
1. w
1
и w
2
∈ W
k
(X) для их общего k ≥ 1;
2. при k = 1 равенство w
1
= w
2
выполняется в X, а при k ≥ 2 есть однозначное разложение w i
= (u i
×v i
), где u
1
= u
2
и v
1
= v
2
в W
< k
(X).
6.3. Определение. Нижний индекс W
k
(X) указывает дли- ну элементов W (X). При w ∈ W
k
(X) обозначим |w| := k.

76
Поскольку
(u×v)
= |u| + |v|, длина определяет вес (нату- ральную градуировку) на W (X):
W
s
(X) × W
t
(X)
⊂ W
s+t
(X) .
6.4. Определение. Среди рассмотренных свободных груп- поидов есть простейший B = W {x}

– группоид скобоч- ных шаблонов. Любой W (X) отображается на B стиранием индексов x i
и с сохранением произведения:
β : W (X) B, где β(x i
) = x, β (u × v)
= β(u) × β(v).
Если w ∈ W (X), то β(w) ∈ B называется скобочной струк- турой неассоциативного монома w. Определим множество мономов одной скобочной структуры b ∈ B:
W
(b)
(X) = β
−1
(b) = {w ∈ W (X) | β(w) = b} .
Тогда разбиение W (X) =
S
b ∈ B
W
(b)
(X) является неассо- циативной мультипликативной градуировкой W (X):
W
(b)
(X) × W
(b
0
)
(X)
= W (
( b × b
0
)
)(X) .
Скобочная структура помнит длину:
β(w)
= |w|, поэтому
W
s
(X) =
[
|b| = s
W
(b)
s
(X) .
Здесь W
(b)
s
(X) = W
(b)
(X), при |b| = s, но W
(b)
s
(X) = ∅, иначе.
Поскольку скобочная структура зада¨ет расстановку ско- бок, вид неассоциативного монома фиксированной структу- ры определяется только порядком вхождения в моном симво- лов x i
. Поэтому нетрудо найти количество неассоциативных мономов структуры b ∈ B:
] B
(b)
= ] W
(b)
{x}
= 1 ,
] W
(b)
(X)
= ](X)
|b|

77 6.5. Следствие. Cкобочные структуры в W (X) связаны с числами Каталана:
] (B
s
) = C
s−1
,
] W
s
(X)
= C
s−1
· ] (X)
s
Надо помнить, что вес скобочного шаблона равен его дли- не, а индекс числа Каталана измеряет количество умножений в шаблоне, которое на 1 меньше. Точные формулы будут вы- ведены позднее. Мы увидим, что они отражают расщепление,
называемое гнездовым.
6.6. Определение. Для X 6= ∅ обозначим множество
1
I =
1
I(X) := W
≥ 2
(X) =
[
s ≥ 2
W
s
(X) .
Тогда
1
I(X) выдерживает умножение на элементы W (X) :
1
I × W (X)
, W (X) ×
1
I
⊂
1
I .
Говорят, что
1
I – идеал группоида W (X). В этом смысле сам W (X) = W
≥ 1
(X) является своим идеалом – обозначим его следующим образом
0
I =
0
I(X) := W (X).
Для непустого M ⊂ W (X) обозначим h M i – идеальное замыкание M в W (X), то есть, – наименьший по включению идеал W (X), содержащий M .
Теперь мы можем определить следующие идеалы (компо- ненты последующих объединений могут пересекаться):
2
I =
2
I(X) :=
(
1
I ×
1
I )
,
s
I =
s
I(X) :=
s − 1
[
t = 1
(
t
I ×
s−t
I )
, при s > 2 .

78
Мономы из s
I являются неассоциативными произведения- ми некоторого набора элементов W (X), не менее s из которых лежат в W
≥ 2
(X). Устройство s
I мы проясним позднее.
Эти идеалы вложены друг в друга,– то есть,– определяют убывающую фильтрацию на W (X):
W (X) =
0
I ⊃
1
I ⊃ · · · ⊃
s
I ⊃
s+1
I ⊃ . . . ,
\
s ≥ 0
s
I = ∅ .
Теперь определим последовательные дополнения предыду- щего ряда множеств:
s
G =
s
G (X) :=
s
I \
s+1
I , s ≥ 0 .
Возникают непересекающиеся (дизъюнктные) объединения:
s
I =
[
t ≥ s t
G ,
в частности,
W (X) =
[
t ≥ 0
t
G .
6.7. Замечание. Множество s
G состоит из неассоциативных мономов, ровно s сомножителей которых лежат в W
≥ 2
(X),
а остальные – в X. И это вполне определяет скобочный шаб- лон: w ∈
s
G (X) если и только если β(w) ∈
s
G {x}
. Так,
мономы шаблона ((((x × (x × x)) × x) × ((x × x) × x)) × x) при- надлежат множеству
2
G – элементы отсюда содержат ровно два вхождения вида (x i
× x j
).
6.8. Определение. Подмономы w ∈ W (X) вида (x i
× x j
)
назов¨
ем гн¨
ездами в w. Количество гн¨
езд определяет принад- лежность монома s
G и s
I: w ∈
s
G, если w имеет s гн¨
езд, и наоборот. Кроме того, |w| ≥ 2s , и в итоге получаем:
s
G =
[
m ≥ 2s
[
b ∈ B
s
G
(b)
m
,
где s
G
(b)
m
=
s
G
\
W
(b)
m
(X) .

79
Безгнездовые мономы имеют вид x i
, – они принадлежат множеству X =
0
G =
0
G
(x)
1 6.9. Замечание. Разбиение {
s
G | s ≥ 0} зада¨ет на множест- ве W (X) частичную градуировку в следующем смысле:
(
s
G ×

t
G ) ⊂
s+t
G при (s, t) 6= (0, 0), но (
0
G ×
0
G ) ⊂
1
G .
Благодаря этому можно вычислить производящую функ- цию группоида W (X), учитывающую гнездовую структуру мономов и их длину (тут ](X) = n):
F (y, z) = ] G(X)
(y, z) :=
X
m ≥ 1
X
s ≥ 0
] (
s
G
m
) · y m
· z s
=
= ny + n
2
y
2
z + 2n
3
y
3
z + · · · .
6.10. Лемма. Функция F (y, z) – алгебраична:
F (y, z) =
1 2
·
1 − (1−2ny)·

1 −
4n
2
y
2
(1−2ny)
2
· z

1/2
!
Доказательство. Функциональная связь для F = F (y, z),
с уч¨
етом вышеуказанного сбоя градуировки s
G , следует из равенств взвешенных множеств и производящих функций:
X ∪ W (X) × W (X)
= W (X) ,
ny + F (y, z)
2
= F (y, z) − n
2
y
2
z + n
2
y
2
Откуда получается квадратичное уравнение:
F
2
− F + (n
2
y
2
z − n
2
y
2
+ ny) = 0 .
Преобразуем дискриминант этого выражения:
D = 1 − 4n
2
y
2
z + 4n
2
y
2
− 4ny = (1 − 2ny)
2
− 4n
2
y
2
z .

80
Для F имеются две возможности:
F
±
=
1 2
1 ± (1 − 2ny) ·

1 −
4n
2
y
2
(1 − 2ny)
2
· z

1/2
!
Но F (0, z) = 0, поэтому F = F
−
, что доказывает Лемму 2.2.
6.11. Замечание. При n = 1, z = 1 получим D = 1 − 4y и
F (y, 1) =
X
m ≥ 1
](B
m
)y m
=

1 −
p
1−4y
.
2 =
X
m ≥ 1
C
m−1
· y m
,
где C
m−1
– числа Каталана, считающие скобочные шаблоны длины m. Получаем для них известную формулу:
C
m−1
= −
1 2
·
1/2
m

· (−4)
m
=
= −
1 2
·
1
m!
·
1 2
·

1 2
− 1

· . . . ·

1 2
− (m−1)


· (−4)
m
=
=
1 2
m+1
· m!
·

2(m−1)−1
· 2(m−2)−1· . . . · 2−1

· 4
m
=
=
1
m!
· (2m − 3) · (2m − 5) · . . . · 1
· 2
m−1
=
=
1
m!
·
(2m − 2)! · 2
m−1
(2m − 2) · (2m − 4) · . . . · 2
=
=
(2m − 2)!
m! · (m − 1)!
=
1 2 · (2m − 1)
·
2m m

И так же можно найти мощность компонент s
G
m
(X).
6.12. Теорема. При m ≥ 2, s ≥ 1:
] (
s
G
m
) = C
s−1
·
m − 2 2s − 2

· 2
m−2s
· ] (X)

m

81
Доказательство. Обозначим n = ] (X) и вычислим ради- кальную часть алгебраического выражения F (y, z):

1 −
4n
2
y
2
(1 − 2ny)
2
· z

1/2
=
X
s ≥ 0
1/2
s

·
(−4)
s
(n
2
y
2
z)
s
(1 − 2ny)
2s
=
= 1 − 2 ·
X
s ≥ 1
C
s−1
·
(n
2
y
2
z)
s
(1 − 2ny)
2s
Далее, из Леммы 6.10 получаем выражение для F (y, z):
F (y, z) =
X
m ≥ 1
X
s ≥ 0
] (
s
G
m
) · y m
· z s
=
=
1 2
·

1 − (1 − 2ny) ·

1 − 2 ·
X
s ≥ 1
C
s−1
·
(n
2
y
2
z)
s
(1 − 2ny)
2s

=
= ny +
X
s ≥ 1
C
s−1
·
(n
2
y
2
z)
s
(1 − 2ny)
2s−1
=
= ny +
X
s ≥ 1
C
s−1
· (n
2
y
2
z)
s
·
X
u ≥ 0
−2s + 1
u

· (−2ny)
u
=
= ny +
X
s ≥ 1
C
s−1
· (n
2
y
2
z)
s
·
X
u ≥ 0
2s + u − 2
u

· (2ny)
u
=
= ny +
X
s ≥ 1
X
u ≥ 0
C
s−1
·
2s + u − 2 2s − 2

· 2
u
· (ny)
2s+u
· z s
=
Сделаем замену 2s + u = m ≥ 2s и продолжим равенство:
= ny +
X
s ≥ 1
X
m ≥ 2s
C
s−1
·
m − 2 2s − 2

· 2
m−2s
· n m
· y m
· z s

82
Следовательно, получаем искомые тождества:
] (
s
G
m
) = C
s−1
·
m − 2 2s − 2

· 2
m−2s
· n m
, при s ≥ 1 , m ≥ 2s ;
] (
0
G
1
) = n . Остальные ] (
s
G
m
) = 0 .
В частности, доказаны равенства:
]
s
G
2s
{x}
= C
s−1
,
]
1
G
m
{x}
= 2
m−2
Они имеют содержательное наполнение. Действительно, обо- значим для удобства x
2
:= (x × x). Тогда s
G
2s
{x}
=
[
k ≥ 0
k
G
s
x
2
,
1
G
m
{x}
=
n x× · · · × x×x
2
. . ., x× · · · × x
2
×x
. . .,
. . . ,
. . . x
2
×x
× · · · ×x
o
Последнее равенство подсказывает описание одногнездо- вых шаблонов.
6.13. Определение. Для b ∈ B обозначим L(b) := (x×b)
и R(b) := (b×x). Операции L и R – преобразования множе- ства шаблонов B, и поэтому их композиция ассоциативна.
Определим отображение µ из множества ассоциативных мо- номов от символов L и R, которое обозначим {L, R}
∗
, в B:
µ : {L, R}
∗
→ B,
µ(∅) = x
2
,
µ w(L, R )
= w(L, R) x
2
.
Оно продолжает отображение µ(L) = L x
2
, µ(R) = R x
2
.
Ясно, что
µ(w)
= |w| + 2 , и можно считать, что deg µ = 2 .
6.14. Лемма. µ – биекция {L, R}
∗
на
1
G {x}
.

83
Доказательство: Поскольку µ однороден степени 2 относи- тельно длины мономов, достаточно убедиться в биективности однородной части отображения
µ : {L, R}
s
→
1
G
s+2
{x}
.
Рассуждение провед¨
ем индукцией по s. Начальные случаи s = 0, 1 – очевидны. Сперва докажем инъективность µ.
Заметим, если µ w
1
(L, R )
= µ w
2
(L, R )
, то |w
1
| = |w
2
| .
Пусть для неких w
1 6= w
2
∈ {L, R}
s выполнено равенство
µ(w
1
) = µ(w
2
). Здесь s можно считать наименьшим из воз- можных – ясно, что s ≥ 2 .
Воспользуемся критерием равенства ассоциативных моно- мов положительной длины: в моноиде X
∗
= {x
1
, . . . }
∗
равен- ство w
1
= w
2
выполнено, если и только если |w
1
| = |w
2
| и w
i
= x j
i
· v i
, где j
1
= j
2
, v
1
= v
2
В нашей ситуации w i
= U
i
· v i
(L, R), где U
i
∈ {L, R}.
По предположению, ассоциативные пары (U
1
, v
1
) и (U
2
, v
2
)
– различны, но равны неассоциативные мономы в B:
µ(w
1
) = U
1
· v
1
(L, R )

x
2
= U
2
· v
2
(L, R )

x
2
= µ(w
2
) ;
U
1
v
1
(L, R) x
2
= U
2
v
2
(L, R) x
2
.
По критерию равенства в B, получаем: U
1
= U
2
и v
1
(L, R) x
2
= µ(v
1
) = µ(v
2
) = v
2
(L, R) x
2
.
При этом ассоциативные мономы v
1
(L, R) и v
2
(L, R) ока- зываются разными, но имеют длину s − 1 < s. Полученное противоречие доказывает инъективность отображения µ.
Теперь докажем сюръективность µ. Пусть m ∈
1
G {x}
.
Но, по определению:
1
G {x}
=
1
I {x}
\
2
I {x}
=

84
=
1
I {x}
\
1
I {x}
×
1
I {x}
= B
≥ 2
\ hB
≥ 2
× B
≥ 2
i .
Таким образом, m ∈ B
≥ 2
и m = u × v. Но оба сомножителя u и v не могут принадлежать B
≥ 2
, поскольку тогда m ∈ hB
≥ 2
× B
≥ 2
i =
2
I {x}

*
1
G {x}
.
Поэтому один из них лежит в B
1
= {x}. Для определ¨ен- ности ограничимся случаем u = x. Если |v| = 1, тогда v = x и m = x
2
= µ(∅) – утверждение доказано. Если же |v| ≥ 2 ,
тогда v ∈ B
≥ 2
, но надо учесть:
v 6∈ hB
≥ 2
× B
≥ 2
i =
1
I {x}
×
1
I {x}
=
2
I {x}
,
поскольку иначе m = x × v ∈
2
I {x}

*
1
G {x}
. Поэтому v ∈
1
I {x}
\
2
I {x}
=
1
G {x}
, |v| = |m| − 1 .
По индукционной гипотезе, для некого w(L, R) ∈ {L, R}
∗
есть равенство v = µ(w). И тогда m = x × v = L(v) = L µ(w)
= µ(L · w) .
Тем самым, индукция завершена и Лемма 6.14 доказана.
Из Теоремы 6.12 следуют частично св¨
ернутые формулы:
6.15. Лемма. Пусть s ≥ 1, m ≥ 2, тогда
]
s
G(X)
(y) :=
X
m ≥ 1
]
s
G
m
(X)
· y m
=
C
s−1
· n
2s
· y
2s
(1 − 2ny)
2s−1
;
] G
m
(X)
(z) :=
X
s ≥ 1
]
s
G
m
(X)
· z s
=
= ] (X)

m
·
X
s ≥ 1
C
s−1
·
m − 2 2s − 2

· 2
m−2s
· z s
;

85
C
m−1
= ] (B
m
) =
X
s ≥ 1
]
s
G
m
{x}
=
=
X
s ≥ 1
C
s−1
·
m − 2 2s − 2

· 2
m−2s
Доказательство. При выводе утверждения Теоремы 6.12
было получено выражение:
F (y, z) =
X
m ≥ 1
X
s ≥ 0
] (
s
G
m
)· y m
· z s
=
X
s ≥ 0
z s
·
X
m ≥ 1
] (
s
G
m
)· y m
=
= ny +
X
s ≥ 1
C
s−1
·
(n
2
· y
2
)
s
(1 − 2ny)
2s−1
· z s
Сравнение коэффициентов при z s
да¨ет первую формулу.
Вторая и третья – применение результата Теоремы 6.12. В
отличие от первой, суммы в них конечны: s ≤ bm/2c.
В нашей совместной работе ([7]) скобочные структуры изу- чены более подробно. С их помощью найдены размерности тождеств одной интересной неассоциативной алгебры.

86 7. ДВОИЧНОЕ РАЗЛОЖЕНИЕ
Натуральные числа неоднозначно представляются суммами степеней двойки. Разнообразие может быть обеспечено сли- янием степеней: 2
k
+ 2
k
= 2
k+1
. И это соображение среди возможных представлений выделяет нетривиальное, состоя- щее из сумм различных степеней двоек:
n = 2
k
1
+ . . . + 2
k d
, где 0 ≤ k
1
< . . . < k d
Показатель k d
ограничен сверху числом blog
2
(n)c – целой частью log
2
(n). Такое представление локально минимально:
если в разложении есть повторения степеней, то за сч¨ет сли- яния можно получить разложение без повторений, короче прежнего. Но из этого не следует, что любое разложение без повторений – кратчайшее из возможных. За отсутствие раз- нообразия разложений без повторов отвечает арифметика.
Действительно, допустим, что какое-то n раскладывается в сумму разных степеней двоек неоднозначно:
n = 2
k
1
+ . . . + 2
k d
= 2
t
1
+ . . . + 2
t a
,
где 0 ≤ k
1
< . . . < k d
; 0 ≤ t
1
< . . . < t a
Число n можно считать наименьшим из возможных, и тог- да старшие степени этих его разложений различны. Можно считать, что k d
< t a
. И тогда получаем неравенство:
n = 2
k
1
+ . . . + 2
k d
≤
X
0 ≤ b ≤ k d
2
b
= 2
k d
+ 1
− 1 <
< 2
k d
+ 1
≤ 2
t a
≤ 2
t
1
+ . . . + 2
t a
= n .
Полученное противоречие доказывает однозначность раз- ложения любого натурального n в сумму разных степеней