Комбинаторика (Виленкин) 1969 год

Скачать Советский учебник

Комбинаторика (Виленкин) 1969 

Назначение: ИЗДАНИЕ РАССЧИТАНО НА САМЫЕ ШИРОКИЕ КРУГИ ЧИТАТЕЛЕЙ

© "НАУКА" ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1969

Авторство: Наум Яковлевич Виленкин

Формат: DjVu, Размер файла: 2.59 MB

СОДЕРЖАНИЕ

Предисловие 6

     

      Глава I. Общие правила комбинаторики 9

      Суеверные велосипедисты 9

      Размещения с повторениями 10

      Системы счисления 12

      Секретный замок 12

      Код Морзе 13

      Морской семафор 15

      Электронная цифровая вычислительная машина 15

      Генетический код 16

{spoiler=ОТКРЫТЬ:  оглавление полностью...}

 

      Общие правила комбинаторики 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 

{/spoilers}

Скачать бесплатный учебник  СССР - Комбинаторика (Виленкин) 1969 года

СКАЧАТЬ DjVu

{spoiler=ОТКРЫТЬ: - отрывок из учебника...}

 ПРЕДИСЛОВИЕ

      Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Начальнику цеха надо распределить несколько видов работ между имеющимися станками, агроному — разместить посевы сельскохозяйственных культур на нескольких полях, заведующему учебной частью школы — составить расписание уроков, ученому-химику — рассмотреть возможные связи между атомами и молекулами, лингвисту — учесть различные варианты значений букв незнакомого языка и т. д. Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой.

      Комбинаторика возникла в 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 двузначный номер без восьмерок.

{/spoilers}

 

УЧЕБНИКИ ПО МАТЕМАТИКЕ СПИСКОМ И ДРУГИЕ РАЗДЕЛЫ БИБЛИОТЕКИ ВС

НОВЫЕ ПУБЛИКАЦИИ УЧЕБНИКОВ И КНИГ ПО МАТЕМАТИКЕ

БОЛЬШЕ НЕТ

ПОПУЛЯРНЫЕ УЧЕБНИКИ И КНИГИ ПО МАТЕМАТИКЕ

БОЛЬШЕ НЕТ

Еще из раздела - МАТЕМАТИКА

БОЛЬШЕ НЕТ
Яндекс.Метрика