Подсчет количества атомов с одной особой точкой (1162482), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

С каждой частью ребра графа K, соединяющей вершины хордовой диаграммы и находящейся вне окружности проведем следующую операцию: если она соединяет вершины разных цветов, то приклеиваем к диску наданных местах неперекрученную ленточку с нарисованной на ней частью ребра графа K, иначе — перекрученную.Далее красим секторы диска в шахматном порядке в черный и белый цвета и продолжаем раскраску на компоненты связности многообразия P \K.

Так как при построении атома мы можем забыть про нумерацию вершин диска,в котором располагаются 2n концов полуребер, то атом возникает единственный с точностью до гомеоморфизма.Проиллюстрируем сказанное на примере:Так установлено взаимнооднозначное соответствие между классами эквивалентности атомов и хордовых диаграмм.3(a)(b)(c)(d)Рис. 2: Пример построения отображения: (a) хордовая диаграмма; (c) “пробрасываем хорды”; (a) построение графаK; (a) соответствующий атом.33.1Подсчет количества классов эквивалентности хордовых диаграмм с2n вершин с точностью до симметрийФормулы для нахождения числа классов эквивалентностей хордовых диаграммс 2n вершин с точностью до симметрийБудем считать, что у нас есть хордовая диаграмма с 2n вершинами, тогдаОпределение 3.1.1 (Период хордовой диаграммы).

Периодом (соотв. наименьшим положительным) хордовойдиаграммы будем называть количество (соотв. минимальное положительное) вершин, на которое нужно ееповернуть так, чтобы все хорды исходной диаграммы совпали с хордами повернутой. Хордовые диаграммы снаименьшим периодом a называют “диаграммой типа [a]”.Определение 3.1.2 (Расстояние от вершины x до вершины y). Минимальное неотрицательное количество вершин, на которое нужно повернуть хордовую диаграмму так, чтобы вершина x перешла в y называется расстоянием от x до y.Пусть :A(a, b) — это количество хордовых диаграмм типа [a] с ab вершинами с точностью до поворотов;B(2n) — это количество хордовых диаграмм с 2n вершинами с точностью до поворотов и имеющих ось симметрии;D(2n) — это количество хордовых диаграмм с 2n вершинами с точностью до поворотов и отражений;Теорема 3.1.1. Числа A(a, b), B(2n) и D(2n) однозначно определяются следующими рекуррентными соотношениями:D(2n) =1(2XA(a,a≤2n,a|2n42n) + B(2n)).aP1a0 A(a0 , baa (f (a, b) −a0 )),a0 <a,a0 |aa P2P1(Ca2i f (a − 2i, b) − a0 <a,a0 |a a0 A(a0 , baA(a, b) = aa0 )),i=0 a−12PP1(Ca2i+1 f (a − 2i − 1, b) − a0 <a,a0 |a a0 A(a0 , baaa0 )),2 - b,2 | b, 2 | a,2 | b, 2 - a.i=0B(2n) = C1 (2n) + C1 (2n − 2),гдеaf (a, b) = b 2 (a − 1)!!,XC1 (2n) =Cnk f (n − k, 2),k≤n,2|(n−k)причем f (0, b) = 1.Также сформулируем теорему, в которой числа A(a, b) выражаются нерекуррентными формулами:Теорема 3.1.2.

Числа A(a, b), B(2n) и D(2n) однозначно определяются следующими явными формулами:D(2n) =1(2XA(a,a≤2n,a|2n2n) + B(2n)).a P1a00 a 0 µ(a )f ( a0 , ba ),a|aaa0P1 P0µ(a)C 2ia0 f (a0 − 2i, ba0 ),A(a, b) = a a0 |ai=0 aa −1a02PP1f ( aa0 − 2i − 1, ba0 ),µ(a0 )C 2i+1aa0a0 |ai=0a2 - b,2 | b, 2 | a,2 | b, 2 - a.B(2n) = C1 (2n) + C1 (2n − 2),гдеaf (a, b) = b 2 (a − 1)!!,µ(x)- функция МебиусаXC1 (2n) =Cnk f (n − k, 2),k≤n,2|(n−k)причем f (0, b) = 1.Отметим, что явные формулы для чисел A(a, b) имеют преимущества, в случае, если есть необходимость посчитать количество 2-атомов с достаточно большим наименьшим периодом, совершив наименьшее количество операций.

