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

Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. - М., 2006. - 400 с.
В книге в популярной форме рассказывается о комбинаторике, методах решения комбинаторных задач, о рекуррентных соотношениях и производящих функциях. Материал частично захватывает области, выходящие за рамки элементарной математики, однако изложение доступно хорошему ученику средней школы. Книга содержит более 400 упражнений.
Книга будет полезна школьникам старших классов, интересующимся математикой, учителям, студентам первых курсов математических факультетов университетов и пединститутов, а также всем, сталкивающимся в своей практической работе с комбинаторными задачами.
Из предисловия: Основой книги являются две книги Н. Я. Виленкина: «Комбинаторика» (М., 1969) и «Популярная комбинаторика» (М., 1975) В конце 80-х годов Наум Яковлевич начал работать над новой книгой, в которую должен был войти материал обеих книг и решения задач ... Завершать эту работу пришлось потомкам.
В этой книге сохранен (а где-то восстановлен) неформальный стиль изложения первой книги. Большинство понятий введено в связи с конкретными задачами. Однако эти задачи подобраны так, чтобы они оставляли ясной математическую суть дела. Для некоторых вопросов найдены новые, более простые решения. Задачи для самостоятельного решения собраны из обеих книг, распределены по главам и почти все снабжены ответами или указаниями.
ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ.......................................................................7
ГЛАВА I
ОБЩИЕ ПРАВИЛА КОМБИНАТОРИКИ ......................................9
1. Суеверный председатель ..................................................9
2. Лото .......................................10
3. Команда космического корабля ....................11
4. Правила суммы и произведения ...................12
5. Размещения с повторениями......................18
6. Секретный замок ..............................18
7. Системы счисления и передача информации ..........19
8. Вокруг ЭВМ..................................20
9. Морской семафор ..............................22
10. Точки—тире телеграфные .......................22
11. Задачи о шашках.............................26
12. Сколько человек не знают иностранных языков? ......27
13. Формула включений и исключений ................29
14. Анализ отчета ...............................31
15. Решето Эратосфена ............................32
16. Проблемы комбинаторики .......................34
17. Множества и кортежи..........................36
Глава II
РАЗМЕЩЕНИЯ, ПЕРЕСТАНОВКИ И СОЧЕТАНИЯ......................40
18. Первенство по футболу .........................40
19. Размещения без повторений .....................41
20. Перестановки ................................43
21. Лингвистические проблемы ......................45
22. Перестановки с повторениями ....................46
23. Сочетания без повторений.......................49
24. Бином Ньютона ..............................52
25. Покупка пирожных ...........................54
26. Сочетания с повторениями ......................56
27. Генуэзская лотерея ............................58
28. «Спортлото» .................................61
29. Снова футбольное первенство.....................63
30. Перестановки с ограничениями ...................63
31. Постройка лестницы...........................65
32. Рыцари короля Артура.........................67
33. Свойства сочетаний............................70
34. Частный случай формулы включений и исключений ... 79
35. Знакопеременные суммы сочетаний ................80
Глава III
РАСКЛАДКИ ......................................... 90
36. Шары и лузы................................90
37. Сбор яблок..................................91
38. Букет цветов и сбор грибов......................93
39. Задача о числе делителей .......................94
40. Домино и преферанс...........................95
41. Раскладка по ящикам..........................97
42. Сушка грибов................................98
43. Разные статистики ............................99
44. Распределение нагрузки ........................101
45. Посылка фотографий ..........................102
46. Числа Стирлинга .............................ЮЗ
47. Комбинаторика классификаций ...................104
48. Флаги на мачтах .............................105
49. Полное число сигналов .........................107
50. Общая задача о ладьях.........................108
51. Симметричные расстановки ......................109
52. Восемь ферзей ...............................112
53. Вся королевская конница.........................113
54. Два коня ...................................115
Глава IV
РАЗБИЕНИЯ .........................................120
55. Задача о наклейке марок .......................120
56. Разбиение чисел на слагаемые....................122
57. Жетоны в мешке .............................123
58. m-арифметический треугольник ...................124
59. Счастливые троллейбусные билеты.................126
60. Некоторые свойства чисел Cm(n,N) ................128
61. Проблема абитуриента..........................130
62. Уплата денег ................................130
63. Покупка конфет ..............................132
64. Как разменять гривенник? ......................133
65. Диаграммная техника..........................135
66. Двойственные диаграммы .......................137
67. Формула Эйлера..............................138
Глава V
СМЕЩЕНИЯ, СУБФАКТОРИАЛЫ И ЗАПРЕТНЫЕ ЗОНЫ.....144
68. Девушка спешит на свидание ....................144
69. Сеанс телепатии ..............................146
70. Общая задача о смещении.......................148
71. Субфакториалы...............................149
72. Запретные зоны и ладейные числа ................151
73. Общая формула ..............................152
74. За обеденным столом ..........................154
75. Диаграммы Юнга .............................156
76. Караван в пустыне ............................158
77. Катание на карусели ..........................160
78. Затруднение мажордома ........................161
Глава VI
БЛУЖДАНИЯ, ФИГУРНЫЕ ЧИСЛА И ОБОБЩЕНИЯ БИНОМИАЛЬНЫХ КОЭФФИЦИЕНТОВ....................165
79. Человек бродит по городу.......................165
80. Броуновское движение .........................166
81. Блуждания и свойства сочетаний .................168
82. Очередь в кассу ..............................170
83. Задача о двух шеренгах ........................175
84. Очереди и свойства сочетаний....................177
85. У Шемаханской царицы ........................178
86. Поглощающая стенка и игры на разорение ..........181
87. Блуждания по бесконечной плоскости ..............181
88. Арифметический квадрат .......................183
89. Фигурные числа..............................184
90. Расширенный арифметический треугольник ..........185
91. Шашка в углу ...............................188
92. Арифметический пятиугольник ...................189
Глава VII
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ .......................194
93. Снова перестановки без повторений ................194
94. Кролики Фибоначчи ...........................195
95. Разбиения фигур .............................198
96. Расстановка скобок............................200
97. Задача о непересекающихся хордах................202
98. Новое решение задачи мажордома.................203
99. Рекуррентные таблицы .........................207
100. Третье решение проблемы мажордома .............207
101. Решение рекуррентных соотношений ..............209
102. Случай постоянных коэффициентов ...............211
103. Случай равных корней характеристического уравнения .214
104. Рекуррентные соотношения и передача информации . . .216
Глава VIII
РЯДЫ И ПРОИЗВОДЯЩИЕ ФУНКЦИИ ...................217
105. Деление многочленов..........................217
106. Алгебраические дроби и степенные ряды ...........218
107. Действия над степенными рядами ................222
108. Применение степенных рядов для доказательства тождеств ............225
109. Производящие функции .......................226
110. Производящие функции и биномиальные коэффициенты ..................227
111. Дробные предметы ...........................229
112. Ряд Ньютона ...............................230
113. Извлечение квадратных корней ..................233
114. Производящие функции и рекуррентные соотношения .236
115. Разложение на элементарные дроби ...............237
116. Производящие функции и задача о разбиениях ......240
117. Полиномиальная формула ......................241
118. Производящие функции и разбиения чисел .........245
119. Производящие функции и наборы гирь ............251
Глава IX
КОМБИНАТОРИКА ОРБИТ .............................257
120. Преобразования и орбиты ......................257
121. Хоровод ...................................258
122. Раскраска куба..............................259
123. Черно-белый квадрат..........................259
124. Орбиты и группы преобразований ................261
125. Неподвижные элементы........................262
126. Черно-белый куб.............................263
127. Сопряжение и циклы .........................265
Глава X
ВОЗМОЖНОЕ И НЕВОЗМОЖНОЕ В КОМБИНАТОРИКЕ ......271
128. Магические квадраты .........................271
129. Офицерское каре.............................275
130. Посев пшеницы .............................277
131. Принцип Дирихле............................278
132. Научная переписка ...........................280
133. Выбор представителей .........................281
134. Графическое решение .........................284
135. Прерывания IRQ.............................286
136. Общие представители .........................287
137. Игра в 15..................................288
138. Острова и мосты.............................291
139. Кругосветное путешествие ......................292
140. Четыре краски ..............................294
141. Код Хемминга ..............................294
Глава XI
ИЗ ИСТОРИИ КОМБИНАТОРИКИ И ЕЕ ПРИЛОЖЕНИЙ .....304
142. Дела давно минувших дней......................304
143. Таинственная черепаха ........................305
144. Комбинаторика в Древней Греции ................306
145. Мистики, астрологи, каббалисты .................308
146. Комбинаторика и схоластики....................309
147. Комбинаторика в странах Востока ................310
148. Liber Abaci.................................311
149. Игра в кости ...............................312
150. Игрок и ученые .............................314
151. Новая ветвь математики .......................315
152. Комбинаторика и шифры ......................316
153. Анаграммы.................................317
154. Иероглифы и клинопись .......................319
155. Комбинаторика в биологии .....................321
156. Модель ДНК................................322
157. Генетический код ............................323
158. Химический пасьянс ..........................327
159. Комбинаторика эпохи компьютеров ...............328
ОТВЕТЫ............................................. 329

Created using FlowPaper Flipbook Maker ↗