|
Комбинаторика — один из разделов математики, играющий важную роль при решении некоторых современных проблем теории вероятностей, кибернетики, математической логики, теории чисел. Знание комбинаторики необходимо представителям самых разных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, лингвистам, специалистам по теории кодов. В книге изложены основные понятия и методы комбинаторики. Изложение ма- териала построено на систематическом использовании теоретико-множественных понятий. Книга рассчитана на учащихся средних школ и студентов младших курсов университетов. Она мржет быть полезна и для лиц, занимающихся комбинаторными расчетами
ОГЛАВЛЕНИЕ
Предисловие 4
§ 1. Введение. Основной принцип комбинаторики 5
§ 2. Конечные множества и операции над ними 9
§ 3. Подмножества данного множества 15
§ 4. Упорядоченные множества. Перестановки и размещения 22
§ 5. Перестановки с повторениями 26
§ 6. Взаимно однозначное соответствие. Сочетания с повторениями 29
§ 7. Прямое произведение множеств 33
§ 8. Бином Ньютона и полиномиальная формула 35
§ 9. Метод рекуррентных соотношений 45
§ 10. Метод производящих функций 47
§ 11. Метод включения и исключения. 59
§ 12. Метод траекторий 64
Ответы, указания, решения 75
Литература 89
ПРЕДИСЛОВИЕ
Комбинаторика — один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике. Между тем программа средней школы не уделяет должного внимания этой полезной и интересной математической дисциплине. Цель этой книжки — ознакомить учащихся с основными понятиями комбинаторики и методами решения комбинаторных задач.
При изучении комбинаторики мы считали целесообразным систематически использовать понятия множества и операции над множествами, поскольку большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств.
При решении комбинаторных задач следует особо отметить метод производящих функций и метод траекторий. Эти методы важны сами по себе, так как находят широкое применение не только в комбинаторике, но и во многих разделах современной математики.
В основу книги положены лекции, прочитанные авторами учащимся республиканской заочной физико-математической школы.
Книга предназначена учащимся средних школ и студентам младших курсов университетов. Она может быть полезна и лицам, занимающимся комбинаторными расчетами. В настоящее издание внесены некоторые исправления и добавлены новые задачи.
Авторы искренне благодарят М. X. Клина и А. Ф. Лапко, внимательно прочитавших украинское издание книги и сделавших большое число полезных замечаний.
Авторы
Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Сколькими способами можно расположить 50 человек в очереди в кассу кино? Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали на чемпионате мира по футболу? Задачи такого типа называются комбинаторными.
С комбинаторными вычислениями приходится иметь дела представителям многих специальностей: ученому-химику при рассмотрении различных возможных типов связи атомов в молекулах, биологу при изучении различных возможных последовательностей чередования ахминокислот в белковых соединениях, конструктору вычислительных машин, агроному, рассматривающему различные_зозможные способы посевов на нескольких участках, диспетчеру при составлении графика движения. Комбинаторные соображения лежат в основе решения многих задач теории вероятностей — важного раздела современной математики, посвященного изучению случайных явлений. Усиленный интерес к комбинаторике в последнее время обусловлен бурным развитием кибернетики, вычислительной техники.
KOHEЦ ФPAГMEHTA КНИГИ
|
