Читать онлайн «Вероятностные методы в комбинаторном анализе»

В последние два десятилетия для решения комбинаторных задач в дискретной математике эффективно используются вероятностные методы. На этой основе сложилось определенное направление исследований, содержащее целый ряд интересных и законченных результатов. Основной целью данной монографии является изложение некоторых общих принципов применения вероятностных методов в исследованиях по комбинаторному анализу и их иллюстрация при решении конкретных комбинаторных задач преимущественно перечислительного характера. Наибольшее внимание уделяется получению асимптотических результатов, так как применение указанных методов в этом случае является наиболее плодотворным. Наряду с общими предельными теоремами теории вероятностей, в книге используются специфические приемы получения асимптотических распределений, основанные, как правило, на применении метода моментов, характеристических функций и производящих функций моментов. Книга имеет определенную связь с опубликованной монографией автора «Комбинаторные методы дискретной математики», которая в известной степени может служить введением в рассматриваемый круг вопросов. В то же время наличие в книге необходимого справочного материала дает возможность не обуславливать ее чтение предварительным знакомством с литературой по данной проблематике. В. Н. САЧКОВ ВЕРОЯТНОСТНЫЕ МЕТОДЫ В КОМБИНАТОРНОМ АНАЛИЗЕ if^Si <0 щ МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1978 22. 174 С 22 УДК 519. 1 Вероятностные методы в комбинаторном анализе. В. Н. Сачков. Главная редакция физико-математической литературы изд-ва «Наука», М. , 1978. Книга посвящена применению вероятностных методов к решению задач комбинаторной математики, прежде всего, в плане получения результатов асимптотического характера. На множествах объектов определенных классов задаются вероятностные распределения и исследуются точные и предельные распределения случайных величин — характеристик случайно извлекаемых объектов. Для отыскания предельных распределений используются методы производящих и характеристических функций и модификации классических предельных теорем теории вероятностей. 20204—147 (g) Главная редакция 54-78 физико-математической' литературы 053 (02)-78 издательства «Наука». 1978 ОГЛАВЛЕНИЕ Предисловие 5 Введение 7 Глава I. Некоторые сведения из теории вероятностей . . 10 § 1. Вероятностные распределения и случайные величины И § 2. Характеристические функции и производящие функции моментов * . . . . 29 § 3. Вероятностные распределения в комбинаторном анализе 41 § 4. Асимлтотичеекие формулы и предельные распределения 49 Глава II. Комбинаторные свойства случайных неотрицательных матриц 63 Введение 63 § 1. Неотрицательные целочисленные матрицы ... . 66 § 2. Перманенты случайных 0,1-матриц 71 § 3. Трансверсали случайных множеств 74 § 4. Перманенты случайных 0,1-матриц с заданным числом единиц 79 § 5. Среднее значение перманента случайной дважды стохастической матрицы 92 Глава III. Вероятностные задачи в общей комбинаторной схеме 101 Введение г101 § 1. Вероятностные распределения для коммутативного несимметричного /г-базиса 107 § 2.