Двухцветные хордовые N-диаграммы с одним черным циклом
В статье рассматривается класс двухцветных хордовых N-диаграмм с n хордами, которые имеют только один цикл черного цвета. Установлены формулы для вычисления числа неэквивалентных таких диаграмм относительно действия циклической и диэдральной групп соответственно....
Збережено в:
| Дата: | 2012 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2012
|
| Назва видання: | Труды Института прикладной математики и механики |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/124082 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Двухцветные хордовые N-диаграммы с одним черным циклом / А.А. Кадубовский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 24. — С. 134-146. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124082 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1240822017-09-20T03:03:28Z Двухцветные хордовые N-диаграммы с одним черным циклом Кадубовский, А.А. В статье рассматривается класс двухцветных хордовых N-диаграмм с n хордами, которые имеют только один цикл черного цвета. Установлены формулы для вычисления числа неэквивалентных таких диаграмм относительно действия циклической и диэдральной групп соответственно. У роботi розглядається клас двокольорових хордових N-дiаграм з n хордами, якi мають лише один цикл чорного кольору. Встановлено формули для пiдрахунку числа нееквiвалентних таких дiаграм вiдносно дiї циклiчної та дiедральної груп вiдповiдно. In this paper we consider the set of two-colored chord N-diagrams with n chords that have one cycle of black color. We calculate the number of non-equivalent such diagrams under rotation and refraction. 2012 Article Двухцветные хордовые N-диаграммы с одним черным циклом / А.А. Кадубовский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 24. — С. 134-146. — Бібліогр.: 10 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/124082 519.175 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
В статье рассматривается класс двухцветных хордовых N-диаграмм с n хордами, которые имеют только один цикл черного цвета. Установлены формулы для вычисления числа неэквивалентных таких диаграмм относительно действия циклической и диэдральной групп соответственно. |
| format |
Article |
| author |
Кадубовский, А.А. |
| spellingShingle |
Кадубовский, А.А. Двухцветные хордовые N-диаграммы с одним черным циклом Труды Института прикладной математики и механики |
| author_facet |
Кадубовский, А.А. |
| author_sort |
Кадубовский, А.А. |
| title |
Двухцветные хордовые N-диаграммы с одним черным циклом |
| title_short |
Двухцветные хордовые N-диаграммы с одним черным циклом |
| title_full |
Двухцветные хордовые N-диаграммы с одним черным циклом |
| title_fullStr |
Двухцветные хордовые N-диаграммы с одним черным циклом |
| title_full_unstemmed |
Двухцветные хордовые N-диаграммы с одним черным циклом |
| title_sort |
двухцветные хордовые n-диаграммы с одним черным циклом |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124082 |
| citation_txt |
Двухцветные хордовые N-диаграммы с одним черным циклом / А.А. Кадубовский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 24. — С. 134-146. — Бібліогр.: 10 назв. — рос. |
| series |
Труды Института прикладной математики и механики |
| work_keys_str_mv |
AT kadubovskijaa dvuhcvetnyehordovyendiagrammysodnimčernymciklom |
| first_indexed |
2025-07-09T00:49:17Z |
| last_indexed |
2025-07-09T00:49:17Z |
| _version_ |
1837128388813258752 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2012. Том 24
УДК 519.175
c©2012. А.А. Кадубовский
ДВУХЦВЕТНЫЕ ХОРДОВЫЕ N-ДИАГРАММЫ
С ОДНИМ ЧЕРНЫМ ЦИКЛОМ
В статье рассматривается класс двухцветных хордовых N -диаграмм с n хордами, которые имеют
только один цикл черного цвета. Установлены формулы для вычисления числа неэквивалентных
таких диаграмм относительно действия циклической и диэдральной групп соответственно.
Ключевые слова: хордовая диаграмма, оснащенный цикл, действие диэдральной группы.
Введение. Одной из основных задач многих областей математики, в частности
топологии, является задача о классификации исследуемых объектов, которая в свою
очередь предполагает построение полных инвариантов. В большинстве случаев для
решения последней эффективно используют некоторые графы с дополнительной
информацией, в частности хордовые диаграммы.
Напомним, что хордовой диаграммой порядка n или, коротко, n-диаграммой на-
зывают конфигурацию на плоскости, которая состоит из окружности, 2n точек на
ней (являющихся вершинами правильного 2n-угольника) и n хорд, соединяющих
указанные точки. Две диаграммы называют изоморфными, если их можно совме-
стить в результате поворота. Диаграммы называют эквивалентными, если их можно
совместить с помощью поворота, осевой симметрии или же их композиции.
Вопросами перечисления хордовых диаграмм определенного вида занимался це-
лый ряд известных математиков, в частности авторы работ [1-5]. Задачи о подсчете
числа неизоморфных и неэквивалентных n-диаграмм были полностью решены в ра-
ботах [4], [5]. Подсчет числа неизоморфных (в частности двухцветных) диаграмм
фиксированного рода является достаточно сложной и в общем случае не решенной
задачей. Известными являются лишь результаты для планарных (рода 0), торои-
дальных (рода 1) n-диаграмм и 2m-диаграмм максимального рода m [5].
Двухцветные хордовые O- и N -диаграммы были использованы в работе [6] для
топологической классификации гладких функций определенного класса на замкну-
тых ориентируемых и соответственно неориентируемых поверхностях фиксирован-
ного рода. В [7] установлены формулы для подсчета числа неизоморфных (относи-
тельно действия циклической группы) и неэквивалентных (относительно действия
диэдральной группы) двухцветных O- и N -диаграмм. В [8] установлены форму-
лы для подсчета числа неизоморфных и неэквивалентных O-диаграмм, среди цик-
лов которых только один черный цикл. В [9] подсчитано число неизоморфных O-
диаграмм с одним черным и одним белым циклом. Число неизоморфных и неэкви-
валентных планарных O-диаграмм (рода 0) подсчитано в работе [10].
В данной работе установлены формулы для вычисления числа неизоморфных и
неэквивалентных N -диаграмм с n хордами, среди циклов которых только один цикл
черного цвета.
134
Двухцветные N -диаграммы с одним черным циклом
1. Основные понятия и определения.
Определение 1.1. Рассмотрим окружность и 2n точек на ней, которые являются
вершинами правильного 2n-угольника. Раскрасим ее дуги поочередно в два цвета
(черный и белый) и занумеруем указанные вершины числами от 1 до 2n по ходу часо-
вой стрелки. Полученную конструкцию будем называть двухцветным 2n-шаблоном
– рис. 1 a).
Определение 1.2. Двухцветной хордовой диаграммой будем называть n-диаг-
рамму, дуги окружности которой поочередно раскрашены в два цвета (черный и
белый) – рис. 1 b), c).
В дальнейшем будем рассматривать только те двухцветные n-диаграммы, кото-
рые построены на основе двухцветного 2n-шаблона (рис. 1 a)).
Определение 1.3. 2-цветную n-диаграмму, которая не содержит (содержит)
хорд, соединяющих вершины с номерами одинаковой четности, будем называть O-
диаграммой (N -диаграммой) – рис. 1 c), b).
Под черным (белым) циклом двухцветной n-диаграммы будем понимать череду-
ющуюся последовательность черных (белых) дуг и хорд, в которой конец каждой
черной дуги совпадает с началом единственной хорды, исходящей из нее, а второй
конец каждой такой хорды определяет начало последующей черной дуги.
«Обход» (вычленение) некоторого черного цикла диаграммы можно совершать
начиная с «четного» конца произвольной черной дуги. Назовем ее «стартовой». Дви-
гаясь в направлении против хода часовой стрелки мы достигнем ее начала. Далее
следует двигаться вдоль хорды, исходящей из этого начала, до второго ее конца на
окружности диаграммы. С этого момента и в дальнейшем движение по окружности
совершается исключительно вдоль черных дуг, вторые концы которых однознач-
но определяют последующие хорды цикла. И так до того момента, пока не будет
достигнута «стартовая» дуга черного цикла.
)a )b )c )d
1
2
3
4
5
6
1 2
3
...
2n
1n +
Рис. 1. a) двухцветный 2n-шаблон; b) N -диаграмма с 1 черным и 1 белым циклом; c) O- диаграмма
с 2 черными и 3 белыми циклами; d) N -диаграмма с 1 черным и 1 белым циклами
Множество N -диаграмм, построенных на двухцветном 2n-шаблоне, обозначим
=N
n , N -диаграмм с 1 черным циклом – =N
n,1, а N -диаграмм с 1 черным и 1 белым
циклом – =N
n,1,1 (рис. 1 d)).
Циклическую группу, порожденную элементом ξ = σ2, σ = (1, 2, 3, ..., 2n) на-
зывают группой циклических перестановок порядка n, которую будем обозначать
135
А.А. Кадубовский
C∗
n =
{
ξi|i = 1, 2, ..., n
}
.
Пусть далее
τ =
(
1 2 . . . 2n− 1 2n
2n 2n− 1 . . . 2 1
)
= (1, 2n)◦(2, 2n− 1)◦(3, 2n− 2)◦ ...◦(n, n + 1).
Тогда все симметрии двухцветного 2n-шаблона исчерпываются: n поворотами
ξi ∈ C∗
n, i = 1, 2, ..., n и n (осевыми) симетриями τi = τ ◦ ξi. Группу симметрий
(порядка 2n) двухцветного 2n-шаблона обозначим D∗
2n =
{
ξi, τi | i = 1, ..., n
}
.
Замечание 1.1. Известно (напр. [5], [6], [7]), что группы C∗
n и D∗
2n действуют на
множестве хордовых диаграмм, в частности на множестве =N
n,1, как сопряжение. А
именно: пусть α =
(
1 k1 . . . k2n−1 k2n
k1 1 . . . k2n k2n−1
)
— подстановка (инволюция) на
множестве номеров nj вершин (двухцветного) 2n-шаблона, которая определяет хор-
ды, а поэтому и саму n-диаграмму D = D(α). Тогда очевидно, что каждую диаграм-
му можно отождествить с соответствующей подстановкой. Более того, имеют место
следующие критерии изоморфности и эквивалентности двухцветных диа-
грамм:
диаграмма D1 = D (α1) изоморфна диаграмме D2 = D (α2) тогда и только
тогда, когда ∃i ∈ {1, 2, ..., n} : α1 = ξ−i ◦ α2 ◦ ξi;
диаграмма D1 = D (α1) эквивалентна диаграмме D2 = D (α2) тогда и только
тогда, когда ∃γ ∈ D∗
2n : α1 = γ−1 ◦ α2 ◦ γ.
Замечание 1.2. Занумеруем черные дуги двухцветного 2n-шаблона номерами
от 1 до n по ходу часовой стрелки. Если обход черных дуг единственного черно-
го цикла диаграммы (из класса =N
n,1) начинать с «первой» черной дуги шаблона в
направлении против хода часовой стрелки (рис. 1 d)), то каждой такой диаграмме
однозначно можно поставить в соответствие цикл (длины n), оснащенный знака-
ми номеров черных дуг. Причем оснащение номера черной дуги знаком «минус»
происходит в случае, когда направление обхода дуги меняется на противоположное
в сравнении с направлением обхода предшествующей дуги цикла. Так диаграмме,
изображенной на рис. 1 d), соответствует оснащенный цикл (1, 4,−6, 2,−5, 3).
Более полную информацию можно найти, например в работах [6-8].
2. Число неизоморфных диаграмм из класса =N
n,1.
Пример 1. Очевидно, что не существует N -диаграмм с 1 хордой (класс =N
2,1 яв-
ляется пустым); класс =N
2,1 состоит из единственной диаграммы — рис. 2 a); а число
неизоморфных диаграмм из класса =N
3,1 равно 2 – рис. 2 b).
)a )b
Рис. 2. a) единственная диаграмма из класса =N
2,1; b) неизоморфные диаграммы из класса =N
3,1.
136
Двухцветные N -диаграммы с одним черным циклом
В дальнейшем число неизоморфных (относительно действия группы C∗
n) диа-
грамм из класса =N
n,1 будем обозначать через d
∗(N)
n,1 . Тогда по лемме Бернсайда и с
учетом результатов работ [5], [6], имеет место равенство
d
∗(N)
n,1 =
1
n
∣∣=N
n,1
∣∣ +
∑
i|n,i6=n
ϕ
(n
i
)
· ρ (n, i)
, (1)
где ρ (n, i) – число диаграмм из класса =N
n,1, которые самосовмещаются при пово-
роте (по часовой стрелке) на угол ωi = 2π
2n · 2i = 2π
n · i, то есть число элементов
множества =N
n,1, неподвижных относительно действия группового элемента ξi ∈ C∗
n;
ϕ(·) – функция Эйлера; а суммирование ведется по всем делителям i числа n за
исключением самого n.
Предложение 2.1. Для натуральных n ≥ 2 имеет место равенство
∣∣=N
n,1
∣∣ = (n− 1)! · (2n−1 − 1
)
. (2)
Доказательство. С учетом замечания 1.2, каждую диаграмму из класса =N
n,1
можно отождествить с циклом вида
b = (1, bj2 , bj3 , ..., bjn) , bji ∈ {±2;±3; ...;±n} , bji = bjk
⇔ i = k. (3)
Общее число циклов указанного вида равно (n− 1)! · 2n−1. Однако среди них
точно (n− 1)! циклов, определяющих O-диаграммы с одним черным циклом [8].
Поэтому
∣∣=N
n,1
∣∣ = (n− 1)! · (2n−1 − 1
)
. ¤
Лемма 2.1. Для нечетных n ∈ N имеют место формулы
d
∗(N)
n,1 =
1
n
(n− 1)! · (2n−1 − 1
)
+
∑
i|n,i6=n
ϕ
(n
i
)
· ρ (n, i)
, (4)
ρ (n, i) = ϕ
(n
i
)
·
(n
i
)i−1
· (i− 1)! · (2i−1 − 1
)
. (5)
Доказательство. Пусть n = 2m + 1. Для доказательства утверждения доста-
точно показать, что число диаграмм из класса =N
n,1, которые самосовмещаются при
повороте на угол ωi = 2π
n · i, можно вычислить по формуле (5).
1) Вначале выясним вопрос о том, какой вид имеют оснащенные циклы, определя-
ющие двухцветные диаграммы с одним черным циклом, которые самосовмещаются
при повороте на угол ωi – удовлетворяют условию (∗).
Пусть i = n
k – делитель числа n, k 6= 1. Как было установлено ранее, каждую
такую n-диаграмму можно отождествить с оснащенным циклом b = (1, l2, l3, ..., ln),
элементы которого – номера (с учетом знаков) черных дуг диаграммы, которые
встречаются при обходе единственного черного цикла n-диаграммы D(b).
137
А.А. Кадубовский
Если упорядоченная пара {1, l2} ∈ b, то циклу b должна принадлежать и пара
{1 + i, sign(l2) · (|l2|+ i)}, аналогично {1 + 2i, sign(l2) · (|l2|+ 2i)} ∈ b,...,{1 + i(k −
1), sign(l2) · (|l2|+ i(k − 1))} ∈ b;
если упорядоченная пара {l2, l3} ∈ b, то циклу b должна принадлежать и па-
ра {sign(l2) · (|l2|+ i) , sign(l3) · (|l3|+ i)}, аналогично {sign(l2) · (|l2|+ 2i) , sign(l3) ·
(|l3|+ 2i)} ∈ b,..., {sign(l2) · (|l2|+ i(k − 1)) , sign(l3) · (|l3|+ i(k − 1))} ∈ b.
Таким образом, множество (оснащенных) номеров черных дуг диаграммы, удо-
влетворяющей условию (∗), разбивается на k подмножеств – «черных блоков» [bj ],
в каждом из которых по i (оснащенных) номеров черных дуг:
[b1] = {1, l2, l3, ..., li},
[b2] = {1 + i, sign(l2) · (|l2|+ i) , sign(l3) · (|l3|+ i) , ..., sign(li) · (|li|+ i)},. . . ,
[bk] = {1 + i(k − 1), ..., sign(li) · (|li|+ i(k − 1))}.
2) Взаимное расположение указанных блоков однозначно определяется выбором
блока [bj ], который следует за [b1]. Более того, обход блоков совершается с шагом
h = j − 1. Поясним последнее: допустим, что b = ([b1][b2]...) = (1, l2, l3, ..., li;
1 + i, sign(l2) · (|l2|+ i) , sign(l3) · (|l3|+ i) , ..., sign(li) · (|li|+ i) ; ...).
Так как цикл b содержит упорядоченную пару {li, 1+i}, то циклу b принадлежит
и пара {sign(l2) · (|li|+ i) , 1+2i} ∈ b. Это означает, что после блока [b2] следует блок
[b3] i т.д.. То есть цикл b имеет вид ([b1][b2][b3]...[bk]) и поэтому обход блоков совер-
шается с шагом h = 1. Аналогично из допущения, что b имеет вид b = ([b1][b3]...),
нетрудно заключить, что обход его блоков совершается с шагом h = 2, то есть
b = ([b1][b3][b5]...). И т.д..
Таким образом, имеем (k − 1) возможностей перегруппировать черные блоки.
Однако диаграмма будет иметь один черный цикл только в том случае, когда обход
черных блоков совершается с шагом h, взаимно простым с k = n
i . То есть существует
точно ϕ(k) = ϕ
(
n
i
)
существенно различных типов таких диаграмм.
3) Зафиксируем допустимый шаг h (взаимно простой с k), с которым совершается
обход k черных блоков [b1], [b2], ..., [bk]. Очевидно, что оснащенную дугу bl2 блока [b1]
можно выбрать (n− k)× 2 способами, так как k чисел 1, 1 + i, ..., 1 + i(k− 1) заняли
первые «позиции» в блоках [b1], [b2], ..., [bk];
оснащенную дугу bl3 можно выбрать (n− 2k)×2 способами, так как после выбора
черной дуги с (оснащенным) номером l2, числа l2, sign(l2) · (|l2|+ i) , ..., sign(l2) ·
(|l2|+ i(k − 1)) заняли вторые «позиции» в соответствующих блоках, i т.д.
Итак, при каждом допустимом шаге h можно образовать точно
2 (n− k) · 2 (n− 2k) · 2 (n− 3k) · ... · 2 (n− (i− 1)k) =
(
n
i
)i−1 · (i− 1)! · 2i−1
разных 2-цветных диаграмм с одним черным циклом, которые самосовмещаются
при повороте на угол ωi. Однако среди них содержится точно
(
n
i
)i−1 · (i − 1)! O-
диаграмм с одним черным циклом [8]. C учетом пунктов 2) и 3), существует точно
ϕ
(
n
i
) ·(n
i
)i−1 ·(i−1)! ·(2i−1 − 1
)
диаграмм из класса =N
n,1, удовлетворяющих условию
(∗). ¤
138
Двухцветные N -диаграммы с одним черным циклом
Лемма 2.2. Для четных n ∈ N имеют место формулы
d
∗(N)
n,1 =
1
n
(n− 1)! · (2n−1 − 1
)
+ µ
(
n,
n
2
)
+
∑
i|n,i6=n
ϕ
(n
i
)
· ρ (n, i)
, где (6)
ρ (n, i) = ϕ
(n
i
)
· (i− 1)! · (2i−1 − 1
) ·
(n
i
)i−1
, µ
(
n,
n
2
)
=
(n
2
)
! · 2n−2. (7)
Доказательство. Пусть n = 2m. Так как доказательство первой формулы (7)
повторяет суждения, проведенные для случая нечетных n, то для доказательства
достаточно показать необходимость включения величины µ
(
n, n
2
)
в формулу (6).
( )1 1, 5 ,3, 4, 6, 2 ,8, 7b = − − − − ( )2 1, 3, 7 ,5, 2, 8, 4 ,6b = − − ] [( )3 1 ,3, 2, 8, 4 ,6, 7, 5b = − − − −
1
2
3
4 6
7
8
5
1
2
3
4
5
6
7
8
1
2
3
4 6
7
8
5
Рис. 3.
Величина µ (2m,m) является числом диаграмм из класса =N
n,1, которые само-
совмещаются при повороте на угол ωn/2 = π и которые не были учтены величиной
ρ (2m,m). Указанный тип диаграмм характеризуется наличием хорд, соединяющих
диаметрально-противоположные вершины 2n-шаблона – рис. 3.
Так как n = 2m, то каждая диаметральная хорда 2n-шаблона соединяет вер-
шины с номерами одинаковой четности. Очевидно, что каждая такая хорда может
быть задана парой оснащенных номеров диаметрально-противоположных (черных)
дуг шаблона, а именно {i,− (m + i)} или {−l,− (m + l)}, соответственно. Далее каж-
дую из n указанных таких хорд обозначим {jl,−|j′l|}. Тогда диаграмму D (b) ∈ =N
n,1,
которая содержит диаметральную хорду шаблона (а именно две) и самосовмещается
при повороте на угол ω = π, можно отождествить с одним из m циклов вида:(
1,−(m + 1) , j2, j3, j4, ..., jm−1, jm,−|j′m| , j′m−1, ..., j
′
4, j
′
3, j
′
2
)
,(
1, j2,−|j′2| , sign(j2) · (m + 1), j3, j4, ..., jm,−|j′m| , ..., j′4, j′3
)
,(
1, j2, j3,−|j′3| , j′2, sign(j2) · (m + 1), j4, ..., jm,−|j′m| , ..., j′4
)
,
. . .
(−1] , j2, j3, ..., jm−1, jm,−|j′m| , j′m−1, ..., j
′
3, j
′
2, [sign(j2) · (m + 1)),
где jk ∈ {±2;±3; ...;±m;±(m + 2), ...,±2m}, |j′k| = (|jk|+ m) mod n – номер (чер-
ной) дуги, диаметрально-противоположной дуге |jk|, причем знаки j′k определяются
однозначно. Общее число таких циклов равно µ
(
n, n
2
)
=
(
n
2
)
! · 2n−2. ¤
139
А.А. Кадубовский
С учетом лемм 2.1 и 2.2 окончательно получаем
Теорема 2.1. Для натуральных n имеют место формулы:
d
∗(N)
n,1 =
1
n
µ
(
n,
n
2
)
+
∑
i|n
ϕ2
(n
i
)
(i− 1)!
(
2i−1 − 1
) (n
i
)i−1
, (8)
µ
(
n,
n
2
)
=
{
0, при нечетном n(
n
2
)
! · 2n−2, при четном n.
(9)
3. Число неэквивалентных диаграмм из класса =N
n,1. В дальнейшем число
неэквивалентных (относительно действия диэдральной группы D∗
2n) диаграмм из
класса =N
n,1 будем обозначать через d
∗∗(N)
n,1 . Тогда по лемме Бернсайда и с учетом,
например, результатов работы [7] имеет место соотношение
d
∗∗(N)
n,1 =
1
2
·
(
d
∗(N)
n,1 +
1
n
· s (n)
)
, (10)
где s (n) – общее число симметричных диаграмм из класса =N
n,1.
Так как число диаграмм, симметричных относительно каждой из осей симметрии
(2n-шаблона) фиксированного типа одинаково, то:
s (n) =
{
n · s0 (n) , при нечетном n
n
2 · (s1 (n) + s2 (n)) , при четном n,
(11)
где s0 (n) – число диаграмм (из класса =N
n,1), симметричных относительно фикси-
рованной оси симметрии (первого типа), которая проходит через середины диамет-
рально-противоположных черной и белой дуг шаблона; s1 (n) – число диаграмм из
класса =N
n,1, симметричных относительно фиксированной оси симметрии (второго
типа), которая проходит через середины диаметрально-противоположных черных
дуг шаблона; s2 (n) – число диаграмм из класса =N
n,1, симметричных относительно
фиксированной оси симметрии (третьего типа), которая проходит через середины
диаметрально-противоположных белых дуг шаблона.
)a ( )2, 1 , 3b = − − )b ( )3, 1 , 2b = − − )c ( )3, 5, 1 ,2, 4b = − − )d ( )1 , 5,2, 4 ,6,3b = −
1 2
3 4 5
6
1
2 5
3 4
1
2 3
1
2 3
Рис. 4. a), b) – все диаграммы из класса =N
3,1, симметричные относительно фиксированной оси
симметрии первого типа: s0(3) = 2.
Лемма 3.1. Для нечетных n ∈ N имеют место формулы:
d
∗∗(N)
n,1 =
1
2
(
d
∗(N)
n,1 + s0 (n)
)
, s0 (n) =
(
n− 1
2
)
! · 2n−1
2 ·
(
2
n−1
2 − 1
)
. (12)
140
Двухцветные N -диаграммы с одним черным циклом
Доказательство. С учетом соотношений (10) и (11), для доказательства леммы
достаточно показать справедливость второй формулы (12). Пусть n = 2m+1. Каж-
дую диаграмму D (b) ∈ =N
n,1, которая симметрична относительно фиксированной
оси симметрии первого типа, можно отождествить с циклом вида
(
|j′m|, ..., j′3, j′2, sign(j2) · 1 , j2, j3, ..., jm
)
, (13)
где jk ∈ {±2;±3; ...;±2m}, k = 2, ..., m, а |j′k| = n + 2 − |jk| – номер (черной) ду-
ги, симметричной дуге |jk| относительно соответствующей оси симметрии первого
типа. Причем ∀k ∈ {2, ..., m− 1} знак j′k определяется однозначно, так как должен
совпадать со знаком jk+1, а «последние» дуги jm i j′m всегда соединены самосиммет-
ричной хордой (откуда и следует, что b ⊃ {..., jm, |j′m|, ...}). Знак, с которым номер
«первой» дуги входит в цикл b, определяется знаком j2 – рис. 4 a)− c).
Общее число указанных циклов равно 4m·m! = 22m·m!. Однако среди них точно
2m ·m! циклов, определяющих O-диаграммы с одним черным циклом [8]. Поэтому
s0 (n) = s0 (2m + 1) =
(
n−1
2
)
! · 2n−1
2 ·
(
2
n−1
2 − 1
)
. ¤
Предложение 3.1. Для четных n ∈ N справедливо равенство
s1 (n) =
(n
2
− 1
)
! · 2n
2
−1 ·
(
2
n
2 − 1
)
. (14)
Доказательство. Пусть n = 2m. Тогда диаграмму D (b) ∈ =N
n,1, симметричную
относительно оси симметрии второго типа (проходящей через середины 1-ой и (m+
1)-ой черных дуг шаблона), можно отождествить с циклом вида
(
1 , j2, j3, ..., jm,± m + 1 , j′m, ..., j′3, j
′
2|, sign(j2) · 1
)
, (15)
где jk ∈ {±2; ...;±m;±m + 2; ...;±2m} , k = 2, ..., m, а |j′k| = n + 2 − |jk| – номер
(черной) дуги, симметричной дуге |jk| относительно указанной выше оси симметрии
второго типа, а знаки j′k однозначно определяются знаками jk+1 — рис. 4 d).
Общее число таких циклов равно 22m−1·(m− 1)!. Однако среди них точно 2m−1·
(m− 1)! циклов, определяющих O-диаграммы с одним черным циклом [8]. Поэтому
s1 (n) = s1 (2m) =
(
n
2 − 1
)
! · 2n
2
−1 ·
(
2
n
2 − 1
)
. ¤
Обозначим далее через s21 (n) (s22 (n)) число диаграмм из класса =N
n,1, которые
симметричны относительно фиксированной оси симметрии третьего типа и содер-
жат (не содержат) самосимметричные относительно этой оси симметрии хорды (рис.
5 и рис. 6, соответственно). Тогда имеет место равенство
s2 (n) = s21 (n) + s22 (n) . (16)
Предложение 3.2. Для четных n имеют место формулы
s21 (n) =
(n
2
)
! · 2n
2
−1 ·
(
2
n
2
−1 − 1
)
, s22 (n) =
(n
2
− 1
)
! · 2n−2. (17)
141
А.А. Кадубовский
∃ ( )1,4 , 3,2b = − ( )1,4 , 2,3b = − ( )1, 3,2 , 4b = − − ( )1, 2,3 , 4b = − −
3 2
1 4
3 2
1 4
3 2
1 4
3 2
1 4
Рис. 5. все диаграммы из класса =N
4,1, симметричные относительно фиксированной оси симметрии
третьего типа и которые не имеют самосимметричных хорд: s21 (4) = 4; s21 (2) = 0
)a
( )1 , 2b = −
)b
( )1 ,3, 4 ,2b = −
)c
( )1 , 3, 4 , 2b = − −
)d
( )1 ,2, 4 ,3b = −
)e
( )1 , 2, 4 , 3b = − −
1 2
1
2 3
4 1
2 3
4 1
2 3
4 1
2 3
4
Рис. 6. a) – единственная диаграмма из класса =N
2,1, которая симметрична относительно фиксиро-
ванной оси симметрии третьего типа и не имеет самосимметричных хорд: s22 (2) = 1;
b) − e) – все диаграммы из класса =N
4,1, которые симметричны относительно фиксированной оси
симметрии третьего типа и не имеют самосимметричных хорд: s22 (4) = 4
Доказательство. Покажем вначале справедливость первой формулы (17).
Пусть n = 2m. Тогда диаграмму из класса =N
n,1, которая симметрична относительно
фиксированной (рис. 5 ) оси симметрии третьего типа и содержит самосиммет-
ричные хорды относительно этой оси, можно отождествить с одним из m циклов
вида: (
1,2m , j2, j3, ..., jm−1, jm, |j′m| , j′m−1, ..., j
′
3, j
′
2|, sign(j2) · 1
)
,(
1, j2, |j′2| , sign(j2) · 2m, j3, j4, ..., jm, |j′m| , ..., j′4, j′3|, sign(j3) · 1
)
,
. . .
(1] , j2, j3, ..., jm−1, jm, |j′m| , j′m−1, ..., j
′
3, j
′
2, [sign(j2) · 2m|, +1) (18)
где jk ∈ {±1;±2;±3; ...;±2m} , k = 2, ...,m, |j′k| = n + 1− |jk| – номер (черной) ду-
ги, симметричной дуге |jk| относительно указанной оси симметрии третьего типа,
причем знаки j′k определяются однозначно.
Общее число таких циклов равно 22m−2 · m!. Однако среди них точно 2m−1 ·
m! циклов, определяющих O-диаграммы с одним черным циклом [8]. Поэтому
s21 (n) = s21 (2m) =
(
n
2
)
! · 2n
2
−1 ·
(
2
n
2
−1 − 1
)
.
Теперь покажем справедливость второй формулы (17). Диаграмму из класса
=N
n,1, которая симметрична относительно фиксированной оси симметрии третьего
типа и не имеет самосимметричных хорд шаблона (рис. 6 ), можно отождествить
с циклом вида
(
1 , j2, ..., jm, sign(−J) · 2m , j′2, ..., j
′
m|, sign(−J) · 1
)
, (19)
142
Двухцветные N -диаграммы с одним черным циклом
где jk ∈ {±2;±3; ...;±2m− 1} , k = 2, ..., m, J =
m∏
l=2
sign(jl), |j′k| = n + 1 − |jk|
– номер (черной) дуги, симметричной дуге |jk| относительно фиксированной оси
симметрии третьего типа, причем знаки j′k определяются однозначно.
Общее число таких циклов составляет 22m−2 · (m− 1)!. Методом от противного
нетрудно показать, что среди циклов указанного вида нет таких, которые опреде-
ляют O-диаграммы. Таким образом, s22 (n) =
(
n
2 − 1
)
! · 2n−2. ¤
С учетом соотношений (14), (16) и (17), имеем
1
2
(s1(n) + s2(n)) =
(n
2
− 1
)
! · 2n
2
−2 ·
(
2
n
2 +
(
2
n
2
−1 − 1
)
·
(n
2
+ 1
))
. (20)
C учетом соотношений (10), (11), леммы 3.1 и соотношения (20) окончательно по-
лучаем
Теорема 3.1. Для натуральных n имеют место формулы
d
∗∗(N)
n,1 =
1
2
(
d
∗(N)
n,1 +
(
n−1
2
)
!2
n−1
2
(
2
n−1
2 − 1
))
, при нечетном n
1
2
(
d
∗(N)
n,1 +
(
n−2
2
)
!2
n
2
−2
((
2
n−2
2 − 1
) (
n
2 + 3
)
+ 2
))
, при четном n.
(21)
Дополнения. Ниже в таблице приведены начальные значения общего числа,
числа неизоморфных, а также числа неэквивалентных диаграмм из класса =N
n,1
Таблица 1. Начальные значения величин dN
n,1, d
∗(N)
n,1 , d
∗∗(N)
n,1 .
n dN
n,1 d
∗(N)
n,1 d
∗∗(N)
n,1
1 0 0 0
2 1 1 1
3 6 2 2
4 42 13 10
5 360 72 48
6 3 720 642 361
7 45 360 6 480 3 408
8 640 080 80 246 40 735
9 10 281 600 1 142 424 574 092
10 185 431 680 18 546 824 9 285 124
11 3 712 262 400 337 478 400 168 798 720
12 81 709 689 600 6 809 212 572 3 404 876 046
Пример 2. На рис. 7 приведены все неизоморфные диаграммы из класса =N
4,1. Не
трудно видеть, что за исключением диаграмм 8 и 9, 10 и 11, 12 и 13 эти диаграммы
являются также и неэквивалентными. Поэтому, d
∗∗(N)
4,1 = 13− 6 + 3 = 10.
143
А.А. Кадубовский
1 2 3 4 5 6 7
8 9 10 11 12 13
Рис. 7. все неизоморфные диаграммы из класса =N
4,1
Пример 3. На рисунках 8 и 9 приведены все неизоморфные диаграммы из класса
=N
5,1.
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
Рис. 8. все симметричные неизоморфные диаграммы из класса =N
5,1
144
Двухцветные N -диаграммы с одним черным циклом
25 26 27 28 29 30
31 32 33 34 35 36
37 38 39 40 41 42
43 44 45 46 47 48
49 50 51 52 53 54
55 56 57 58 59 60
61 62 63 64 65 66
67 68 69 70 71 72
Рис. 9. все несимметричные неизоморфные диаграммы из класса =N
5,1
Для каждого i = 12, ..., 35 диаграммы с номерами (2i + 1) и (2i + 2) являют-
ся эквивалентными относительно действия диэдральной группы (рис. 9 ). Поэтому
145
А.А. Кадубовский
d
∗∗(N)
5,1 = 72− 48 + 24 = 48.
Выводы. Как было отмечено ранее, в общем случае задачи о подсчете числа
неизоморфных и неэквивалентных двухцветных O- и N -диаграмм фиксированного
рода являются нерешенными. Однако они имеют непосредственную связь с под-
счетом числа топологически неэквивалентных гладких функций (векторных полей)
определенного класса на замкнутых ориентируемых и неориентируемых поверхно-
стях соответствующего рода. По мнению автора вполне достижимым является под-
счет числа неизоморфных диаграмм из класса =N
n,1,1 для случая простых n.
1. Touchard J. Sur une problème de configurations et sur les fractions continues // Can. J. Math. –
1952. – №. 4. – P. 2-25.
2. Riordan J. The distribution of crossings of chords joining pairs of 2n points on a circle //
Mathematics of Computation. – 1975. – Vol. 29, № 129. – P. 215-222.
3. Harer J., Zagier D. The Euler characteristic of the moduli space of curves // Inventiones mathe-
matical – 1986. – № 85. – P. 457-485.
4. Stoimenov A. Enumeration of chord diagrams and an upper bound for Vassiliev invariants // Journal
of Knot and its Ramifications. – 1998. – Vol. 7, No. 1. – P. 93-114.
5. Cori R., Marcus M. Counting non-isomorphic chord diagrams // Theoretical Computer Science. –
1998. – Vol. 204. – P. 55-73.
6. Кадубовський О. Топологiчна еквiвалентнiсть функцiй на орiєнтованих поверхнях // Укра-
їнський математичний жур. – 2006. – Т. 58, № 3. – С. 343-351.
7. Кадубовський О.А., Сторожилова О.В., Сторожилова Н.В. Двокольоровi O- i N -дiаграми //
Пошуки i знахiдки. Серiя: фiзико-матем. науки. – 2010. – Том IV, вип. 1. – С. 41-50.
8. Кадубовський О.А., Саприкiна Ю.С., Мазур С.Ю. Двокольоровi O-дiаграми з одним чорним
циклом // Пошуки i знахiдки. Серiя: фiзико-матем. науки. – 2010. – Том IV, вип. 1. – С. 51-60.
9. Кадубовський О. Про один клас хордових дiаграм максимального роду // Вiсник Київського
унiверситету Серiя: фiзико-матем. науки. – 2006. – Вип. 1. – C. 17-27.
10. Callan D., Smiley L. Non-crossing Partitions under Rotation and Reflection // Arxiv: math. – 2005.
— 15 p. – Access mode: http://arxiv.org/abs/math.CO/0510447.
A.A. Kadubovskiy
2-color chord N-diagrams with one black cycle.
In this paper we consider the set of two-colored chord N -diagrams with n chords that have one cycle of
black color. We calculate the number of non-equivalent such diagrams under rotation and refraction.
Keywords: chord diagrams, equipped faces, under rotation and refraction.
О.А. Кадубовський
Двокольоровi хордовi N-дiаграми з одним чорним циклом.
У роботi розглядається клас двокольорових хордових N -дiаграм з n хордами, якi мають лише один
цикл чорного кольору. Встановлено формули для пiдрахунку числа нееквiвалентних таких дiаграм
вiдносно дiї циклiчної та дiедральної груп вiдповiдно.
Ключовi слова: хордова дiаграма, оснащений цикл, дiя циклiчної та дiедральної груп.
Донбасский государственный педагогический ун-т, г. Славянск
kadubovs@ukr.net
Получено 25.04.12
146
|