КнигоПровод.Ru | 05.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 |
|
Книги на ту же тему- Живые числа. Пять экскурсий, Боро В., Цагир Д., Рольфс Ю., Крафт Х., Янцен Е., 1985
- Прикладная комбинаторная математика, Беккенбах Э., ред., 1968
- Комбинаторные методы дискретной математики, Сачков В. Н., 1977
- Преобразования и перестановки, Калужнин Л. А., Сущанский В. И., 1979
- Введение в прикладную комбинаторику, Кофман А., 1975
- Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
- Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
- Теория вероятностей и математическая статистика. Учеб. пособие для втузов. — 5-е изд., перераб. и доп., Гмурман В. Е., 1977
- Теория вероятностей. Математическая статистика, Бочаров П. П., Печинкин А. В., 1998
- Теория вероятностей, Солодовников А. С., 1999
- Вероятность, Ламперти Д., 1973
- Вероятность, Мостеллер Ф., Рурке Р., Томас Д., 1969
- Задачник по теории вероятностей, Палий И. А., 2004
- Дискретная математика для программистов, Хаггарти Р., 2004
- Информатика, Луенбергер Д. Д., 2008
- Эффективное кодирование, Новик Д. А., 1965
- Основы кодирования, Вернер М., 2006
- Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение, Морелос-Сарагоса Р., 2005
- Кибернетическое моделирование. Некоторые приложения, Кемени Д. Д., Снелл Д. Л., 1972
|
|
|
© 1913—2013 КнигоПровод.Ru | http://knigoprovod.ru |
|