КнигоПровод.Ru05.12.2024

/Наука и Техника/Математика

Комбинаторика — Виленкин Н. Я.
Комбинаторика
Виленкин Н. Я.
год издания — 1969, кол-во страниц — 328, тираж — 100000, язык — русский, тип обложки — твёрд. 7Б суперобл., масса книги — 340 гр., издательство — Физматлит
цена: 700.00 рубПоложить эту книгу в корзину
Сохранность книги — хорошая, суперобложки — удовл.

Формат 60x90 1/16. Бумага типографская №1. Печать офсетная
ключевые слова — комбинатор, рекуррентн, производящ, комбинац, расписан, азартн, лотер, карточн, вероятност, тарталь, ставк, дискретн, транспортн, кодирован, шифр, размещен, перестановк, сочетан, факториал, разбиен, информатик, бином

Комбинаторика — один из разделов математики, нужный представителям самых разных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, лингвистам, инженерам и многим другим научно-техническим работникам. Комбинаторные рассмотрения лежат в основе решения многих задач теории вероятностей и её приложений.

В этой книге в популярной форме рассказывается о комбинаторике, методах решения комбинаторных задач, о рекуррентных соотношениях и производящих функциях. Материал частично захватывает области, выходящие из рамок элементарной математики, однако изложение доступно хорошему ученику средней школы.

Книга будет полезна школьникам старших классов, интересующимся математикой, студентам первых курсов математических факультетов университетов и пединститутов, а также всем, сталкивающимся в своей практической работе с комбинаторными задачами.

Виленкин Наум Яковлевич (род. в 1920 году), доктор физико-математических наук, профессор, автор около 100 научных работ в области топологической алгебры, теории функций действительного переменного и теории представлений групп. Кроме того, им написано более 50 научно-популярных и педагогических статей, его популярные книги «Рассказы о множествах» и «Метод последовательных приближений» переведены на многие иностранные языки.


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

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

ПРЕДИСЛОВИЕ

ОГЛАВЛЕНИЕ

Предисловие6
 
Г л а в а  I.  Общие правила комбинаторики9
 
Суеверные велосипедисты9
Размещения с повторениями10
Системы счисления12
Секретный замок12
Код Морзе13
Морской семафор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
Как разменять гривенник?110
Разбиение чисел на слагаемые112
Диаграммная техника11З
Двойственные диаграммы115
Формула Эйлера116
 
Г л а в а  V.  Комбинаторика на шахматной доске121
 
Человек бродит по городу121
Арифметический квадрат122
Фигурные числа123
Арифметический треугольник125
Расширенный арифметический треугольник126
Шахматный король128
Обобщённый арифметический треугольник129
Обобщённые арифметические треугольники и m-ичная система счисления131
Некоторые свойства чисел Cm(k,n)131
Шашка в углу133
Арифметический пятиугольник135
Геометрический способ доказательства свойств сочетаний137
Случайные блуждания140
Броуновское движение141
У Шемаханской царицы143
Поглощающая стенка145
Блуждания по бесконечной плоскости145
Общая задача о ладьях147
Симметричные расстановки148
Два коня151
 
Г л а в а  VI.  Рекуррентные соотношения154
 
Числа Фибоначчи155
Другой метод доказательства158
Процесс последовательных разбиений159
Умножение и деление чисел161
Задачи о многоугольниках163
Затруднение мажордома165
Счастливые троллейбусные билеты169
Рекуррентные таблицы170
Другое решение проблемы мажордома172
Решение рекуррентных соотношений174
Линейные рекуррентные соотношения с постоянными коэффициентами175
Случай равных корней характеристического уравнения178
Третье решение задачи мажордома180
 
Г л а в а  VII.  Комбинаторика и ряды182
 
Деление многочленов182
Алгебраические дроби и степенные ряды183
Действия над степенными рядами187
Применение степенных рядов для доказательства тождеств190
Производящие функции191
Бином Ньютона192
Полиномиальная формула196
Ряд Ньютона199
Извлечение квадратных корней202
Производящие функции и рекуррентные соотношения205
Разложение на элементарные дроби207
Об едином нелинейном рекуррентном соотношении210
Производящие функции и разбиения чисел212
Сводка результатов по комбинаторике разбиений216
 
Задачи по комбинаторике219
Решения и ответы255

Книги на ту же тему

  1. Живые числа. Пять экскурсий, Боро В., Цагир Д., Рольфс Ю., Крафт Х., Янцен Е., 1985
  2. Прикладная комбинаторная математика, Беккенбах Э., ред., 1968
  3. Комбинаторные методы дискретной математики, Сачков В. Н., 1977
  4. Преобразования и перестановки, Калужнин Л. А., Сущанский В. И., 1979
  5. Введение в прикладную комбинаторику, Кофман А., 1975
  6. Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
  7. Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
  8. Теория вероятностей и математическая статистика. Учеб. пособие для втузов. — 5-е изд., перераб. и доп., Гмурман В. Е., 1977
  9. Теория вероятностей. Математическая статистика, Бочаров П. П., Печинкин А. В., 1998
  10. Теория вероятностей, Солодовников А. С., 1999
  11. Вероятность, Ламперти Д., 1973
  12. Вероятность, Мостеллер Ф., Рурке Р., Томас Д., 1969
  13. Задачник по теории вероятностей, Палий И. А., 2004
  14. Дискретная математика для программистов, Хаггарти Р., 2004
  15. Информатика, Луенбергер Д. Д., 2008
  16. Эффективное кодирование, Новик Д. А., 1965
  17. Основы кодирования, Вернер М., 2006
  18. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение, Морелос-Сарагоса Р., 2005
  19. Кибернетическое моделирование. Некоторые приложения, Кемени Д. Д., Снелл Д. Л., 1972

© 1913—2013 КнигоПровод.Ruhttp://knigoprovod.ru