Колчин В.Ф. Случайные отображения Изд. 2

---

Предисловие к первому изданию				5
Глава I. Обобщенная схема размещения частиц и случайные отображения				9
§ 1. Вероятностный подход к перечислительным задачам комбинаторики				9
§ 2. Обобщенная схема размещения и полиномиальное распределение				13
§ 3. Примеры сведения комбинаторных задач к обобщенной схеме размещения				18
§ 4. О локальных предельных теоремах				21
§ 5. Кратности вершин случайного отображения				25
§ 6. Связность графов и обобщенная схема размещения				32
§ 7. Обобщенная схема размещения и случайные подстановки				41
§ 8. Свойства распределения логарифмического ряда				43
§ 9. Циклы случайной подстановки				52
§ 10. Линейные комбинации длин циклов				57
§ 11. Порядок случайной подстановки				65
§ 12. Компоненты случайного отображения и обобщенная схема размещения				79
§ 13. Вариационный ряд компонент случайного отображения				86
§ 14. Дополнения и литературные ссылки				95
Глава II. Ветвящиеся процессы и случайные деревья				102
§ 1. Ветвящиеся процессы				102
§ 2. Связь ветвящихся процессов и случайных деревьев				112
§ 3. Предельные теоремы для условных распределений критического ветвящегося процесса				118
§ 4. Условное распределение момента вырождения критического ветвящегося процесса				125
§ 5. Предельные распределения характеристик случайного дерева				140
§ 6. Дополнения и литературные ссылки				148
Глава III. Случайные леса и отображения				152
§ 1. Связь лесов и отображений				152
§ 2. Объемы деревьев в случайном отображении				157
§ 3. Максимальный объем деревьев в случайном отображении				166
§ 4. Ветвящиеся процессы и случайные леса				173
§ 5. Высота случайного отображения				179
§ 6. Дополнения и литературные ссылки				189
Литература				201

---

В последние два десятилетия вероятностные методы занимают все большее место в исследованиях комбинаторного характера. Если на множестве изучаемых комбинаторных объектов задать равномерное распределение, то числовые характеристики этих объектов можно рассматривать как случайные величины и применять для их изучения хорошо развитые в теории вероятностей аналитические методы. Успешное применение этих методов в комбинаторном анализе связано с тем, что при вероятностном подходе ограничиваются изучением свойств типичных представителей рассматриваемого множества комбинаторных объектов, составляющих основную массу этого множества. При этом нетипичные по своим свойствам объекты, число которых составляет малую долю общего числа рассматриваемых объектов, естественным образом исключаются из рассмотрения.

В книге вероятностный подход применяется для изучения однозначных отображений конечного множества в себя, когда число элементов множества стремится к бесконечности. В исследованиях таких комбинаторных объектов нашли применение различные вероятностные методы: метод моментов, асимптотические методы анализа характеристических и производящих функций, в том числе метод перевала. Эти методы приспособлены для установления слабой сходимости последовательностей распределений и наиболее эффективны в случаях, когда изучаемые распределения связаны с последовательностями независимых случайных величин. Как правило, характеристики случайных комбинаторных объектов представляют собой зависимые случайные величины. Однако, хотя кратности вершин, объемы компонент, объемы деревьев случайного отображения, длины циклов случайной подстановки зависимы, их совместное распределение инвариантно относительно перестановки этих случайных величин. Симметричность зависимости позволяет надеяться, что совместное распределение таких характеристик может быть представлено, как в случае бесконечной последовательности симметрично связанных величин, в виде условного распределения независимых величин. Возможность такого представления впервые была отмечена автором и в последнее десятилетие применялась для решения ряда вероятностных задач комбинаторного характера. В книге сделана попытка изложить основные результаты о случайных подстановках, деревьях, лесах и отображениях конечных множеств на основе систематического использования этой возможности представления распределений комбинаторных объектов с помощью независимых случайных величин. Изложение опирается на связь случайных отображений с обобщенной схемой размещения частиц и на связь случайных деревьев и лесов с ветвящимися процессами. Несмотря на внешнее различие этих двух подходов, они объединяются тем, что в обоих случаях применяемые вероятностные методы существенно используют свойство независимости. В обобщенной схеме размещения частиц распределение заполнений ячеек представимо как условное распределение независимых случайных величин при условии, что их сумма принимает фиксированное значение. Аналитические методы, применяемые для анализа ветвящихся процессов, основаны на независимости поведения каждой частицы ветвящегося процесса от ее происхождения и от поведения остальных частиц.

