Cтраница 2
Многие результаты, приводимые в книге, получены путем сведения комбинаторных задач к соответствующей обобщенной схеме размещения. [16]
Графы, состоящие из некорневых деревьев и компонент ровно с одним циклом, играют такую же роль в исследовании случайных графов как и леса из корневых деревьев в исследовании графов случайных отображений. Поэтому в последующих разделах внимание сосредоточено на таких графах, причем для их изучения используется обобщенная схема размещения частиц. [17]
Гончаров детально исследовал цикловую структуру случайных подстановок, интерес к этому кругу задач сохраняется. В [48] для изучения характеристик случайных подстановок был предложен подход, использующий их связь с обобщенной схемой размещения. [18]
Все эти доказательства довольно сложны. По нашему мнению, простейшее доказательство, но все еще не достаточно простое, предложено в [55], где используется подход с привлечением обобщенной схемы размещения. [19]
Терминология классической схемы размещения оказалась удобной для описания многих задач, в которых появляется полиномиальное распределение. Введение обобщенной схемы размещения частиц не только расширяет область использования удобного языка для описания комбинаторных структур, но также дает возможность применять те методы, которые опираются на соотношение (1.2.2) и были развиты при анализе классической схемы. [20]
Имеется огромное число работ по теории графов и нет никакой возможности дать здесь их обзор. При анализе случайных структур использовались разнообразные вероятностные методы, в том числе метод моментов, пуассоновская и гауссовская аппроксимации, производящие функции и их анализ методом перевала, теоремы тауберова типа, теория мартингалов. В последние три десятилетия в вероятностной комбинаторике широкое распространение получил подход, основанный на применении так называемой обобщенной схемы размещения, который сводит ряд комбинаторных задач к задачам о суммах независимых случайных величин, классическому объекту изучения в теории вероятностей. Свое название эта схема получила в связи с тем, что она является обобщением задачи о случайном размещении п частиц в N ячеек. [21]
В параграфах 1.4 - 1.6 изучаются случайные леса из некорневых деревьев. В параграфе 1.4 рассматривается число таких лесов. Полный анализ случайных лесов из некорневых деревьев был проведен В. Е. Бритиковым, использовавшим в своих исследованиях обобщенную схему размещения. [22]
В этом разделе приводятся результаты о подстановках с ограничениями на длины их циклов. Мы будем рассматривать множество Sn R всех подстановок степени п, длины циклов которых принимают значения из множества R. Одной из первых задач, возникающих в этой ситуации, является задача об асимптотическом поведении числа аП) д элементов в множестве Sn R. В этом разделе будут приведены некоторые результаты, полученные с помощью привлечения обобщенной схемы размещения. [23]