ПРЕДИСЛОВИЕ

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

При изучении комбинаторики мы считали целесообразным систематически использовать понятия множества и операции над множествами, поскольку большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств.

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

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

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

Авторы искренне благодарят М. X. Клина и А. Ф. Лапко, внимательно прочитавших украинское издание книги и сделавших большое число полезных замечаний.

Авторы

• 1. ВВЕДЕНИЕ. ОСНОВНОЙ ПРИНЦИП КОМБИНАТОРИКИ

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

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

Установим сначала очень важное правило, которое часто применяется при комбинаторных расчетах. Начнем с такой задачи.

Задача 1. Из Киева до Чернигова можно добраться пароходом, поездом, автобусом, самолетом; из Чернигова до Новгорода-Северского — пароходом и автобусом. Сколькими способами можно осуществить

путешествие по маршруту Киев — Чернигов — Новгород-Северский?

Решение. Очевидно, число разных путей из Киева до Новгорода-Северского равно 4X2 = 8, так как, выбрав один из четырех возможных способов путешествия от Киева до Чернигова, имеем два возможных способа путешествия от Чернигова до Новгорода- Северского (рис. 1).

Ниед

пароход абтобус

Чернигов

пароход автобус

Новгород-Северский

Рис. 1.

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

Если некоторый выбор А можно осуществить т различными способами, а для каждого из этих способов некоторый другой выбор В можно осуществить п способами, то выбор А и В (в указанном порядке) можно осуществить т X ^п способами.

Иначе говоря, если некоторое действие (например, выбор пути от Киева до Чернигова) можно осуществить пг различными способами, после чего другое действие (выбор пути от Чернигова до Новгорода-Северского) можно осуществить и способами, то два действия вместе (выбор пути от Киева до Чернигова, выбор пути от Чернигова до Новгорода-Северского) можно осуществить т X п способами.

Задача 2. В розыгрыше первенства страны по футболу принимает участие 16 команд. Сколькими способами могут быть распределены золотая и серебряная медали?

Решение. Золотую медаль может получить одна из 16 команд. После того как определен владелец золотой медали, серебряную медаль может иметь одна из 15 команд. Следовательно, общее число способов, которыми могут быть распределены золотая и серебряная медали, равно 16 X 15 = 240.

Сформулируем теперь основное правило комбинаторики (правило умножения) в общем виде.

Пусть требуется выполнить одно за другим k дей* ствий. Если первое действие можно выполнить П\ с по* собами, второе действие — п₂ способами, третье дей* ствие — п₃ способами и так до k-го действия, которое можно выполнить пь способами, то все k действий вместе могут быть выполнены

rhXn₂Xn₃X . Xn_k способами.

Задача 3. Сколько четырехзначных чисел можно составить из цифр 0, 1,2, 3, 4, б, если:

а) ни одна из цифр не повторяется более одного раза;

б) цифры могут повторяться;

в) числа должны быть нечетными (цифры могут повторяться)?

Решение, а) Первой цифрой числа может быть одна из 5 цифр 1, 2, 3, 4, 5 (0 не может быть первой цифрой, потому что в таком случае число не четырехзначное); если первая цифра выбрана, то вторая может быть выбрана 5 способами, третья — 4 способами, четвертая—3 способами. Согласно правилу умножения общее число способов равно 5Х5Х4ХЗ= 300, б) Первой цифрой может быть одна из цифр 1, 2, 3, 4, 5 (5 возможностей), для каждой из следующих цифр имеем б возможностей (0, 1, 2, 3, 4, 5). Следовательно, число искомых чиёел равно 5Х6Х6Х6 = == 5Х6³ = 1080.

в) Первой цифрой может быть одна из цифр 1, 2, 3, 4, 5, а последней— одна из цифр 1, 3, 5 (числа должны быть нечетными). Следовательно, общее количество чисел равно 5Х6Х6ХЗ = 540.

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

УПРАЖНЕНИЯ

1. На вершину горы ведет 7 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? Дайте ответ на тот же'самый вопрос, если подъем и спуск осуществляются различными путями.

2. Сколько трехзначных чисел можно составить из цифр I, 2, 3, 4, 5?

3. Сколько трехзначных чисел можно составить из цифр I, 2, 3, 4, 5, если каждую из этих цифр можно использовать не более одного раза?

4. Сколькими способами 7 человек могут разместиться в очереди в кассу?

5. В классе изучают 10 предметов. В понедельник 6 уроков, причем все уроки разные. Сколькими способами можно составить расписание на понедельник?

6. Сколько имеется пятизначных чисел, которые делятся на 5?

