Диссертация (1137428), страница 2

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

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

Краткий обзор уже накопленных в рамках этой моделирезультатов приводится в данной главе.9§2. ОтображенияПодстановки – это особый вид отображений конечногомножества в себя, поэтому предварительно мы кратко напомнимнекоторые общие факты из теории отображений, которые понадобятсянам в дальнейшем.ПустьX  x и Y  y - два произвольных множества.Отображением множества X в Y называется любое правило(обозначим его символом s), ставящее в соответствие каждомуэлементу x X некоторый элемент y Y . Это записывается так:SX Yили (более детально) y  s x  , x  X . Элемент y  Y , вкоторый отображается x , называется его образом, а исходныйэлемент x – прообразом у (при отображении s).При этом мы всегда будем предполагать выполненным свойствооднозначности: образ всегда только один.

Что касается числапрообразовданногоy Y , то для каждого конкретного типаотображения оно может быть своим, то есть это число являетсяхарактеристикой отображения.Взадачахдискретнойматематики,какправило,рассматриваются конечные множества. Если объем X  n , то говорятоб n-множестве и записывают его так: X n  1,2,..., n. Часто множествоY совпадает с X.

В этом случае говорят об отображении множества Хв себя – именно этот случай и рассматривается в теории подстановок.10Любое отображениеSXn Xnможно записатьв видеследующей таблицы:1s   s12s2kskn,s n (2.1)где в верхней строке перечисляются элементы множества X n , а внижней-соответствующиеобразыприотображенииs:sk  sk  X n , k  1,2,..., n.Нагляднымпредставлениемотображенияsслужиториентированный граф Г n  s  , множество вершин которого составляетX n , а множество ребер (дуг) образованоnдугамиk, sk ,направленными из k в sk , k  1,2,..., n. .Число дуг, входящих в вершину k в графе Г n  s  , равно числупрообразов элемента k при отображении s и называется кратностьювершины k.Граф Г n  s  отображения s естественным образом разбивается насвязные компоненты, при этом каждая связная компонента содержитровно один контур (цикл) и, возможно, подходы к нему.

Если какойто элемент k  X n отображается в себя же: k  sk  (в этом случаеговорят, что отображение s оставляет элемент k на месте), то в графеГ n  s  в вершине k имеется петля. Таким образом, петля - это циклдлины 1. Вершины графа Г n  s  , лежащие на циклах, называютсяциклическими, их число для конкретного цикла называется длинойэтого цикла.11Важнейшими характеристиками отображенияявляются:sчисло связных компонент графа Г n  s  , число циклических точек,число циклов заданной длины, размер наибольшей компоненты(число вершин в ней) и т.д.Приведем два важных примера конкретных отображений.Еслина отображениеsне накладывается никакихдополнительных ограничений (помимо однозначности), то естьвнижней строке таблицы (2.1) на каждом месте может стоять любойэлемент множества X n , то мы получаем класс всех однозначныхотображений множества X n в себя, обозначаемыйчисло таких отображенийn .Очевидно,n = n n .Если отображение s взаимно однозначное, то есть для любогоk  X n имеется только один прообраз, то нижняя строка таблицы (2.1)содержит все элементы X n , как-то переставленные.

Число всехперестановок из n элементов равно n!; таким образом, числоразличных взаимно однозначных отображений множества X n в себяравно n!. Такие отображения называются подстановками степени nилиn-подстановками,множествовсехтакихподстановокобозначается S n . Для любой подстановки s  S n ее граф Г n  s  состоиттолько из циклов, кратности всех вершин равны 1 и все вершиныявляются циклическими.Подстановки играютв математике и её приложенияхисключительную роль, они и являются предметом нашего внимания.В теории отображений основной интерес представляют, такназываемые, перечислительные комбинаторные задачи, связанные12с подсчетом числа отображений заданного класса, обладающихизучаемым свойством.

