Комбинаторика, Виленкин Н.Я., Виленкин А.Н., Виленкин П.А., 2006

Комбинаторика, Виленкин Н.Я., Виленкин А.Н., Виленкин П.А., 2006.
В книге в популярной форме рассказывается о комбинаторике, методах решения комбинаторных задач, о рекуррентных соотношениях и производящих функциях. Материал частично захватывает области, выходящие за рамки элементарной математики, однако изложение доступно хорошему ученику средней школы. Книга содержит более 400 упражнений.
Книга будет полезна школьникам старших классов, интересующимся математикой, учителям, студентам первых курсов математических факультетов университетов и пединститутов, а также всем, сталкивающимся в своей практической работе с комбинаторными задачами.
4. Правила суммы и произведения.
Как мы увидим дальше, комбинаторные задачи бывают самых разных видов. Но большинство задач решается с помощью двух основных правил — правила суммы и правила произведения.
Правило суммы. Если на блюде лежат три яблока, то выбрать одно яблоко можно тремя способами (взять одно из трех яблок). Если на другом блюде лежат две груши, то выбрать одну грушу можно двумя способами (взять одну из двух груш). А выбрать один фрукт можно пятью способами
(выбирая из пяти фруктов — трех яблок и двух груш). Это и есть правило суммы, которое можно сформулировать так.

ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ.
ГЛАВА I ОБЩИЕ ПРАВИЛА КОМБИНАТОРИКИ.
1. Суеверный председатель.
2. Лото.
3. Команда космического корабля.
4. Правила суммы и произведения.
5. Размещения с повторениями.
6. Секретный замок.
7. Системы счисления и передача информации.
8. Вокруг ЭВМ.
9. Морской семафор.
10. Точки-тире телеграфные.
11. Задачи о шашках.
12. Сколько человек не знают иностранных языков?
13. Формула включений и исключений.
14. Анализ отчета.
15. Решето Эратосфена.
16. Проблемы комбинаторики.
17. Множества и кортежи.
Глава II РАЗМЕЩЕНИЯ, ПЕРЕСТАНОВКИ И СОЧЕТАНИЯ.
18. Первенство по футболу.
19. Размещения без повторений.
20. Перестановки.
21. Лингвистические проблемы.
22. Перестановки с повторениями.
23. Сочетания без повторений.
24. Бином Ньютона.
25. Покупка пирожных.
26. Сочетания с повторениями.
27. Генуэзская лотерея.
28. «Спортлото».
29. Снова футбольное первенство.
30. Перестановки с ограничениями.
31. Постройка лестницы.
32. Рыцари короля Артура.
33. Свойства сочетаний.
34. Частный случай формулы включений и исключений
35. Знакопеременные суммы сочетаний.
Глава III РАСКЛАДКИ.
36. Шары и лузы.
37. Сбор яблок.
38. Букет цветов и сбор грибов.
39. Задача о числе делителей.
40. Домино и преферанс.
41. Раскладка по ящикам.
42. Сушка грибов.
43. Разные статистики.
44. Распределение нагрузки.
45. Посылка фотографий.
46. Числа Стирлинга.
47. Комбинаторика классификаций.
48. Флаги на мачтах.
49. Полное число сигналов.
50. Общая задача о ладьях.
51. Симметричные расстановки.
52. Восемь ферзей.
53. Вся королевская конница.
54. Два коня.
Глава IV РАЗБИЕНИЯ.
55. Задача о наклейке марок.
56. Разбиение чисел на слагаемые.
57. Жетоны в мешке.
58. m-арифметический треугольник.
59. Счастливые троллейбусные билеты.
60. Некоторые свойства чисел Ст(п* N).
61. Проблема абитуриента.
62. Уплата денег.
63. Покупка конфет.
64. Как разменять гривенник?.
65. Диаграммная техника.
66. Двойственные диаграммы.
67. Формула Эйлера.
Глава V СМЕЩЕНИЯ, СУБФАКТОРИАЛЫ И ЗАПРЕТНЫЕ ЗОНЫ
68. Девушка спешит на свидание.
69. Сеанс телепатии.
70. Общая задача о смещении.
71. Субфакториалы.
72. Запретные зоны и ладейные числа.
73. Общая формула.
74. За обеденным столом.
75. Диаграммы Юнга.
76. Караван в пустыне.
77. Катание на карусели.
78. Затруднение мажордома.
Глава VI БЛУЖДАНИЯ, ФИГУРНЫЕ ЧИСЛА И ОБОБЩЕНИЯ БИНОМИАЛЬНЫХ КОЭФФИЦИЕНТОВ.
79. Человек бродит по городу.
80. Броуновское движение.
81. Блуждания и свойства сочетаний.
82. Очередь в кассу.
83. Задача о двух шеренгах.
84. Очереди и свойства сочетаний.
85. У Шемаханской царицы.
86. Поглощающая стенка и игры на разорение.
87. Блуждания по бесконечной плоскости.
88. Арифметический квадрат.
89. Фигурные числа.
90. Расширенный арифметический треугольник.
91. Шашка в углу.
92. Арифметический пятиугольник.
Глава VII РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ.
93. Снова перестановки без повторений.
94. Кролики Фибоначчи.
95. Разбиения фигур.
96. Расстановка скобок.
97. Задача о непересекающихся хордах.
98. Новое решение задачи мажордома.
99. Рекуррентные таблицы.
100. Третье решение проблемы мажордома.
101. Решение рекуррентных соотношений.
102. Случай постоянных коэффициентов.
103. Случай равных корней характеристического уравнения
104. Рекуррентные соотношения и передача информации.
Глава VIII РЯДЫ И ПРОИЗВОДЯЩИЕ ФУНКЦИИ.
105. Деление многочленов.
106. Алгебраические дроби и степенные ряды.
107. Действия над степенными рядами.
108. Применение степенных рядов для доказательства тождеств.
109. Производящие функции.
110. Производящие функции и биномиальные коэффициенты.
111. Дробные предметы.
112. Ряд Ньютона.
113. Извлечение квадратных корней.
114. Производящие функции и рекуррентные соотношения
115. Разложение на элементарные дроби.
116. Производящие функции и задача о разбиениях.
117. Полиномиальная формула.
118. Производящие функции и разбиения чисел.
119. Производящие функции и наборы гирь.
Глава IX КОМБИНАТОРИКА ОРБИТ.
120. Преобразования и орбиты.
121. Хоровод.
122. Раскраска куба.
123. Черно-белый квадрат.
124. Орбиты и группы преобразований.
125. Неподвижные элементы.
126. Черно-белый куб.
127. Сопряжение и циклы.
Глава X ВОЗМОЖНОЕ И НЕВОЗМОЖНОЕ В КОМБИНАТОРИКЕ.
128. Магические квадраты.
129. Офицерское каре.
130. Посев пшеницы.
131. Принцип Дирихле.
132. Научная переписка.
133. Выбор представителей.
134. Графическое решение.
135. Прерывания IRQ.
136. Общие представители.
137. Игра в 15.
138. Острова и мосты.
139. Кругосветное путешествие.
140. Четыре краски.
141. Код Хемминга.
Глава XI ИЗ ИСТОРИИ КОМБИНАТОРИКИ И ЕЕ ПРИЛОЖЕНИЙ
142. Дела давно минувших дней.
143. Таинственная черепаха.
144. Комбинаторика в Древней Греции.
145. Мистики, астрологи, каббалисты.
146. Комбинаторика и схоластики.
147. Комбинаторика в странах Востока.
148. Liber Abaci.
149. Игра в кости.
150. Игрок и ученые.
151. Новая ветвь математики.
152. Комбинаторика и шифры.
153. Анаграммы.
154. Иероглифы и клинопись.
155. Комбинаторика в биологии.
156. Модель ДНК.
157. Генетический код.
158. Химический пасьянс.
159. Комбинаторика эпохи компьютеров.
ОТВЕТЫ.