Теория множеств. Теорема сложения вероятностей. Случайные величины

подмножества отличаются друг от друга или составом элементов, или порядком их распределения. Но число элементов во всех этих под- множествах равно А;. Для определения числа А размещений из п элементов по А; учтем, что первый элемент подмножества может быть взят п способами, второй — (п—1) способом,..., А;-й элемент — (п—(А;---1)) способами. Отсюда, используя правило умножения, получаем

А =п(п-1)...(п-(А;-1))=

=

п!

Здесь п! = 123...(п-.-1)п и (п—А;)! = 12З..:(п—А;). о 0! Условимся считать 0! = 1, поэтому А0 = = 1. Пример. В соревнованиях принимают участие 16 команд. Сколькями способами могут распредели-ться три первых места, т. е. необходимо найти число всех подмножеств, состоящих из трех элементов, отличающихся составом (номерами команд) или порядком их размещения (подмножества !Ч 1, н 2, Н Зи Н 2, Н 1, Н З являются разными). Таким образом, имеем дело с размещением. Тогда искомое число равно А3 — 16! 16! 12.3.45.678.91011.1213.14.1516 — (16—З)! Л3! 1234б67891011121З —

= 1Ф151б = 3360.

3.1.3. Пересгйановки

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

=А =()! п!1 ,т.е. Р =п!.

Пример. Сколькими способами можно расставить б различных книг на одной полке? Искомое число способов равно

Р = б! = 1 2 3 4 5 6 = 720. б действительно, первую кшву можно выбрать шестью способами, вторую — пятью способами и т.д., последнюю — одним способом. По правилу умножения общее число способовравно654 32 1=720.

3.1.4. Сочетания

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

62

63

Рту ставом элементов. Подмножества, отличающиеся друг от друга лишь порядком следования элементов, не считаются различными. Число всех возможных сочетаний из п элементов по обозначается с. Так как число перестановок из * равно !, то число размещений из п элементов по * — А будет в ! раз больше, чем число сочетаний из п элементов по Iо—С, т. е. А== i”С, ,, А п! отсюда С Пример. В бригаде из 25 человек нужно вщделить четырех для работы на определенном участке. Сколькими способами это можно сделать? Так как порядок выбранных четырех человек не имеет значения, то это можно сделать С способами; 25! 25! 21!22.23.24.2522.2з.24.25 650 25 (25—4)!4г 21! 4! — 12 З•4 —12 Упражнения 1. Имеется 5 видов конвертов без марок и 4 вида марок. Скольквми способами можно выбрать конверт и марку дня посылки письма? Ответ. 20. 2. Из 9 человек надо выбрать 4 человека и разместить их на четырех занумерованньа стульях (по 1 человеку на стуле). Сколькями способами это можно сделать? Ответ. 3024. 3. Сколькими способами можно составить команду из 4 человек для соревнования по бегу, если имеется 7 бегунов? Ответ. 35. 4. Сколькмми способами можно обить б стульев тканью, если имеются ткани шести различных цветов и все стулъя должны быть разного цвета? Ответ. 720.

Происхождение графов Многие задачи сводятся к рассмотрению совокупности объектов, существенные свойства которых описываются связями между ними. Например, глядя на карту автомо- бильньгх дорог, можно интересоваться только тем, имеется ли связь между некоторыми населенным пунктами, отвлекаясь от конфигурации и качеств дорог, расстояний и других подробностей. Ин-терес могут представлять связи и отношения между людьми, событиями, состояниями и вообщ между любыми объектами. 4 В подобных случаях удобно рассматриваемые объекты изображать точками, называемыми вершинами а связи между ними — линиями (произвольно конфигурации), называемыми ребрами. Множество вершин, связи между которыми определен множеством ребер, называют графом. Первая работа по графам была опубликована двадцатилетним Леонардом Эйлером в 1736 г., когд он работал в Российской академии наук. Она содержала решение задачи о кенигсбергских мостах можно ли совершить прогулку таким образом, чтобьт, вьтйдя из любого места города, вернуться в него, пройдя один раз по каждому мосту? С тех пор поток задач с применением графов нарастал подобн снежной лавине. Наряду с многочисленньгм головоломками и играми на графах, рассматривались проблемы, многие из которых требовали использования математических методов. Уже в середине ХiХ в. Кирхгоф применил графы для анализа электрических цепей. Однако теория графов как математическая дисцшлина сформировалась