Комбинаторика. Виленкин Н.Я.
Виленкин Н.Я.
М.: Наука. Гл. ред. физ.-мат. лит., 1969.— 323 с.
В предлагаемой вниманию читателя книге о комбинаторных проблемах рассказывается в занимательной, популярной форме. Тем не менее в ней разбираются и некоторые довольно сложные комбинаторные задачи, дается понятие о методах рекуррентных соотношений и производящих функций.
Первая глава книги посвящена общим правилам комбинаторики— правилам суммы и произведения. Во второй главе изучаются размещения, перестановки и сочетания. Этот традиционный школьный материал сопровождается разбором некоторых занимательных примеров. В главе III мы изучаем комбинаторные задачи, в которых на рассматриваемые комбинации налагаются те или иные ограничения. В главе IV рассмотрены задачи на разбиения чисел и рассказано о геометрических методах в комбинаторике. Глава V посвящена задачам о случайных блужданиях и различным модификациям арифметического треугольника. В главе VI рассказано о рекуррентных соотношениях, а в главе VII — о производящих функциях, и в частности о биномиальной формуле.
К книге приложено несколько сотен задач по комбинаторике, взятых автором из различных источников. Много задач заимствовано из книги Уитворта «Выбор и случай» (Whitworth W. A., Choice and Chance, London, 1901), упомянутой книги Риордана, книги А. М. Яглома и И. М. Яглома «Неэлементарные задачи в элементарном изложении», Гостехиздат, 1954, различных сборников задач математических олимпиад и т. д.
Формат: djvu / zip
Размер: 2,6 Мб
Оглавление:
Предисловие
Глава 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
Комбинаторика