На главную Тексты книг БК Аудиокниги БК Полит-инфо Советские учебники За страницами учебника Фото-Питер Техническая книга Радиоспектакли Детская библиотека

Комбинаторика. Виленкин Н. Я. — 1969 г

Наум Яковлевич Виленкин

Комбинаторика

*** 1969 ***


DjVu

      ОГЛАВЛЕНИЕ
     
      Предисловие 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


Фрагмент:

      ПРЕДИСЛОВИЕ
      Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Начальнику цеха надо распределить несколько видов работ между имеющимися станками, агроному — разместить посевы сельскохозяйственных культур на нескольких полях, заведующему учебной частью школы — составить расписание уроков, ученому-химику — рассмотреть возможные связи между атомами и молекулами, лингвисту — учесть различные варианты значений букв незнакомого языка и т. д. Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой.
      Комбинаторика возникла в 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 двузначный номер без восьмерок.


      KOHEЦ ФPAГMEHTA

 

На главную Тексты книг БК Аудиокниги БК Полит-инфо Советские учебники За страницами учебника Фото-Питер Техническая книга Радиоспектакли Детская библиотека


Борис Карлов 2001—3001 гг.