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

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

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

Подсчет аналогичен первому случаю, за исключением того, что в начальный момент две вершины уже “заняты” (через них уже проходит хорда).Таким образом, выражение для C2 таково:XkC2 (2n) =Cn−1f (n − k − 1, 2)k≤n,2|(n−k−1)Заметим, что C2 (2n) = C1 (2n − 2).Утверждение 3.3.1. Любая симметричная диаграмма участвует ровно два раза в подсчете C1 (2n) + C2 (2n).Доказательство. В зависимости от четности длины минимального периода и их количества (a и b соответственно)можно выделить три вида расположения осей симметрии.Случай 1: Если b нечетно (а значит a четно). В таком случае все оси симметрии обязательно проходят междувершинами, причем один из концов располагается в середине периода, а второй проходит между периодами. Какизвестно, все оси симметрии получаются при повороте диаграммы на a2 точек. В этом случае при таком поворотеполучается диаграмма, совпадающая с исходной при повороте на π.

То есть такие диаграммы подсчитаны ровнодва раза в C1 по одному с каждого из концов оси.Случай 2: Если b четно, а a нечетно. В таком случае у диаграммы ровно два класса осей симметрии, одному изкоторых принадлежат оси, проходящие через противоположные точки, являющиеся серединами периода, а значитони подсчитаны в C2 , а второму классу принадлежат оси, проходящие между периодами, а значит они включеныв подсчет C1 .Случай 3: Если b и a четны. В таком случае у диаграммы также ровно два типа осей симметрии, оси одного изкоторых проходят между периодами, а второго посередине двух противоположных периодов.Таким образом утверждение верно и количество симметричных диаграмм равнолемма.3.4C1 +C2.2А значит доказана иДоказательство рекуррентных соотношений для D(2n)В леммах 2 и 4 найдены соотношения для A(a, b) и B(2n).

Очевидно, что множество всех хордовых диаграмм с 2nвершинами можно разбить на непересекающиеся подмножества:X — хордовые диаграммы с точностью до поворотов, у которых нет ни одной оси симметрии,Y — хордовые диаграммы с точностью до поворотов, у которых есть ось симметрии,где |X| и |Y | — количество элементов в соответствующих множествах.PУтверждение 3.4.1.

В выражении a≤2n,a|2n A(a, 2na ) + B(2n) каждая диаграмма посчитана ровно 2 раза.7Доказательство. Заметим, что Pесли хордовая диаграмма не имеет оси симметрии (принадлежит иножеству X),тогда она участвует в подсчете a≤2n,a|2n A(a, 2nЕсли же хордоваяa ) ровно два раза, и ни одного раза в B(2n). Pдиаграмма имеет ось симметрии (принадлежит множеству Y ), она участвует по одному разу в a≤2n,a|2n A(a, 2na )и B(2n).Следствие. По предыдущему утверждениюD(2n) =11(|X| + |Y |) = (22XA(a,a≤2n,a|2n2n) + B(2n)).aТеорема 3.1.1 доказана.3.5Доказательство Теоремы 3.1.2Для доказательства теоремы будем пологать, что Теорема 3.1.1 уже известна, и попробуем просто преобразоватьформулы для выражения чисел A(a, b).Воспользуемся следующей теоремой из курса Теории Чисел:Теорема 3.5.1.

(Формула обращения Мебиуса) Для арифметических функций f и gXf (d)g(n) =d|nтогда и только тогда, когдаXnf (n) =µ(d)g( )dd|n.Запишем и преобразуем в общем виде выражения для A(a, b):A(a, b) =1(ϕ(a, b) −aXa0 A(a0 ,ba))a0a0 A(a0 ,ba)a0a0 <a,a0 |aXaA(a, b) = ϕ(a, b) −a0 <a,a0 |aϕ(a, b) =Xa0 A(a0 ,a0 |aba)a0Помним, что ab = 2n и фиксируем nϕ(a,X2n2n)=a0 A(a0 , 0 )aa0a |aОтсюда по Формуле Обращения МебиусаaA(a,X2naa01Xa)=µ(a0 )ϕ( 0 , 2n ) или A(a, b) =µ(a0 )ϕ( 0 , ba0 )aaaa 0a0a |aa |a P1µ(a0 )f ( aa0 , ba0 ),2 - b,a0a |aaa0P1 P0C 2ia0 f (a0 − 2i, ba0 ),2 | b, 2 | a,µ(a )A(a, b) = a a0 |aai=0a −1a0 P2P10µ(a )C 2i+1f ( aa0 − 2i − 1, ba0 ), 2 | b, 2 - a.aaa0a0 |ai=0Таким образом приведены явные выражения для фунции A(a, b) через которую выражается общее количествоклассов эквивалентностей хордовых диаграмм, а соответственно и 2-атомов с точностью до гомеоморфизма.84Алгоритм подсчета количества вырожденных 2-атомов с одной особенностью степени 2n и примеры4.1АлгоритмНапомним, что определения основных функций, которые мы ввели ранее:A(a, b) — это количество хордовых диаграмм с точностью до поворотов и минимальным периодом длины a иab = 2n вершинами;B(2n) — это количество хордовых диаграмм с 2n вершинами с точностью до поворотов и имеющих ось симметрии;D(2n) — это количество хордовых диаграмм с 2n вершинами с точностью до поворотов и отражений (количество вырожденных атомов степени 2n, а также количество ориентированных f-атомов с одной граничной чернойокружностью).Поставим цель посчитать число D(2n).