Но реккурентные формулы остаются в плюсе, при необходимости получить полную картину, за счет отсутствияв записи формулы Мебиуса, которая трудоемко реализуется на компьютерах.Доказательства формул будут приведены ниже.3.2Доказательство реккурентных соотношений для A(a, b)В хордовой диаграмме типа [a] выберем первые a подряд идущих вершин. По тому, с какими точками они соединены,можно восстановить всю хордовую диаграмму. Таким образом, все точки разбиты на b = 2n периодов, в каждомиз которых a a точек, которые будем нумеровать от 1 до a. Период, в котором лежит начало отсчета, занумеруемчислом 1.

Оставшимся периодам сопоставим натуральные числа2, ..., b по часовой стрелке. Возьмем точку с номеромi в первом периоде, и пусть она соединена с точкой A. Cопоставим точке i пару чисел (j, k), где j-номер точкиA в своем периоде и k — номер периода, в котором она находится. Заметим, что таким кодированием мы простопоказали, что расстояние между точкой с номером i в любом периоде до ее пары равно (k − 1)a + j − i. Такимобразом, каждой хордовой диаграмме типа [a] мы сопоставили последовательность из a пар чисел.

В дальнейшеминогда мы будем обозначать пару одной буквой, а не двумя. Так, запись x = y может обозначать то, что пара xсовпадает с парой y.5Лемма 3.2.1. Пусть дана хордовая диаграмма типа [a]. Если при повороте на k вершин последовательности,отвечающие исходной и полученной хордовым диаграммам, совпадают, то k кратно a.Доказательство. Так как наименьший положительныq период хордовой диаграммы равен a, без ограниченияобщности будем считать, что поворот происходит на 0 ≤ k ≤ a вершин.

Пусть при повороте на k вершин получается хордовая диаграмма, которой сопоставляется та же последовательность из a пар, что и исходной диаграмме.Обозначим подпоследовательность из k пар, соответствующих точкам периода с номерами 1, ..., k, через c.Так как сдвинутая на k единиц последовательность начинается также с подпоследовательности c, то исходная последовательность начинается с двух подряд стоящих подпоследовательностей c. Возвращаемся к сдвинутойпоследовательности, она начинается с двух подряд стоящих последовательностей , значит, исходная последовательность начинается с трех подпоследовательностей и т.д. На i-ом шаге получаем, что начальная последовательностьначинается с i подряд стоящих подпоследовательностей c.

Это рассуждение мы можем проводить неограниченноечисло раз, даже когда ik > a, что означает,что k — это период хордовой диаграммы, но k ≤ a, a a — это наименьшийпериод хордовой диаграммы, значит, k = 0, откуда следует утверждение леммы.Теперь докажем следующую формулу:P1a0 A(a0 , ba2 - b,a (f (a, b) −a0 )),0a <a,a0 |aa P2P12i00 ba2 | b, 2 | a,A(a, b) = a ( Ca f (a − 2i, b) − a0 <a,a0 |a a A(a , a0 )),i=0a−12PP1Ca2i+1 f (a − 2i − 1, b) − a0 <a,a0 |a a0 A(a0 , baa(a0 )), 2 | b, 2 - a.i=0Рассмотрим случай, когда b - нечетно.Возьмем точку с номером i ∈ {1, ..., a} и посмотрим, какая пара (j, k) может ставиться ей в соответствие. Номерj может быть любым в {1, ..., a} кроме i, так как иначе вершине с номером i в периоде с номером k ставится всоответствие вершина с номером i в периоде с номером 2k−1 ( mod b). Из чего можно сделать вывод, что 2k−2 = b,но b нечетно.

Таким образом, для первой вершины номер j может принимать (a − 1) значений, а k - любое из bзначений. То есть, вариантов пар (a−1)b. Отметим, что точке с номером j однозначно сопоставляется пара (1, b−k+2). Для следующей вершины аналогично количество возможных пар (a − 3)b и т.д.

