Читать онлайн «Элементы комбинаторики»

. ). 0: \B. CKi*i ii, . / l » ы я И, И, ЕЖОВ, А. В. СКОРОХОД, М. И. ЯДРЕНКО ЭЛЕМЕНТЫ КОМБИНАТОРИКИ Перевод с украинского 3. Л. Кулик издательство «наука» главная редакция физико-математической литературы Москва 197 7 ОГЛАВЛЕНИЕ Предисловие* 4 § 1. Введение. Основной принцип комбинаторики 5 § 2. Конечные множества и операции над ними 9 § 3. Подмножества данного множества 15 § 4. Упорядоченные множества. Перестановки и размещения 22 § 5. Перестановки с повторениями . . 26 § 6. Взаимно однозначное соответствие. Сочетания с повторениями 29 § 7. Прямое произведение множеств ... . ... ... . 33 § 8. Бином Ньютона и полиномиальная формула 35 § 9. Метод рекуррентных соотношений 45 § 10. Метод производящих функций . . 47 § 11. Метод включения и исключения ... ... ... . 5Э § 12. Метод траекторий . 64 Ответы, указания, решения . . . . . . . . . 75 Литература, . . '. . . 80 ПРЕДИСЛОВИЕ Комбинаторика — один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике. Между тем программа средней школы не уделяет должного внимания этой полезной и интересной математической дисциплине. Цель этой книжки — ознакомить учащихся с основными понятиями комбинаторики и методами решения комбинаторных задач. При изучении комбинаторики мы считали целесообразным систематически использовать понятия множества и операции над множествами, поскольку большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств. При решении комбинаторных задач следует особо отметить метод производящих функций и метод траекторий. Эти методы важны сами по себе, так как находят широкое применение не только в комбинаторике, но и во многих разделах современной математики. В основу книги положены лекции, прочитанные авторами учащимся республиканской заочной физико- математической школы. Книга предназначена учащимся средних школ и студентам младших курсов университетов. Она может быть полезна и лицам, занимающимся комбинаторными расчетами. В настоящее издание внесены некоторые исправления и добавлены новые задачи. Авторы искренне благодарят М. X. Клина и А. Ф. Лапко, внимательно прочитавших украинское издание книги и сделавших большое число полезных замечаний. Авторы § 1. ВВЕДЕНИЕ. ОСНОВНОЙ ПРИНЦИП КОМБИНАТОРИКИ Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Сколькими способами можно расположить 50 человек в очереди в кассу кино? Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали на чемпионате мира по футболу? Задачи такого типа называются комбинаторными. С комбинаторными вычислениями приходится иметь дела представителям многих специальностей: ученому-химику при рассмотрении различных возможных типов связи атомов в молекулах, биологу чпри изучении различных возможных последовательностей чередования аминокислот в белковых соединениях, конструктору вычислительных машин, агроному, рассматривающему различны^^возможные способы посевов на нескольких участках, диспетчеру при составлении графика движения.