В книге излагаются результаты о случайных комбинаторных объектах, имеющих равномерное распределение на множестве изучаемых объектов. При равномерном распределении, несмотря на вероятностную терминологию, рассматриваемые задачи по существу являются перечислительными задачами комбинаторного анализа и вероятностный подход обеспечивает лишь удобную форму изложения и помогает применять хорошо развитые в теории вероятностей методы асимптотического анализа.

Внимание к рассмотренным в книге комбинаторным объектам, с одной стороны, является отражением общего повышения интереса к комбинаторным задачам, а с другой стороны, вызвано многочисленными применениями этих объектов в различных областях приложений математики. В связи с развитием вычислительной техники знание свойств типичных представителей множеств подстановок деревьев, отображений приобретает особенно важное значение, так как они широко используются при построении и анализе вычислительных алгоритмов.

Простота и наглядность формулировок делает изложенные в книге вероятностные задачи комбинаторного анализа хорошими объектами для демонстрации в педагогической практике применений асимптотических методов теории вероятностей и особенно локальных предельных теорем для целочисленных слагаемых и предельных теорем теории ветвящихся процессов.

Наглядным представлением однозначного отображения конечного множества в себя может служить граф, вершинами которого являются элементы этого множества. Из каждой вершины графа выходит ровно одна дуга, которая соединяет вершину с ее образом при отображении. Каждая компонента связности графа однозначного отображения содержит один контур. Если в графе отображения убрать дуги, составляющие эти контуры, то останется граф, представляющий собой лес. Таким образом, можно считать, что граф отображения строится из деревьев. Поэтому в книге выбран следующий порядок изложения. Вначале рассматриваются взаимно однозначные отображения, граф которых состоит только из контуров. Далее изучаются деревья и леса и с помощью результатов о случайных лесах исследуются случайные отображения.

Книга состоит из трех глав. В гл. I излагаются результаты, получаемые с помощью сведения задач к обобщенной схеме размещения частиц. Особое внимание уделяется изучению циклового строения случайных подстановок, взаимно однозначных отображений конечного множества в себя, а также объемам компонент случайного отображения. В гл. II с помощью теории ветвящихся процессов изучаются случайные деревья. В гл. III связь с ветвящимися процессами распространяется на случайные леса и с помощью результатов о случайных лесах исследуются свойства случайных однозначных отображений.

Излагаемые результаты получены в основном за последние пятнадцать лет. Все литературные ссылки даются в заключительных параграфах каждой главы, при этом не ставится цели дать в этих параграфах исчерпывающий обзор исследований. Кроме статей, прямо использованных в основном тексте, в обзорные параграфы включены работы, в которых приведенные в основном тексте результаты получены другими методами, а также статьи, близко примыкающие по содержанию к материалу соответствующей главы.

Книга доступна читателям, владеющим обычными курсами математического анализа и теории вероятностей. Определения изучаемых комбинаторных объектов приводятся в тексте, однако более широкое знакомство с основными понятиями комбинаторики представляется желательным. Технически наиболее сложными являются доказательства играющих в книге вспомогательную роль локальных предельных теорем для сумм независимых одинаково распределенных целочисленных слагаемых в схеме серий. Известные в теории вероятностей достаточные условия справедливости локальных теорем не охватывают всех случаев их применений, встречающихся в книге. Если в результате развития этой области теории вероятностей появится теорема общего характера, следствиями которой окажутся доказываемые в книге локальные теоремы в схеме серий, то сложность изложения соответствующих разделов существенно уменьшится. Используемая в книге связь характеристик ветвящихся процессов с соответствующими характеристиками случайных деревьев и лесов дает возможность использовать аналитические методы, развитые в теории ветвящихся процессов, при этом в теории ветвящихся процессов возникают новые задачи, вызываемые потребностями изучения случайных деревьев и лесов.

В книге принята следующая нумерация формул, теорем, лемм и следствий. В каждом параграфе для каждого из этих объектов имеется своя нумерация, используемая при ссылках внутри параграфа. При ссылке на объект из другого параграфа той же главы к его номеру добавляется номер параграфа, а при ссылке на объект из другой главы—еще и номер главы. Так, на теорему 1 из § 2 гл. III ссылаются в § 2 гл. III как на теорему 1, в другом параграфе гл. III как на теорему 2.1 ив другой главе как на теорему 3.2.1. Аналогичного правила придерживаются и при ссылках на параграфы, которые в каждой главе имеют свою нумерацию.

Автор благодарен И. Б. Калугину, замечания которого помогли устранить в рукописи ряд неточностей.

1982 г. В. Ф. Колчин

---