Так как количество шагов равноab , получаем f (a, b) хордовых диаграмм с (необязательно наименьшим) периодом a. Заметим, что мы посчиталитакже и “лишние” хордовые диаграммы — это те, у которых минимальный период не a, a a0 | a, где 0 ≤ a0 ≤ a.Более того, если отождествить хордовые диаграммы, отличающиеся поворотом, то каждую из нихP мы 0посчиталировно a0 раз в силу леммы 1. После вычитания “лишних” хордовых диаграмм остается f (a, b) −a A(a0 , baa0 ) a0 <a,a0 |aэто диаграммы, у которых минимальный период ровно a.

Но опять же, если отождествлять хордовые диаграммы,отличающиеся поворотом, в силу леммы 1 каждую из них мы посчитали a раз, значит, нужно на a разделить.Получаем требуемый ответ.Рассмотрим случай, когда b - четно. Отличие от случая нечетного b в том, что теперь точке с номером i можетбыть сопоставлена противоположная вершина в многоугольнике, то есть пара (i, b+22 ) (2k − k может быть равноb). Назовем такие точки особыми. Тогда появляется зависимость еще и от четности a, так как, если a четное, тоособых точек в периоде четное число, а при нечетном a - нечетное.Пусть в периоде d особых точек, тогда количество диаграмм типа [a] равно Cad f (a − d, b).

Здесь Cad отвечает зато, какие именно точки в периоде особые, a f (a − d, b) считается аналогично первому случаю после исключенияособых точек. Таким образом, нами доказана справедливость формулы для вычисления A(a, b).3.3Доказательство реккурентных соотношений для B(2n)До сих пор мы рассматривали хордовые диаграммы только с точностью до поворотов, теперь добавим осевыесимметрии. В отличие от A(a, b), для B(2n) подсчет будет проводиться сразу для всей диаграммы без учета минимального периода.Пусть хордовая диаграмма типа [a] симметрична относительно какой-либо оси.

Ось симметрии (или простоось) может проходить либо через противоположные вершины многоугольника (тогда они соединены хордой), либомежду вершинами (следовательно, любые две оси получаются друг из друга поворотом на полуцелое число точек).Изучим, какой вид может иметь период хордовой диаграммы в каждом из этих случаев расположения оси.В дальнейшем нам понадобитсяЛемма 3.3.1. Если a — это минимальный положительный период хордовой диаграммы, то все оси симметрииполучаются друг из друга поворотами на целое или полуцелое количество точек, кратное a2 .6Доказательство.

Пусть хордовая диаграмма симметрична относительно некоторой оси l, а также относительнооси, получившейся из l с помощью поворота по часовой стрелке на k точек. Композиция симметрий относительнодвух указанных осей — это поворот на 2k точек. Она переводит хордовую диаграмму в себя, то есть 2k | a. Изусловия о том, что a минимальный период следует лемма.Лемма 3.3.2. Для B(2n) выполняются следующие соотношения:B(2n) = C1 (2n) + C1 (2n − 2),гдеC1 (2n) =XCnk f (n − k, 2).k≤n,2|(n−k)Доказательство.

Случай 1: Пусть у хордовой диаграммы существует ось симметрии, проходящая между вершинами. C1 — это количество хордовых диаграмм (некоторые, возможно, подсчитаны несколько раз, что будет объясненопозже), у которых существует ось симметрии такого типа. По аналогии с подсчетом A(a, b) выберем Cnk вершинс одной стороны от выбранной оси, которым будут сответствовать вершины, симметричные относительно даннойn−kоси. Оставшимся (n − k) точкам будут соответствовать f (n − k, 2) = 2 2 (n − k − 1)!! вариантов сопоставленияточек. Причем 2 | (n − k). Таким образом, выражение для C1 таково:XC1 (2n) =Cnk f (n − k, 2).k≤n,2|(n−k)Случай 2: Пусть у хордовой диаграммы существует ось симметрии, проходящая через противоположные вершины многоугольника. C2 — это количество хордовых диаграмм (аналогично первому случаю некоторые, возможно,подсчитаны несколько раз), у которых существует ось симметрии такого типа.

Характеристики

Список файлов курсовой работы