Элементы комбинаторики
Правило умножения (основной принцип)
жүктеу/скачать 336 Kb.
|
- Бұл бет үшін навигация:
- Пример 1.
- Правило суммы.
- Пример 2.
- Размещениями
| Правило умножения (основной принцип): если из некоторого конечного множества первый объект (элемент ) можно выбрать способами и после каждого такого выбора второй объект (элемент ) можно выбрать способами, то оба объекта ( и ) в указанном порядке можно выбрать способами.
Этот принцип, очевидно, распространяется на случай трех и более объектов. Пример 1. Сколько трехзначных чисел можно составить из цифр 1, 2,3,4,5, если: а) цифры не повторяются? б) цифры могут повторятся? Решение. Имеется 5 различных способов выбора цифры для первого места (слева в трехзначном числе). После того как первое место занято, например, цифрой 2, осталось четыре цифры для заполнения второго места. Для заполнения третьего места остается выбор из трех цифр. Следовательно, согласно правилу умножения имеется 5 . 4 . 3 = 60 способов расстановки цифр, т. е. искомое количество трехзначных чисел есть 60. (Вот некоторые из этих чисел: 243, 541, 514, 132, ... ) Понятно, что если цифры могут повторяться, то трехзначных чисел 5 . 5 . 5 = 125. (Вот некоторые из них: 255, 333, 414, 111, ... ) Правило суммы. Если некоторый объект можно выбрать способами, а объект можно выбрать способами, причем первые и вторые способы не пересекаются, то любой из указанных объектов ( или ), можно выбрать способами. Это правило распространяется на любое конечное число объектов. Пример 2. В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать, для выполнения различных заданий, двух студентов одного пола? Решение. По правилу умножения двух девушек можно выбрать 14·13 = 182 способами, а двух юношей - 6·5 = 30 способами. Следует выбрать двух студентов одного пола: двух студенток или двух юношей. Согласно правилу сложения таких способов выбора будет 182 + 30 = 212 . Решение вероятностных (и не только их) задач часто облегчается, если использовать комбинаторные формулы. Каждая из них определяет число всевозможных исходов в некотором опыте (эксперименте), состоящем в выборе наудачу элементов из различных элементов рассматриваемого множества. Существуют две схемы выбора элементов из исходного множества: без возвращения (без повторений) и с возвращением (с повторением). В первом случае выбранные элементы не возвращаются обратно; можно отобрать сразу все элементов или последовательно отбирать их по одному. Во второй схеме выбор осуществляется поэлементно с обязательным возвращением отобранного элемента на каждом шаге. Мы рассмотрим только первую схему. Пусть дано множество, состоящее из различных элементов. Размещениями из элементов по элементов называются соединения, каждое из которых состоит из элементов, взятых из данных элементов. При этом размещения отличаются друг от друга как самими элементами, так и их порядком. Число размещений из элементов по элементов обозначается символом и вычисляется по формуле (1) или
, где , . (2) Для составления размещения надо выбрать элементов из множества с элементами и упорядочить их, т. е. заполнить мест элементами множества. Первый элемент можно выбрать способами, т. е. на первое место можно поместить любой из элементов. После этого второй элемент можно выбрать из оставшихся элементов способами. Для выбора третьего элемента имеется способа, четвертого - способа, и, наконец, для последнего -го элемента - способов. Таким образом, по правилу умножения, существует способов выбора элементов из данных элементов, т. е. . жүктеу/скачать 336 Kb. Достарыңызбен бөлісу:
|