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

Страницы работы

Фрагмент текста работы

подмножества отличаются друг от друга или составом элементов, или порядком их распределения. Но число элементов во всех этих под- множествах равно А;. Для определения числа А размещений из п элементов по А; учтем, что первый элемент подмножества может быть взят п способами, второй — (п—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Х в. Кирхгоф применил графы для анализа электрических цепей. Однако теория графов как математическая дисцшлина сформировалась

Похожие материалы

Информация о работе

Предмет:
Математика
Тип:
Конспекты лекций
Размер файла:
133 Kb
Скачали:
0