По Теореме 3.1.1:D(2n) =1(2XA(a,a≤2n,a|2n2n) + B(2n)).aДля подсчета общего количества необходимо посчитать для всех a|2n числа A(a, 2na ).4.2Пример для n = 3Найдем их значения для n = 3:A(1, 6) = 11 (C11 f (0, 6) − 0) = 1, (единственная диаграмма имеющая период 1)1A(2, 3) = 12 (f (2, 3) − A(1, 6)) = 3 1−1= 1, (единственная диаграмма имеющая период 2)21113= 2, (две диаграммы имеющии период 3)A(3, 2) = 3 (C3 f (2, 2) + C3 f (0, 2) − A(1, 6)) = 2 3+1−13A(6, 1) = 61 (f (6, 1) − 3A(3, 2) − 2A(2, 3) − A(1, 6)) = 15−6−2−1= 1, (единственная диаграмма не имеющая периода6меньшего 6)B(6) = 5,D(6) = 1+1+2+1+5= 5.2Ниже приведены соответсвующие хордовые диаграммы и 2-атомы (см. Рис. 3 и Рис.

4 соответственно)Рис. 3: Хордовые диаграммы с точностью до поворотов и симметрий для n = 3.Рис. 4: Атомы степени 6, соответствующие данным хордовым диаграммам.В данном случае все диаграммы имеют ось симметрии, что вводит в некоторые заблуждения, но в следующемпримере приведена более полная картина.94.3Пример для n = 4Аналогичным образом вычислим все необходимые значения:A(1, 8) = 11 (C11 f (0, 8) − 0) = 1,= 2,A(2, 4) = 12 (C20 f (2, 4) + C22 f (0, 4) − A(1, 8)) = 4+1−12A(4, 2) = 14 (C40 f (4, 2) + C42 f (2, 2) + C44 f (0, 2) − 2A(2, 4) − A(1, 8)) = 12+12+1−4−1= 5,4A(8, 1) = 18 (f (8, 1) − 4A(4, 2) − 2A(2, 4) − A(1, 8)) = 105−20−4−1= 10,8B(8) = 16,D(8) = 1+2+5+10+16= 17.2В данном случае отчетливо виден атом, не имеющий оси симметрии (см.

Рис. 5: второй ряд, пятый столбец).Рис. 5: Хордовые диаграммы с точностью до поворотов и симметрий для n = 4.10Рис. 6: Атомы степени 8, соответствующие данным хордовым диаграммам.Список литературы[1] Фоменко А.Т. “Теория Морса интегрируемых гамильтоновых систем”// Доклады АН СССР, 1986, т. 287, No. 5,с. 1071-1075. Объем 0,3 п.л.[2] Болсинов А.В., Фоменко А.Т. “Интегрируемые гамильтоновы системы. Геометрия, топология, классификация”Т.1,2.// Ижевск: Издательский дом “Удмуртский университет”, 199.[3] A.Kruzin, “Enumeration of chord diagrams"// http://arxiv.org/abs/math.CO/008209, 1998[4] Манойло Т.О., Cipa M.I., Кадубовский О.А., “Про число неiзоморфных та нееквiалентних хордовых дiаграмм”//Пошуки i знахiдки 2010 С. 61-70.[5] Gori R., Marcus M., “Counting non-isomophic chord diagrams”// Theoretical Computer Science 301 (2003) 477-489.[6] Joe Sevada, “A fast algorithm to generate necklaces with fixed content”// Theoretical Computer Science - 1998-204.- p.

55-73[7] В.О. Мантуров “Атомы, высотные атомы, хордовые диаграммы и узлы. Перечисление атомов малой сложностис использованием языка Mathematica 3.0”// Топологические методы в теории гамильтоновых систем, сборникстатей, изд. “Факториал”, 1998.[8] А.А.

Ошемков, “Функции Морса на двумерных поверхностях. Кодирование особенностей”// Новые результатыв теории топологической классификации интегрируемых систем, Сборник статей, Тр. МИАН, 205, Наука, М.,1994, 131-140.[9] Harer J., Zagier D. “The Euler characteristic of the moduli space of curves”// Invent. Math. 85 (1986) 457-485.[10] Chmutov S., Prittel B. “The genus of a random chord diagram is asymtotically normal”// arXiv’:1108.5214v3, 2011.11.

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

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