Комбинаторика (Виленкин) 1969 год - старые учебники
Скачать Советский учебник
Назначение: ИЗДАНИЕ РАССЧИТАНО НА САМЫЕ ШИРОКИЕ КРУГИ ЧИТАТЕЛЕЙ
Авторство: Наум Яковлевич Виленкин
Формат: DjVu, Размер файла: 2.59 MB
СОДЕРЖАНИЕ
Предисловие 6
Глава I. Общие правила комбинаторики 9
Суеверные велосипедисты 9
Размещения с повторениями 10
Системы счисления 12
Секретный замок 12
Код Морзе 13
Морской семафор 15
Электронная цифровая вычислительная машина 15
Генетический код 16
Общие правила комбинаторики 17
Задача о домино 19
Команда космического корабля 20
Задачи о шашках 21
Сколько человек не знают иностранных языков? 24
Формула включений и исключений 25
В чем ошибка? 27
Решето Эратосфена 28
Глава II. Размещения, перестановки и сочетания 31
Футбольное первенство
Размещения без повторений
Научное общество
Перестановки
Задача о ладьях
Лингвистические проблемы
Хоровод
Перестановки с повторениями
Анаграммы
Сочетания
Генуэзская лотерея
Покупка пирожных
Сочетания с повторениями
Снова футбольное первенство
Свойства сочетаний
Частный случай формулы включений и исключений
Знакопеременные суммы сочетаний
Глава III. Комбинаторные задачи с ограничениями 63
Львы и тигры
Постройка лестницы
Книжная полка
Рыцари короля Артура
Девушка спешит на свидание
Сеанс телепатии
Общая задача о смещении
Субфакториалы
Караван в пустыне
Катание на карусели
Очередь в кассу
Задача о двух шеренгах
Новые свойства сочетаний
Глава IV. Комбинаторика разбиений
Игра в домино
Раскладка по ящикам
Букет цветов
Задача о числе делителей
Сбор яблок
Сбор грибов
Посылка фотографий
Флаги на мачтах
Полное число сигналов
Разные статистики
Разбиения чисел
Отправка бандероли
Общая задача о наклепке марок
Комбинаторные задачи теории информации
Проблема абитуриента
Уплата денег
Покупка конфет
Как разменять гривенник?
Разбиение чисел на слагаемые
Диаграммная техника
Двойственные диаграммы
Формула Эйлера
Глава V. Комбинаторика на шахматной доске 121
Человек бродит по городу 121
Арифметический квадрат 122
Фигурные числа 123
Арифметический треугольник 125
Расширенный арифметический треугольник 126
Шахматный король 128
Обобщенный арифметический треугольник 129
Обобщенные арифметические треугольники и шичная система счисления 131
Некоторые свойства чисел Cm(k, п) 131
Шашка в углу 133
Арифметический пятиугольник
Геометрический способ доказательства свойств сочетаний 137
Случайные блуждания 140
Броуновское движение 141
У Шемаханской парины 143
Поглощающая стенка 145
Блуждания по бесконечной плоскости 145
Общая задача о ладьях 147
Симметричные расстановки 148
Два коня 151
Глава VI. Рекуррентные соотношения
Числа Фибоначчи
Другой метод доказательства
Процесс последовательных разбиений
Умножение и деление чисел
Задачи о многоугольниках
Затруднение мажордома
Счастливые троллейбусные билеты
Рекуррентные таблицы
Другое решение проблемы мажордома
Решение рекуррентных соотношений
Линейные рекуррентные соотношения с постоянными коэффициентами
Случай равных корней характеристического уравнения
Третье решение задачи мажордома
Глава VII. Комбинаторика и ряды 182
Деление многочленов 182
Алгебраические дроби и степенные ряды 183
Действия над степенными рядами 187
Применение степенных рядов для доказательства тождеств 193
Производящие функции 191
Бином Ньютона 192
Полиномиальная формула 195
Ряд Ньютона 199
Извлечение квадратных корней 202
Производящие функции и рекуррентные соотношения 205
Разложение на элементарные дроби 237
Об едином нелинейном рекуррентном соотношении 210
Производящие функции и разбиения чисел 212
Сводка результатов по комбинаторике разбиений 216
Задачи по комбинаторике 219
Решения и ответы 255
Скачать бесплатный учебник СССР - Комбинаторика (Виленкин) 1969 года
СКАЧАТЬ DjVu
ПРЕДИСЛОВИЕ
Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Начальнику цеха надо распределить несколько видов работ между имеющимися станками, агроному — разместить посевы сельскохозяйственных культур на нескольких полях, заведующему учебной частью школы — составить расписание уроков, ученому-химику — рассмотреть возможные связи между атомами и молекулами, лингвисту — учесть различные варианты значений букв незнакомого языка и т. д. Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой.
Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры. В карты и кости выигрывались и проигрывались золото и бриллианты, дворцы и имения, породистые кони и дорогие украшения. Широко были распространены всевозможные лотереи. Понятно, что первоначально комбинаторные задачи касались в основном азартных игр — вопросов, сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей в данной карточной игре. Эти и другие проблемы азартных игр явились движущей силой в развитии комбинаторики и развивавшейся одновременно с ней теории вероятностей.
Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывавшую, сколькими способами могут выпасть r костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена разными способами (например, 1 + 3 + 4 = 4 + 2 + 2).
Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские ученые Паскаль и Ферма. Исходным пунктом их исследований тоже были проблемы азартных игр. Особенно большую роль сыграла здесь задача о разделе ставки, которую предложил Паскалю его друг шевалье де Мере, страстный игрок. Проблема состояла в следующем: «матч» в орлянку ведется до шести выигранных партий; он был прерван, когда один игрок выиграл 5 партий, а другой — 4; как разделить ставку? Было ясно, что раздел в отношении 5:4 несправедлив. Применив методы комбинаторики, Паскаль решил задачу в общем случае, когда одному игроку остается до выигрыша r партий, а второму s партий. Другое решение задачи дал Ферма.
Дальнейшее развитие комбинаторики связано с именами Якова Бернулли, Лейбница и Эйлера. Однако и у них основную роль играли приложения к различным играм (лото, солитер и др.). За последние годы комбинаторика переживает период бурного развития, связанного с общим повышением интереса к проблемам дискретной математики. Комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний; для составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики и т. д. Комбинаторика используется для составления и декодирования шифров и для решения других проблем теории информации.
Значительную роль комбинаторные методы играют и в чисто математических вопросах — теории групп и их представлений, изучении оснований геометрии, неассоциативных алгебр и т. д.
На русском языке очень мало книг по комбинаторике. Помимо совсем элементарных книг типа школьных учебников, можно указать лишь на переводные книги М. Холла «Комбинаторный анализ», ИЛ, 1963; Дж. Риордана «Введение в комбинаторный анализ», ИЛ, 1963, и Г. Дж. Райзера «Комбинаторная математика», «Мир», 1965.
В предлагаемой вниманию читателя книге о комбинаторных проблемах рассказывается в занимательной, популярной форме. Тем не менее в ней разбираются и некоторые довольно сложные комбинаторные задачи, дается понятие о методах рекуррентных соотношений и производящих функций.
Первая глава книги посвящена общим правилам комбинаторики — правилам суммы и произведения. Во второй главе изучаются размещения, перестановки и сочетания. Этот традиционный школьный материал сопровождается разбором некоторых занимательных примеров. В главе III мы изучаем комбинаторные задачи, в которых на рассматриваемые комбинации налагаются те или иные ограничения. В главе IV рассмотрены задачи на разбиения чисел и рассказано о геометрических методах в комбинаторике.
Глава V посвящена задачам о случайных блужданиях и различным модификациям арифметического треугольника. В главе VI рассказано о рекуррентных соотношениях, а в главе VII — о производящих функциях, и в частности о биномиальной формуле.
К книге приложено несколько сотен задач по комбинаторике, взятых автором из различных источников. Много задач заимствовано из книги Уитворта «Выбор и случай» (Whitworth W. A., Choice and Chance, London, 1901), упомянутой книги Риордана, книги А. ДА. Яглома и И. М. Яглома «Неэлементарные задачи в элементарном изложении», Гостехиздат, 1954, различных сборников задач математических олимпиад и т. д.
ГЛАВА I
ОБЩИЕ ПРАВИЛА КОМБИНАТОРИКИ
Суеверные велосипедисты
«Опять восьмерка!» — горестно воскликнул председатель клуба велосипедистов, взглянув на погнутое колесо своего велосипеда. «А все почему? Да потому, что при вступлении в клуб мне выдали билет за номером 008, И теперь месяца не проходит, чтобы то на одном, то па другом колесе не появилась восьмерка. Надо менять номер билета. А чтобы меня не обвиняли в суеверии, проведу-ка я перерегистрацию всех членов клуба и буду выдавать только билеты с номерами, в которые ни одна восьмерка не входит».
Сказано — сделано, и на другой день он заменил все билеты. Сколько членов было в клубе, если известно, что использованы все трехзначные номера, не содержащие ни одной восьмерки? (Например, 000 использован, а 836 нет.)
Для решения этой задачи определим сначала, сколько однозначных номеров не содержит восьмерку. Ясно, что таких номеров девять 0, 1, 2, 3, 4, 5, 6, 7, 9 (номер 8 пропускается). А теперь найдем все двузначные номера, не содержащие восьмерок. Их можно составить так: взять любой из найденных однозначных номеров и написать после него любую из девяти допустимых цифр. В результате из каждого однозначного номера получится девять двузначных. А так как однозначных номеров тоже 9, то получится 9х9=81 двузначный номер без восьмерок.
Автор - Виленкин Н.Я. , Дискретная математика, Комбинаторика