Комбинаторика. Виленкин Н. Книга: Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин «Комбинаторика
Комбинаторика . Виленкин Н.Я.
М.: Наука. Гл. ред. физ.-мат. лит., 1969.- 323 с.
В предлагаемой вниманию читателя книге о комбинаторных проблемах рассказывается в занимательной, популярной форме. Тем не менее в ней разбираются и некоторые довольно сложные комбинаторные задачи, дается понятие о методах рекуррентных соотношений и производящих функций.
Первая глава книги посвящена общим правилам комбинаторики- правилам суммы и произведения. Во второй главе изучаются размещения, перестановки и сочетания. Этот традиционный школьный материал сопровождается разбором некоторых занимательных примеров. В главе III мы изучаем комбинаторные задачи, в которых на рассматриваемые комбинации налагаются те или иные ограничения. В главе IV рассмотрены задачи на разбиения чисел и рассказано о геометрических методах в комбинаторике. Глава V посвящена задачам о случайных блужданиях и различным модификациям арифметического треугольника. В главе VI рассказано о рекуррентных соотношениях, а в главе VII - о производящих функциях, и в частности о биномиальной формуле.
К книге приложено несколько сотен задач по
комбинаторике, взятых автором из различных источников. Много задач заимствовано
из книги Уитворта «Выбор и случай» (Whitworth W. A., Choice and Chance, London,
1901), упомянутой книги Риордана, книги А. М. Яглома и И. М. Яглома
«Неэлементарные задачи в элементарном изложении», Гостехиздат, 1954, различных
сборников задач математических олимпиад и т. д.
Формат: djvu / zip
Размер: 2 ,6 Мб
/ Download
файл
Оглавление
Предисловие
Глава I. Общие правила комбинаторики 9
Суеверные велосипедисты 9
Размещения с повторениями J0
Системы счисления
Секретный замок
Код Морзе
Морской семафор 15
Электронная цифровая вычислительная машина. 15
Генетический код 16
Общие правила комбинаторики 17
Задача о домино 19
Команда космического корабля 20
Задачи о шашках 21
Сколько человек не знают иностранных языков? ... .24
Формула включений и исключений 25
В чем ошибка? 27
Решето Эратосфеиа 28
Гл а в а II. Размещения, перестановки и сочетания 31
Футбольное первенство 31
Размещения без повторений 32
Научное общество 33
Перестановки 33
Задача о ладьях 34
Лингвистические проблемы 35
Хоровод 36
Перестановки с повторениями 37
Анаграммы 39
Сочетания 41
Генуэзская лотерея. . . , 44
Покупка пирожных 47
Сочетания с повторениями 49
Снова футбольное первенство 51
Свойства сочетаний 52
Частный случай формулы включений и исключений. . 59
Знакопеременные суммы сочетаний 59
Глава III. Комбинаторные задачи с ограничениями 63
Львы и тигры 63
Постройка лестницы 64
Книжная полка 65
Рыцари короля Артура 66
Девушка спешит на свидание 67
Сеанс телепатии 70
Общая задача о смещении 73
Субфакториалы 74
Караван в пустыне 76
Катание на карусели 79
Очередь в кассу 80
Задача о двух шеренгах 85
Новые свойства сочетаний 86
Глава IV. Комбинаторика разбиений 90
Игра в домино 91
Раскладка по ящикам 92
Букет цветов 93
Задача о числе делителей 94
Сбор яблок 95
Сбор грибов, 96
Посылка фотографий 96
Флаги на мачтах 98
Полное число сигналов 99
Разные статистики 100
Разбиения чисел 101
Отправка бандероли 101
Общая задача о наклейке марок. 103
Комбинаторные задачи теории информации 104
Проблема абитуриента 105
Уплата денег 107
Покупка конфет 108
Как разменять гривенник? ПО
Разбиение чисел на слагаемые 112
Диаграммная техника 113
Двойственные диаграммы 115
Формула Эйлера 116
Глава V. Комбинаторика на шахматной доске 121
Человек бродит по городу 121
Арифметический квадрат 122
Фигурные числа 123
Арифметический треугольник 125
Расширенный арифметический треугольник 126
Шахматный король 128
Обобщенный арифметический треугольник. . 129
Обобщенные арифметические треугольники и m-ичная система счисления 131
Некоторые свойства чисел Cm(k,n) 131
Шашка в углу 133
Арифметический пятиугольник.135
Геометрический способ доказательства свойств сочетаний 137
Случайные блуждания
Броуновское движение
У Шемаханской царицы
Поглощающая стенка
Блуждания по бесконечной плоскости 14о
Общая задача о ладьях 147
Симметричные расстановки
Два коня 151
Глава VI. Рекуррентные соотношения 154
Числа Фибоначчи 135
Другой метод доказательства 158
Процесс последовательных разбиений 159
Умножение и деление чисел 161
Задачи о многоугольниках... 163
Затруднение мажордома 165
Счастливые троллейбусные билеты 169
Рекуррентные таблицы 170
Другое решение проблемы мажордома.. 172
Решение рекуррентных соотношений 174
Линейные рекуррентные соотношения с постоянными коэффициентами. 175
Случай равных корней характеристического уравнения 178
Третье решение задачи мажордома 180
Глава VII. Комбинаторика и ряды 182
Деление многочленов 182
Алгебраические дроби и степенные ряды 183
Действия над степенными рядами 187
Применение степенных рядов для доказательства тождеств 190
Производящие функции 191
Бином Ньютона 192
Полиномиальная формула 195
Ряд Ньютона 199
Извлечение квадратных корней 202
Производящие функции и рекуррентные соотношения. . 205
Разложение на элементарные дроби 217
Об едином нелинейном рекуррентном соотношении.219
Производящие функции и разбиения чисел 212
Сводка результатов по комбинаторике разбиений.... 216
Задачи по комбинаторике.... 219
Решения и ответы 255
М.: ФИМА, МЦНМО, 2006. — 400 с.Основой книги являются две книги Н.Я.Виленкина: «Комбинаторика» (М., 1969) и «Популярная комбинаторика» (М., 1975). В конце 80-х годов Наум Яковлевич начал работать над новой книгой, в которую должен был войти материал обеих книг и решения задач. Завершать эту работу пришлось потомкам.В этой книге сохранен (а где-то восстановлен) неформальный стиль изложения первой книги. Большинство понятий введено в связи с конкретными задачами. Однако эти задачи подобраны так, чтобы они оставляли ясной математическую суть дела. Для некоторых вопросов найдены новые, более простые решения. Задачи для самостоятельного решения (более 400 упражнений) собраны из обеих книг, распределены по главам и почти все снабжены ответами или указаниями.В книге в популярной форме рассказывается о комбинаторике, методах решения комбинаторных задач, о рекуррентных соотношениях и производящих функциях. Материал частично захватывает области, выходящие за рамки элементарной математики, однако изложение доступно хорошему ученику средней школы.Книга будет полезна школьникам старших классов, интересующимся математикой, учителям, студентам первых курсов математических факультетов университетов и пединститутов, а также всем, сталкивающимся в своей практической работе с комбинаторными задачами.Содержание
:
Общие правила комбинаторики
.
Суеверный председатель.
Лото.
Команда космического корабля.
Правила суммы и произведения.
Размещения с повторениями.
Секретный замок.
Системы счисления и передача информации.
Вокруг ЭВМ.
Морской семафор.
Точки—тире телеграфные.
Задачи о шашках.
Сколько человек не знают иностранных языков?
Формула включений и исключений.
Анализ отчета.
Решето Эратосфена.
Проблемы комбинаторики.
Множества и кортежи.
Размещения, перестановки и сочетания
.
Первенство по футболу.
Размещения без повторений.
Перестановки.
Лингвистические проблемы.
Перестановки с повторениями.
Сочетания без повторений.
Бином Ньютона.
Покупка пирожных.
Сочетания с повторениями.
Генуэзская лотерея.
«Спортлото».
Снова футбольное первенство.
Перестановки с ограничениями.
Постройка лестницы.
Рыцари короля Артура.
Свойства сочетаний.
Частный случай формулы включений и исключений.
Знакопеременные суммы сочетаний.
Раскладки
.
Шары и лузы.
Сбор яблок.
Букет цветов и сбор грибов.
Задача о числе делителей.
Домино и преферанс.
Раскладка по ящикам.
Сушка грибов.
Разные статистики.
Распределение нагрузки.
Посылка фотографий.
Числа Стирлинга.
Комбинаторика классификаций.
Флаги на мачтах.
Полное число сигналов.
Общая задача о ладьях.
Симметричные расстановки.
Восемь ферзей.
Вся королевская конница.
Два коня.
Разбиения
.
Задача о наклейке марок.
Разбиение чисел на слагаемые.
Жетоны в мешке.
тп-арифметический треугольник.
Счастливые троллейбусные билеты.
Некоторые свойства чисел.
Проблема абитуриента.
Уплата денег.
Покупка конфет.
Как разменять гривенник?
Диаграммная техника.
Двойственные диаграммы.
Формула Эйлера.
Смещения, субфакториалы и запретные зоны
.
Девушка спешит на свидание.
Сеанс телепатии.
Общая задача о смещении.
Субфакториалы.
Запретные зоны и ладейные числа.
Общая формула.
За обеденным столом.
Диаграммы Юнга.
Караван в пустыне.
Катание на карусели.
Затруднение мажордома.
Блуждания, фигурные числа и обобщения биномиальных коэыыициентов
.
Человек бродит по городу.
Броуновское движение.
Блуждания и свойства сочетаний.
Очередь в кассу.
Задача о двух шеренгах.
Очереди и свойства сочетаний.
У Шемаханской царицы.
Поглощающая стенка и игры на разорение.
Блуждания по бесконечной плоскости.
Арифметический квадрат.
Фигурные числа.
Расширенный арифметический треугольник.
Шашка в углу.
Арифметический пятиугольник.
Рекуррентные соотношения
.
Снова перестановки без повторений.
Кролики Фибоначчи.
Разбиения фигур.
Расстановка скобок.
Задача о непересекающихся хордах.
Новое решение задачи мажордома.
Рекуррентные таблицы.
Третье решение проблемы мажордома.
Решение рекуррентных соотношений.
Случай постоянных коэффициентов.
Случай равных корней характеристического уравнения.
Рекуррентные соотношения и передача информации.
Ряды и производящие фуекции
.
Деление многочленов.
Алгебраические дроби и степенные ряды.
Действия над степенными рядами.
Применение степенных рядов для доказательства тождеств.
Производящие функции.
Производящие функции и биномиальные коэффициенты.
Дробные предметы.
Ряд Ньютона.
Извлечение квадратных корней.
Производящие функции и рекуррентные соотношения.
Разложение на элементарные дроби.
Производящие функции и задача о разбиениях.
Полиномиальная формула.
Производящие функции и разбиения чисел.
Производящие функции и наборы гирь.
Комбинаторика орбит
.
Преобразования и орбиты.
Хоровод.
Раскраска куба.
Черно-белый квадрат.
Орбиты и группы преобразований.
Неподвижные элементы.
Черно-белый куб.
Сопряжение и циклы.
Возможное и невозможное в комбинаторике
.
Магические квадраты.
Офицерское каре.
Посев пшеницы.
Принцип Дирихле.
Научная переписка.
Выбор представителей.
Графическое решение.
Прерывания IRQ.
Общие представители.
Игра в 15.
Острова и мосты.
Кругосветное путешествие.
Четыре краски.
Код Хемминга.
Из истории комбинаторики и ее приложений
.
Дела давно минувших дней.
Таинственная черепаха.
Комбинаторика в Древней Греции.
Мистики, астрологи, каббалисты.
Комбинаторика и схоластики.
Комбинаторика в странах Востока.
Liber Abaci.
Игра в кости.
Игрок и ученые.
Новая ветвь математики.
Комбинаторика и шифры.
Анаграммы.
Иероглифы и клинопись.
Комбинаторика в биологии.
Модель ДНК.
Генетический код.
Химический пасьянс.
Комбинаторика эпохи компьютеров.
Ответы
.
В книге в популярной форме рассказывается о комбинаторике, методах решения комбинаторных задач, о рекуррентных соотношениях и производящих функциях. Материал частично захватывает области, выходящие за рамки элементарной математики, однако изложение доступно хорошему ученику средней школы. Книга содержит более 400 упражнений.
ПРЕДИСЛОВИЕ
ГЛАВА 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. Некоторые свойства чисел Сm (n, 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. Игра в 16
138. Острова и мосты
139. Кругосветное путешествие
140. Четыре краски
141. Код Хемминга
Глава XI
ИЗ ИСТОРИИ КОМБИНАТОРИКИ II ЕЕ ПРИЛОЖЕНИЙ
142. Дела давно минувших дней
143. Таинственная черепаха
144. Комбинаторика в Древней Греции
145. Мистики, астрологи, каббалисты
146. Комбинаторика и схоластики
147. Комбинаторика в странах Востока
148. Liber Abaci
149. Игра в кости
150. Игрок и ученые
151. Новая ветвь математики
152. Комбинаторика и шифры
153. Анаграммы
154. Иероглифы и клинопись
155. Комбинаторика в биологии
156. Модель ДНК
157. Генетический код
158. Химический пасьянс
159. Комбинаторика эпохи компьютеров
ОТВЕТЫ
Примеры.
1. Во скольких девятизначных числах все цифры различны?
2. Каких чисел от 1 до 10 000 000 больше: тех, в записи которых встречается единица, или тех, в которых ее нет?
3. Через каждую из трех данных точек на плоскости проведем по т прямых так, чтобы среди них не было двух, параллельных между собой, и трех, пересекающихся в одной точке (за естественным исключением трех прямых одного пучка). Найдите число точек пересечения этих прямых (не считая трех данных).
4. Сколько шестизначных чисел содержат ровно три различные цифры?
5. В составлении 40 задач принимало участие 30 студентов со всех пяти курсов. Любые два студента с одного курса придумали поровну задач, а любые два студента с разных курсов - разное число задач. Сколько человек придумало одну задачу?
6. Сколько имеется шестизначных чисел, у которых сумма цифр четна (допускаются лишь шестизначные числа, первая цифра которых отлична от 0)? А если берут все числа от 1 до 999 999?
- (лат. ars combinatoria). Наука о законах сочетания известных предметов. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. КОМБИНАТОРИКА лат. ars combinatoria. Наука о законах сочетания известных предметов. Объяснение … Словарь иностранных слов русского языка
Раздел математики, в котором изучаются простейшие соединения. Перестановки соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число ихРазмещения соединения, содержащие по m предметов из числа n… … Большой Энциклопедический словарь
КОМБИНАТОРИКА, и, жен. Раздел дискретной математики, изучающий всевозможные сочетания и расположения предметов. | прил. комбинаторный, ая, ое. К. анализ. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 … Толковый словарь Ожегова
Раздел математики, где рассматриваются сочетания, размещения, перестановки элементов и связанные с ними задачи. Широко применяется при вероятностном моделировании геол. процессов. Геологический словарь: в 2 х томах. М.: Недра. Под редакцией К. Н … Геологическая энциклопедия
комбинаторика - — Тематики биотехнологии EN combinatorics … Справочник технического переводчика
КОМБИНАТОРИКА - раздел математики, посвящённый решению задач выбора и расположения элементов из некоторого основного (обычно конечного) множества в соответствии с заданными правилами. Простейшими задачами К. являются перестановки, сочетания и размещения … Большая политехническая энциклопедия
- (Комбинаторный анализ) раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими… … Википедия
И; ж. [лат. combinare соединять] Раздел математики, изучающий все возможные способы простейших перестановок элементов, цифр, каких л. данных. * * * комбинаторика раздел математики, в котором изучаются простейшие «соединения». Перестановки … … Энциклопедический словарь
1) то же, что математический Комбинаторный анализ. 2) Раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов… … Большая советская энциклопедия
Ж. Раздел математики, изучающий различного рода соединения элементов: перестановки, сочетания, размещения. Толковый словарь Ефремовой. Т. Ф. Ефремова. 2000 … Современный толковый словарь русского языка Ефремовой
Комбинаторика, комбинаторики, комбинаторики, комбинаторик, комбинаторике, комбинаторикам, комбинаторику, комбинаторики, комбинаторикой, комбинаторикою, комбинаториками, комбинаторике, комбинаториках (