Например, может представлять интересвопрос: сколько существует n-подстановок, имеющих заданное числоциклов определенной длины? При решении задач такого рода весьмаэффективным оказался вероятностный подход, впервые примененныйВ.Л. Гончаровым в [1]. В настоящее время вероятностный подходуспешно применяется при исследовании структуры различныхкомбинаторныхобъектов,втомчислеиразличныхтиповотображений.Опишемобщуюсхемусведенияперечислительныхкомбинаторных задач к соответствующим вероятностным задачам.Пусть Fn ={s} - некоторый класс отображений множества X n в себя, иH есть некоторое свойство, которым каждое отображение s  Fn можетобладатьилинет.Подмножествоотображений,обладающихсвойством H, обозначим Fn (H).

Суть вероятностного подхода дляопределения объема Fn  H  состоит в следующем. На множестве Fnзадается равномерная вероятностная мера, приписывающая каждомуотображению s  Fn вероятность его наблюдения P(s)=1.FnТем самым получается конструкция случайного отображения.Далее, по классическому определению вероятности, можем записатьсоотношение:P s  Fn  H  =Fn  H .Fn(2.2)Если мы можем, используя вероятностные методы, вычислить(или хотя бы приближенно оценить) эту вероятность, то мы получаемответ в виде:13Fn  H  =P s Fn  Fn .(2.3)Так перечислительная задача вычисления объема Fn  H  сводится квероятностной задаче вычисления вероятности случайного события{ s  Fn  H  }. Для решения же последней задачи можно использоватьмощный аппарат современной теории вероятностей и в особенностиее предельные теоремы.Дело в том, что для практическихприменений особо актуальны ситуации, когда параметр n принимаетвесьма большие значения ( n   ).

В этих случаях необходимасимптотический анализ, и предельные теоремы теории вероятностейкак раз и являются эффективным инструментом проведения такихисследований.14§3. Подстановки и их цикловая структураКак уже говорилось выше, n-подстановка – это взаимнооднозначное отображение множества Xn = {1,2,….,n} в себя, класс(множество) всех таких отображений обозначается Sn = {s}, их числоесть S n = n!. Стандартная запись подстановки s имеет вид:1s   s12s2kskns n (3.1)где нижняя строка (s1, s2, … , sn) представляет собой некоторуюперестановку чисел (1,2,….,n). Отметим некоторые важные свойстваподстановок.Дляподстановокпроизведение:еслиестественнымsиgобразомопределяетсяихпроизвольныеn-подстановкитопроизведение sg есть n-подстановка, которая действует по правилуsg(k) = g(s(k)), k  Xn .Такимобразом,произведениеsg–этопоследовательноеприменение этих отображений (сначала применяется s, затем g).

Этаоперация ассоциативна: sghk   sg hk   h g sk  , но, вообщеговоря, не коммутативна.Далее, в множестве Sn имеется единичная подстановка e,оставляющая все элементы Xn на месте: e(k)=k для всех k  X n ; длянее таблица (3.1) принимает вид:1 2 ... ...e  1 2 ... ...n.n 15s  S n соответствует единственнаяНаконец, каждой подстановкеподстановка s-1  Sn такая, что s-1 s = ss-1 = e.Тем самым n-подстановки Sn образуют группу, которая называетсясимметрическойгруппойстепениn.Групповыесвойстваподстановок изучаются в алгебре; об их значении говорит, вчастности, известная теорема Кэли о том, что любая конечная группаизоморфна симметрической группе подстановок или некоторой еёподгруппе. Мы же будем акцентировать внимание на комбинаторныхсвойствах подстановок, связанных с их цикловой структурой.Рассмотрим граф Г n  s  произвольной подстановки s  S n .

Как ужеотмечалось раньше, этот граф состоит только из циклов вида i → j →k → … → r → i, которые записываются в виде строки (i, j, … , r),называемой циклом подстановки s; длина этого цикла равна числувходящих в него элементов (числу соответствующих вершин в циклеграфа Г n  s  ); при этом цикл длины 1 имеет вид (i) и соответствуетпетле в Г n  s  в вершине i. Таким образом, подстановки из Sn могутсодержать циклы любой длины j, 1≤ j ≤ n, и любую подстановкуs  S n можно записать в виде произведения ее циклов:s = i1 i2 i1  j1 , k1  j2 , k 2 ... j 2 , k 2 …(3.2)Представление (3.2) означает, что подстановка s имеет α1 цикловдлины 1, α2 циклов длины 2 и т.д.Говорят, что подстановка s Sn принадлежит цикловому классу1 2 ...n , если она содержит αj циклов длины j, 1≤ j ≤ n. Набор 12n=(α1, α2, … , αn) называется цикловой структурой подстановки s.

