AN INTRODUCTION TO COMBINATORIAL ANALYSIS JOHN RIORDAN Member Technical Staff Bell Telephone Laboratories, Inc. New York-John Wiley & Sons, Inc. London •Chaprnan^& Hall, Limited 1 958 ДЖ. РИОРДАН ВВЕДЕНИЕ В КОМБИНАТОРНЫЙ АНАЛИЗ Перевод с английского Л. Е. САДОВСКОГО Под редакцией л. я. КУЛИКОВА ИЗДАТЕЛЬСТВО ИНОСТРАННОЙ ЛИТЕРАТУРЫ МОСКВА 1963 50 АННОТАЦИЯ Книга Дж. Риордана содержит оригинальное изложение ком- бинаторного анализа — области математики, близкой к теории чисел, алгебре, теории вероятностей и имеющей большое приклад- ное значение. Основным аппаратом, которым пользуется автор при решении задач комбинаторики, является метод производящих функций и символическое исчисление. В конце каждой главы име- ется большое число задач, помогающих активно усваивать изло- женные в книге методы. На русском языке нет книг, посвященных систематическому изложению комбинаторного анализа. Перевод книги Дж. Риордана восполняет этот существенный пробел. Книга, несомненно, будет полезна научным работникам и инженерам различных специаль- ностей, а также студентам и аспирантам, желающим расширить и углубить свои знания в области комбинаторики. Редакция литературы по математическим наукам ИЗ ПРЕДИСЛОВИЯ АВТОРА Комбинаторный анализ является хорошо изученным разделом математики, однако его границы определены недостаточно четко. Началом комбинаторного анализа следует считать «ars combinatoria» Лейбница, если этот раздел понимать в смысле Нетто (N e t t о Е., Lehrbuch der Combinatorik, Leipzig, 1901), т. e. как совокуп- ность исследований о расположении, упорядочении или выборе элементов некоторого множества. Этот же смысл вложен в назва- ние книги Уитворта «Выбор и случай» (Whithworth "W. А., Choice and Chance, London, 1901), одной из немногих книг по этому вопросу, изданных в Англии. Ее удачное название подчеркивает также тесную связь между комбинаторикой и теорией вероятностей. Мак-Магон в своем весьма основательном трактате указывает только, что комбинаторный анализ занимает промежуточное поло- жение между алгеброй и высшей арифметикой, понимая под послед- ней то, что сейчас называется теорией чисел. Современный американский словарь (Funk and Wagnalls New Standard, 1943) определяет «комбинаторику» (этим удобным сокра- щением пользуемся и мы в нашей книге) как «раздел математики, изучающий составление, перечисление и свойства разбиений, вариа- ций, сочетаний и перестановок из конечного числа элементов при различных условиях». Более удачным на наш взгляд является определение комби- наторного анализа, данное Августом де Морганом (de Morgan A., Differential and Integral Calculus, London, 1842): «Комбинаторный анализ состоит главным образом в изучении сложных разложений при помощи априорных соображений и набо- ра различных комбинаций членов, в которые могут входить коэф- фициенты». 6 Предисловие Ни одно из приведенных выше определений не является вполне удовлетворительным, так как не дает четкого ответа на вопрос, что относится и что не относится к комбинаторике. Авторы трех упомянутых книг могли позволить себе некоторую неточность, так как само содержание этих книг говорило о том, что именно авторы имели в виду. Определение, даваемое словарем, не оставляет места для новых приложений комбинаторной техники (такие при- ложения имеются в последнем разделе гл. VI настоящей книги, посвященном числовому описанию деревьев, сетей и линейных гра- фов). Определение де Моргана утверждает, что, говоря современ- ным языком, коэффициенты производящих функций могут быть определены путем решения комбинаторных задач, однако в нем ничего не сказано о решении комбинаторных задач с помощью определения коэффициентов производящих функций. Так как комбинаторный анализ развивается в нескольких новых направлениях, то при его определении имеется опасность чрезмер- ной узости, и некоторая расплывчатость, быть может, желательна. В настоящей книге «комбинаторным» считается все то, что «перечисля- емо»; на протяжении всей книги основное внимание уделяется оты- сканию числа способов выполнения некоторых точно определенных операций. Сюда включаются все традиционные разделы, перечислен- ные в определении, данном в словаре, а также и новый материал, упомянутый выше. Поэтому данная книга может служить введением в рассматриваемый нами предмет, отвечающим современному его уровню. Современное развитие комбинаторного анализа тесно связано с использованием производящих функций. В целях использования этих функций для нужд комбинаторики, их, следуя Беллу, естест- венно считать инструментом алгебры последовательностей и по- этому, несмотря на внешнее сходство с производящими функциями из анализа, относить к алгебре, а не к анализу. Использование производящих функций намного сокращает объем необходимых преоб- разований, позволяет унифицировать многие результаты и тем са- мым дает возможность охватить значительно больший круг вопро- сов. Применяя производящие функции в качестве основного ору- дия комбинаторики, можно показать, что метод включения и исклю- чения связан с использованием факториальных моментов (что дол- Предисловие ~1 жно представлять некоторый интерес для статистиков). Наконец, метод производящих функций хорошо согласуется с методом пред- ставления вероятностей, данным В. Феллером в его книге «Введе- ние в теорию вероятностей и ее приложения». Представляются полезными следующие замечания о содержании книги. Глава I дает беглый обзор той части теории перестановок и сочетаний, которая приводится в книгах по элементарной алгебре. Однако здесь подчеркивается связь результатов этой теории с произ- водящими функциями, и таким образом эти общеизвестные резуль- таты освещаются по-новому. В гл. II производящие функции рассматриваются более подробно. Здесь важным моментом является введение многочленов Белла, которые используются и в последующих главах. В гл. III содержится подробное изучение принципа включения и исключения, который необходим для перечисления перестановок с ограничениями на позиции, рассматриваемых в гл. VII и VIII. В гл. IV изучаются методы подсчета числа перестановок, пред- ставленных с помощью циклов. Эту главу можно рассматривать как введение в замечательную работу моего друга Жака Тушара. Глава V содержит беглый обзор теории размещений, в которую сделал значительный вклад Мак-Магон. В гл. VI рассматриваются разбиения, композиции и перечисле- ния деревьев и линейных графов. Большая часть материала по линейным графам была подготовлена специально для этой книги и является продолжением работы, выполненной совместно с моими друзьями Фостером и Шенноном. О гл. VII и VIII уже упоминалось. Они посвящены развитию исследований, в начале которых мне посчастливилось сотрудничать с Ирвингом Капланским; продолжению этой работы в большой сте- пени способствовала переписка с Тушаром и Коихи Ямамото; во всем остальном работа проделана мной одним. В каждой главе имеется обширный раздел задач, которые разви- вают положения, приведенные в основном тексте. По мере возможно- сти, задачи ставятся в такой форме, которая помогает читателям. Тем не менее решение этих задач требует определенной математи- ческой зрелости. Что касается обозначений, то я в основном ограничился исполь- 8 Предисловие зованием букв латинского алфавита, в результате чего одна и та же буква иногда оказывается имею-дей несколько различных смыслов. По мере возможности использование одной и той же буквы в различ- ных смыслах разделено достаточными интервалами, а в случаях, когда возможна путаница, делаются специальные оговорки. В пре- делах каждой главы для соотношений, теорем, разделов, примеров и задач избрана сквозная нумерация, и ссылки в пределах главы даются в соответствии [с этой нумерацией. Ссылки же, относящиеся к другой главе, содержат в начале дополнительную цифру, указы- вающую на номер соответствующей главы. Так, например, отсылка к соотношению 3 а из гл. IV дается в пределах этой главы в виде (За), а в гл. VI в виде (4.За). Список литературы дается в конце каждой главы. Для указания объема таблиц часто используются принятые в настоящее время сокращения; так, например, запись п == ==0(1)10 означает, что п пробегает значения О, 1, 2, ..., 10. Я ставил перед собой цель доводить все преобразования до того момента, когда с предельной легкостью можно получить нужный численный результат. Поэтому оказываются оправданными некото- рые алгебраические преобразования, излишние при иных подхо- дах. Некоторые числовые результаты настолько занимательны, что стимулируют изучение их арифметической природы. Поэтому в кни- ге приведены (без доказательств) соответствующие результаты тео- рии чисел. В первый период работы над книгой, 15 лет назад, я состоял в активной переписке с Беккером. Во время интенсивной работы в последние два года, которую мне не удалось бы выполнить без поддержки Б. Мак-Миллана, я воспользовался возможностью изло- жить материал этой книги на двух заседаниях семинара в лабора- тории компании Белл. Е. Гильберт — организатор одного из этих заседаний — оказался настолько любезным, что прочитал весь текст в различных вариантах, а также просмотрел много задач и пополнил их число. Многие улучшения были внесены после прочтения текста Ж. Тушаром и С. Рисом. Всем этим коллегам я приношу искреннюю благодарность. Джон Риордан Лаборатория компании Белл, Нью-Йорк, Февраль 1958 Глава 1 ПЕРЕСТАНОВКИ И СОЧЕТАНИЯ 1. Введение В этой главе собран наиболее простой и чаще всего используемый материал из теории сочетаний. Этот материал излагается в целом ряде учебников по элементарной алгебре, поэтому в настоящей кни- ге изложение его сопровождается лишь самыми необходимыми объ- яснениями и минимальным количеством примеров. Основное внима- ние уделено методам доказательств, которые могут оказаться полез- ными позднее, и введению необходимых понятий и рабочих приемов. Среди этих понятий вводится понятие производящей функции. Это- позволяет провести в весьма общем виде изучение как перестано- вок, так и сочетаний. Подобный метод, как нам представляется, не в достаточной мере известен. В большей части доказательств в той или иной форме использует- ся одно или одновременно два из следующих правил: Правило суммы. Если объект Л может быть выбран т способами,. а объект В другими п способами, то выбор «либо А, либо В» может быть осуществлен m+n способами. Правило произведения. Если объект Л может быть выбран т способами и после каждого из таких выборов объект В в свею оче- редь может быть выбран п способами, то выбор «Л и В» в указанном порядке может быть осуществлен тп способами. Правила эти по своей природе являются определениями, и их скорее нужно понимать, нежели доказывать. Следует заметить, что в первом правиле выборы Л и В являются взаимно исключающими; т. е. нет возможности выбрать оба объекта одновременно (одним и тем же путем). Правило произведения наиболее часто использует- ся в тех случаях, когда порядок выбора не является существен- ным, т. е. когда выборы Л и В оказываются независимыми. Не сле- дует, однако, игнорировать возможность наличия такой зависи- мости. Даем основные определения перестановок и сочетаний: Определение, г-перестановкой из п элементов называется упорядоченная выборка (либо расположение в определенном порядке} г из этих элементов. Оп ределение. г-сочетанием, из п элементов называется выборка г из них без учета порядка. 280 Гл. 8. Перестановки с ограниченными позициями II Проверить таблицу для чисел Л2 gn.r ^\ г N. о 1 2 3 4 5 6 п '•< 1 1 2 1 4 1 3 1 20 48 20 1 4 1 72 603 1168 603 72 ' 38. Показать аналогично предыдущему, что для любого с 1 = Afe, ift-ii -ik+2^ ,(,). •"А, гй- (<•+1)' ==<\й-1-1 +(^+ i)4?ift-i, ('-^у =4V._, +(^+1)л^_,-1+('^2) и, следовательно, что у Л^-^=3 (-^СТ) (^-s У (Карлиц [6]). s=0 ИМЕННОЙ УКАЗАТЕЛЬ Айткен 92 Барнард 23 Белл 30, 45, 49, 142, 179 Бэттен 217 Виман 95, 105 Ворпицкий 259, 279 Герштейн 95, 104, 105 Гильберт 174, 178, 231 Гончаров 95, 101 Гупта 144, 145 Джейкоб 259 Диксон 63, 129, 148, 193 Капланский 214, 217, 234, 248, 260 Карлиц 179, 260, 280 Каттанео 211, 217 Керавала 246, 260 Кёниг 132, 170, 179 Кнёдель 169, 179 Коши 85 Кристалл 23 Кулбек 217 Кэли 141, 142, 151, 152, 165, 179, 231, 237, 260 Лаплас 78 Лах 43 Линделёф 217 Люка 30, 49, 193, 194, 217, 231, 260 Мак-Магон 31, 49, 108, 114, 117, 118, 121, 129, 130, 140, 141, 165, 167, 179, 193 Мендельсон 217, 260 Мозер 95, 105 Монмор 63, 71 Mop 95, 104 Моро 193 Мьюир 231, 260 Нетто 23, 121, 260 Нормам 179 Ньюкомб 195, 231, 253, 254 Олдз 217 Оттер 163, 179 Пойа 106, 107, 151, 152, 153, 156, 170, 179, 191 Риордан 179, 217, 243, 246, 260 Саде 248, 253, 260 Cere 106, 107 Сильвестр 140 Скотт 95, 105 3 Спрейг 260 Тейт 231, 260 Тушар 68, 76, 78, 82, 95, 97, 102, 232, 233, 238, 261 Уилкс 217 Уитворт 23, 73, 121 Уитни 76 Уленбек 179, 189 Феллер 88, 95 Форд 179 Фостер 179 Франклин 138 Фреше76, 217 Харари 174, 179, 187, 189 Харди 49 Херштейн 95, 104, 105 Чайлд 23 Човла 95, 104, 105 Шеннон 179 Шобе 261 Шредер 179 Шрутка 261 Эйлер 16, 50, 74, 129, 140, 195 Эрдейи 203 Эрдёш 248, 260 Якобсталь 95 Ямамото 179, 217, 246, 248, 261. 264, 276 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Анткена треугольная запись 92 Аппеля полиномы 73 Белла полиномы 46, 47, 169 — — таблица 62 Бесселя функция 269 Бернулли числа 57 Биномиальная вероятностная произ- водящая функция 53 Биномиальные коэффициенты 13 — — таблица 14 — моменты 41, 67 Бицентр дерева 160 Бицентроид дерева 160 Блиссара исчисление 30, 38 Борелевское суммирование 40 Бруно формула 48 Вандермонда теорема 18 Вариации 10 Вильсона теорема 97 Встреч числа 73 — — таблица 80 Граф Ферре 130 — зигзагообразный (для компози- ций) 130, 131 Графы 133 — линейные 131 — — число (таблица) 173 — — энумератор 172 — ориентированные 187 — связные 178 — — с одним циклом 175 — — — — — таблица 178 — с параллельными соединениями 190 — с точками, снабженными ярлы- ками 174 Группа диэдра 176, 177 Двоичная система 180 Дельта Кронекера 45 Денумеранты 140 — разложений на простейшие дроби 143 — рекуррентных соотношений 140, 141, 142 Дерево 133 — корневое 133 — ориентированное 152 — раскрашенное 158 — свободное 133 — снабженное ярлыками 158 — с хроматической окраской точек 185 — химическое 191 Деревья корневые, с линиями, снаб- женными ярлыками 185 — — с точками, снабженными ярлы- ками 162 — ориентированные, корневые или свободные, с раскрашенными точ- ками или линиями, хроматиче- скими или снабженными ярлы- ками 186 — с линиями, снабженными ярлы- ками, раскрашенными или хрома- тическими 185 — — раскрашенными точками 185 — — точками, снабженными ярлы- ками 162 — — цветными точками 185 Дисперсия 42 Дурфи квадрат 137 Занятость (occupancy) 109 Задача о встречах (probleme des ren- contres) 71 — — — неполная 199, 225 — — — обобщенная 78 — — гостях (probleme des menages) 195, 231 — — — таблица 233, 234 — — ладьях (problem of the rooks) 196 Предметный указатель 283 Задача о слонах (problem of the- bishops) 258, 259 — Симона Ньюкомба 195, 231, 253, 254, 257, 279 Запас (элементов) (store) 153 Кактусы 189 Класс перестановок 82 Клетки шахматной доски 196 Ковариация (covariance) 43 Композиции (compositions) 129 — граф 130, 131 — не содержащие частей, больших чем s 184 — с заданными частями 148 — — — в определенном порядке частями 148 — содержащие по крайней мере одну часть, равную s 184 — сопряженные 131 — cm нечетными частями 148 — — — частями, каждая из кото- рых не превышает s 148, 183 Кош и алгебра 30, 34 — тождество 85 Лагерра полиномы 57, 203, 209 Лагранжа тождество — сравнение 97 Ладейный многочлен (rook polyno- mial) 197 — — дополнения в прямоугольнике 212 — — квадрата 217 — — лестницы 219 — — наибольший 216 — — прямоугольника 202 — — таблицы для связных досок 229, 230 — — трапеции 248 — — треугольника 250 — — трехслойной лестницы 271, 272 — — усеченной трапеции 276 — — Х-образной доски 268 Лапласа преобразование 32 Латинские квадраты 248 — прямоугольники 195 — — с двумя строками 195 — — — k строками 248 — — трехстрочные 241 — — — таблица 247 Лаха числа 56 Лежандра полиномы 227 Лестница (staircase) 195 Лотерея 79 Момент биномиальный 41 Момент, производящая функция 42 — факториальный 41 — центральный (среднего значения 41 Неопределенный знак (indetermi- nate) 30 Ожерелья (necklaces) 192 Оператор разностный (Д) 22 — смещения (Е) 22 — сумм (5) 35 — 6=tD 36 Определители 58, 106, 221 Парные карты (cardmatching) 71, 207 — — колоды спецификации pq 208, 227 — — — — (а5) 210, 227 — — — — 2"1 220 — — — — pq...va 228 — — образование по достоинству 208 — — — — масти 208 Паскаля треугольник 14 Перестановки (permutations) 9, 10 — без единичных циклов 88 — нечетные 94, 95, 105 — производящая функция 20, 21 — противоречивые (discordant) двум данным перестановкам 238, 240, 241 — — — трем данным перестанов- кам 272 — различных элементов 10 — с неограниченными повторениями 12, 156 — — повторениями, в которых два соседних элемента различны 27, 28 — — — — — три соседних эле- мента различны 28 — — — — — т соседних элемен- тов различны 28 — циклы 81 — четные 94, 95, 105 Перманент (permanent) 218 Петля (sling) 132 Подъем (ascending runs) перестановок 252, 255 Пойа теорема 153 Полиномиальный коэффициент 12 Попаданий многочлен (hit polyno- mial) 197 Правило произведения 9, 155 — суммы 9 Преобразования перестановок 176 Предметный указатель Принцип включения и исключения 63 — перекрестной классификации 63 Производящая функция (generating function) для моментов 41 — — — — биномиальных 41 — — — — факториальных 41 — — — — центральных 43 — — кумулянтная 48 — — обратная 35, 39 — — обычная 29, 42 — — перестановок 20, 21 — — симметрических функций 32 — — со многими переменными 32 — — сочетаний 16, 17 — — экспоненциальная 29 Простой цикл 141 Пуанкаре теорема 65 Разбиение (partition) 129 — граф 130 Разбиения, все части которых не превосходят k 134 — — — — различны 134 — не более чем с k частями 135 — общее число 145 — перечисляющая производящая функция 133 — самосопряженные 137 — совершенные 146, 147 — с различными нечетными частями 182 — таблица по числу частей 130 — только с нечетными частями 134 — точно с k частями 135 — — — — — и максимальной ча- стью / 181 Размен монет 180 Размещение (distribution) 109 — при одинаковых ячейках 119 — — — — таблица 120 — — — элементах и различных ячейках 111 — — отсутствии пустых ячеек 110, 121 — — различных элементах и ячей- ках 109 — — упорядочении 118 — элементов любой спецификации 113, 114, 123, 124, 125 Разности нуля 22, 25, 110 Ранг 70 Решета метод 63 Свертка 34 Сети 131 Сети последовательно- параллельные 166 — — — существенно-параллельные 167 — — — — последовательные 167 — снабженные ярлыками 169 — с с расцветками 189 Символический метод 63 Символическое исчисление 30 Симметрические функции, сумма од- нородных произведений 60, 112 — — — степеней 60 — — элементарные 17, 60 Сложная функция (composite func- tion) 45, 46 Совершенное подразбиение 146, 147 Совпадения, попадания и выборки (coincidences, hits, matches) 72 Сопряженные перестановки 252 — разбиения 130 Сочетания (combinations) 9 — по меньшей мере с одним повторе- нием элемента каждого вида 19 — производящие функции 16 — различных элементов 13 — с ограниченным числом повторе- ний 19, 20 — — четным числом повторений 19, 20 — элементов спецификации pi'7 25 _ _ _ s"1 25 _ _ _ gm]n-2in gg Спады (descents) перестановок 252, 255 Спецификация элементов 10 Стильтьеса интеграл 32 Стирлинга числа 43 — — (второго рода), связь с разме- щением 110, 111, 119 — — обобщенные 45 — — (первого рода), делимость 97 — — присоединенные 88, 93 — — производящая функция 54, 55 — — связь с задачей о ладьях 251 — — — — перестановками без еди- ничных циклов 88, 95 — — — — — из k циклов 86, 91 — — — — числами Бернулли 57, 58 — — таблица 61 Субфакториал 73 Телефонная станция 102 Терквема задача 27 Трапеция 248 — усеченная 276 Предметный указатель Факториал 11 — возрастающий 18 — убывающий 11, 18 Факторизация чисел 119 Ферре граф 130 Фибоначчи числа 24, 27, 183, 275 —Фигурные числа 35 Центр дерева 150 Центроид дерева 150 Цикл графа 132 Цикловой индекс (cycle index) 154 — индикатор (cycle indicator) 83 Цикловые индексы группы диэдра 177 — — линейного графа 171, 172 — — ориентированного линейного графа 187 — — — полигона 188 — — связного графа с двумя цик- лами 188 — — симметрической группы 154 Цикловые индикаторы всех переста- новок 83 — — — — таблица 84 — — нечетных перестановок 94, 95 — — с упорядоченными циклами 91 — — перестановок с k г-циклами 98 — — — с / г-циклами и k s-цик- лами 101 — — четных перестановок 94, 95 Циклы перестановок индекс 154 — — классы 82 — — характер 90 Циклы перестановок, цикловой инди- катор 83 Чебышева полиномы 239, 262, 263, 269 Числа встреч 80 Чтения (readings) 252 Шахматная доска 196 — — дополнение к ней 211 Эйлера преобразование рядов 70 — тождество 139 — функция 76 — числа 50, 253, 254 — — в связи с треугольными пе- рестановками 254 — — таблица 254 Эквивалентность клеток шахматных досок 216, 219 — шахматных досок •213, 214 Энумератор (enumerator) 17 — деревьев корневых с точками, снабженными ярлыками 158 — — — с одинаковыми точками 151 — — — с раскрашенными точками 184 — — — — хроматическими точ- ками 185 Эрмита полиномы 60, 103 Ячейки (cells) в задачах о размеще- ниях 109 ОГЛАВЛЕНИЕ Глава 1. Перестановки и сочетания 1. Введение ........................ 2. г-перестановки ..................... 2.1. Различные предметы (элементы) .......... 2.2. Число перестановок из п объектов, из которых р при- надлежат одному виду, q другому и т. д. ...... 2.3. /--перестановки с неограниченными повторениями . . . 3. Сочетания ....................... 3.1. г-сочетания из п различных элементов ........ 3.2. Сочетания с повторениями ............. 4. Производящие функции для сочетаний .......... 5. Производящие функции для перестановок ........ Литература ...................... Задачи*. ......................... Глава 2. Производящие функции 1. Введение ........................ 2. Элементарные соотношения между обычными производящими функциями ....................... 3. Решение линейных рекуррентных уравнений ....... 4. Экспоненциальные производящие функции ........ 5. Соотношения между обычными и экспоненциальными произ- водящими функциями .................. 6. Производящие функции для моментов .......... 7. Числа Стирлинга .................... 8. Производные сложных функций ............. Литература ...................... Задачи .......................... Глава 3. Принцип включения и исключения 1. Введение ............. 2. Логическое тождество ....... 3. Символическое обобщение ..... 4. Ранг ............... 5. Задача о встречах ......... Литература............ Задачи ...........'.... Глава 4. Циклы перестановок ......... 1. Введение ............... 2. Цикловые классы ........... 3. Перестановки с заданным числом циклов 4. Перестановки без единичных циклов . 5. Перечисление по характеристике цикла 6. Циклы четных и нечетных перестановок Литература ............ Задачи ............... Оглавление Рлава б. Размещения, занятость . . ........... 1. Введение .................... 2. Различные объекты и ячейки .......... 3. Одинаковые объекты и различные ячейки .... 4. Объекты любой спецификации и различные ячейки 5. Упорядоченные размещения ........... 6. Одинаковые ячейки ............... Литература .................. Задачи ...................... Глава 6. Разбиения, композиции, деревья и сети . . 1. Введение ................ 2. Производящие функции для разбиений . . 3. Приложение графа Ферре ........ 4. Денумерант ............... 5. Совершенные разбиения ......... 6. Композиции ............... 7. Подсчет числа корневых деревьев .... 8. Теорема Пойа . . ............ 9. Деревья ................. 10. Последовательно-параллельные сети .... 11. Линейные графы ............. 12. Связные графы с одним циклом ..... Литература .............. Задачи ................... Глава 7. Перестановки с ограниченными позициями I 1. Введение ................. 2. Задача о ладьях ............. 3. Свойства ладейных многочленов ...... 4. Прямоугольные доски ........... 5. Парные карты ............. 6. Парные карты. Аппроксимация ...... 7. Дополнения ............... 8. Эквивалентность ............. Литература ............... Задачи ................... Глава 8. Перестановки с ограниченными позициями II ....... 1. Введение ................. 2. Задача о гостях ............ 3. Перестановки, противоречивые двум заданным переста- новкам ......... 4. Латинские прямоугольники ........ '. . . . '. ' 5. Трапеции и треугольники .............. 6. Треугольные перестановки . . ..........'.'. 7. Задача Симона Ньюкомба .............' 8. Задача о слонах ........... Литература ............. Задачи .......... Д. Риордан ВВЕДЕНИЕ В КОМБИНАТОРНЫЙ АНАЛИЗ Редактор И, Л. Никольская Художник В. М. Новоселова Технический редактор 3. Д. Горькош Сдано в производство 19/V 1962 г. Подписано к печати 14/IX 1962 г. Бумага 60x9(Jl/ie=9,0 бум. л. 18,0печ. л. Уч.-изд. л. 15,3 Изд. № 1/0128. Цена 1 р. 27 к. Зак. 273 ИЗДАТЕЛЬСТВО ИНОСТРАННОЙ ЛИТЕРАТУРЫ Москва, 1-й Рижский пер., 2 Московская типография № 5 Мосгорсовнархоза Москва, Трехпрудный пер., 9