7. На одной из боковых сторон треугольника взято п точек, на другой — т точек. Каждая из вершин при основании треугольника соединена прямыми с точками, взятыми на противоположной стороне, а) Сколько точек пересечения этих прямых образуется внутри треугольника? б) На сколько частей делят треугольник эти прямые?

8. Сколько есть двузначных чисел, у которых обе цифры четные?

9. Сколько есть пятизначных чисел, у которых все цифры нечетные?

10. Сколько четырехзначных чисел можно написать с помощью цифр 0, 1, 2, 3, 4, 5? Найти сумму всех этих чисел.

11. Сколько есть трехзначных чисел, которые записываются с помощью цифр 0, I, 2, 3, 4, 5 и делятся на 3?

12. Сколько есть пятизначных чисел, которые одинаково читаются слева направо и справа налево (например, таких, как 67876, 17071)?

13. 5 мальчиков и 5 девочек садятся в ряд на 10 расположенных подряд стульев, причем мальчики садятся на места с нечетными номерами, а девочки — на места с четными номерами. Сколькими способами это можно сделать?

14. Сколько разных слов можно составить перестановкой букв в слове «математика»?

15. Автомобильные номера составляются из одной, двух или трех букв и четырех цифр. Найти число таких номеров, используя 32 буквы русского алфавита.

16. В селении живут 1500 жителей. Доказать, что по крайней мере двое из них имеют одинаковые инициалы.

17. а) Сколько разных делителей имеет число З⁹ X 5*? б) Пусть pt,., р_п — различные простые числа. Сколько делителей имеет число

т = р“'Х . ХР?>

где ai, Лп — некоторые натуральные числа?

18. От А до В 999 км. Вдоль дороги стоят столбы, на которых указаны расстояния до А и до В

0 999 ; 1,998 ;

2,997 ; 999,0

Сколько среди них таких, на которых есть только 2 различные цифры?

19. Пассажир оставил вещи в автоматической камере хранения, а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37, Чтобы открыть камеру, нужно правильно набрать пятизначный номер. Какое наибольшее количество номеров нужно перебрать, чтобы открыть камеру?

20. В прямоугольной таблице из т строк и п столбцов записаны числа +1 и —1 так, что произведение чисел в каждой строке и каждом столбце равно 1. Сколькими способами это можно сделать?

• 2. КОНЕЧНЫЕ МНОЖЕСТВА И ОПЕРАЦИИ НАД НИМИ

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

Основной характеристикой конечного множества является число его элементов.

Теория конечных множеств изучает правила: как, зная количество элементов некоторых множеств, вычислить количество элементов других множеств, которые составлены из первых с помощью некоторых операций. Операции над множествами мы введем немного позднее.

Введем основные обозначения, которыми будем пользоваться в дальнейшем. Множества будем обозначать большими латинскими буквами, их элементы— малыми'. аеЛ: а есть элемент А, или а принадлежит А; а ё==Л: а не есть элемент А, или а не принадлежит А. Количество элементов множества будем обозначать N(A),

2.1. Операции над множествами. Два множества равны между собой, если элементы первого являются

элементами второго и, наоборот, элементы второго являются элементами первого.

Если А и В—два множества, то множество С, которому принадлежат все те и только те элементы, которые входят либо в А, либо в В, называется суммой или объединением множеств А и В и обозначается С = A U В.

Эта операция «сложения» множеств удовлетворяет коммутативному и ассоциативному закону:

AUB=BUA A U (В U С) = (A (JB) U С. (1)

Первое из этих равенств вытекает из определения суммы. Второе есть следствие того, что и A U (В U С) и (A U В) (J С есть совокупность элементов, входящих хотя бы в одно из множеств А, либо В, либо С. Поэтому можно рассматривать сумму любого числа множеств Ai U А₂ U . U А_п, это будет множество, в которое входят элементы каждого из множеств Ai, А₂, ., А_п и только они (общие элементы считаются только по одному разу).

Однако это «сложение» отличается от обычного сложения. Чтобы пояснить это, рассмотрим числовые множества. Если %i, ., х_п— некоторые числа, то через {xi, ., х_п} обозначим множество, которое состоит из элементов ., х_п. Предположим, что даны два множества {1, 2, 3} и {2, 3, 4}. Тогда {1, 2, 3} U {2, 3, 4} = {1, 2, 3, 4}. Если множества А и В имеют общие элементы, то каждый из этих элементов входит в A U В только один раз. Итак, число элементов в сумме множеств не обязательно равно сумме чисел элементов первого и второго множеств, а может быть меньше ее. В частности, сложение множеств приводит к такой необычной для чисел формуле:

AUA = A, AUAU . иЛ = А.

Множество С, которому принадлежат те и только те элементы, которые являются общими для множеств А и В (элементы, которые входят в оба эти множества), называется пересечением множеств А и В и обозначается С = А П В.