Посвоемуопределениюкомпонентывекторасутьцелыенеотрицательные числа, удовлетворяющие соотношению:161α1 + 2α2 + … + nαn = n.ПодсчетчислахарактеристикамиподстановокцикловойвSn(3.3)сструктурытемииилиинымисоставляеткругкомбинаторных (перечислительных) задач в теории подстановок. Прирешениитакихсоответствиисзадач используется вероятностный подход, вкоторымсчитается,чтокаждаяподстановкаs  S n может наблюдаться с одной и той же вероятностью P(s)=1.Вn!этом случае говорят о равновероятных (или случайных) nподстановках.Для случайной подстановки s  S n ее цикловая структура  = (α1,α2, … , αn) становится случайным вектором, и его распределениеявляется основой для вероятностного анализа свойств случайнойподстановки.17§4.

Случайные подстановки, распределение их цикловойструктурыОбозначим K n a  число n-подстановок в цикловом классе1a 2 a ...n a ,12na = (a1, a2, … , an),r 1 ra r  n .nТогда для случайнойподстановки по классическому определению вероятности имеемP  a  K n a ,n!(4.1)следовательно, ключевую роль в этой проблематике играют числаK n a .Для этих чисел известна формула КэлиK n a  =n!n ar ! r.ar(4.2)r 1Из формул (4.1) и (4.2) следует, чтоP  a   nn1,если ra r  n, a ! r arr 1r 1 r0 в противном случае.Если использовать индикатор: I  A  1, если A имеет место, и 0 впротивном случае, то последнее соотношение удобно записывать вболее компактном виде: n n1P  a   I   ra r  n .a r 1 r 1 a r ! r r(4.3)18Представление(4.3),хотяидаетответнавопросораспределении цикловой структуры случайной подстановки, но изнего трудно извлекать конкретную информацию об особенностяхцикловойструктуры.эффективнымявляетсяДлядальнейшегоиспользованиепродвиженияаппаратавесьмапроизводящихфункций.Введём производящую функцию цикловой структуры  = (α1, α2, … ,αn)Fn t1 ,..., t n   E t r  r   P  a  t r ar .nnr 1r 1aТогда, с учетом (4.3), она имеет вид:Fn t1 ,..., t n  na:  rar  nt  rr r 1nar1.ar !(4.4)r 1Рассмотрим теперь разложение экспонентыarzr   1  zr  t r  .exp  t r    r  ar 0 ar !  r Тогдаn  zr  zr   nt r  ar 1exp  t r    exp  t r    z    . r 1 r  r 1 r  n0 a: n ra n r 1  r  ar ! r(4.5)r 1Сравнивая (4.4) и (4.5), можем записать, что  zr Fn t1 ,..., t n   z n exp  t r . r 1 r  (4.6)19Этоиестьитоговоеиудобноедлядальнейшегоанализапредставление для производящей функции цикловой структурыслучайной равновероятной n-подстановки.Представление (4.6) можно записать и в несколько ином виде.Посколькуzrzrt r r  r tr  1  ln 1  z ,r 1r 1то, вместо (4.6) для Fn t1 ,..., t n  можно записать представление  zr1Fn t1 ,..., t n   zexp  t r  1.1 z r 1 r nСформулируемполученныйрезультатв(4.7)видеследующегоутверждения.Теорема1.Дляслучайнойn-подстановкипроизводящаяфункция Fn t1 ,..., t n  её цикловой структуры  = (α1, α2, … , αn) имеетвид (4.7).Соотношение (4.7) является базовым в теории случайныхподстановок:изнегоможноизвлечьвсюинформациюобособенностях и свойствах цикловой структуры n-подстановок, что ибудет продемонстрировано в дальнейшем.

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

Список файлов диссертации