Правило умножения

Элементы комбинаторики

Основные правила комбинаторики.

Правило сложения

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

Пример 2. Из пункта А в пункт В можно добраться самолетом, поездом и автобусом, причем между этими пунктами существуют 2 авиамаршрута, 1 железнодорожный и 3 автобусных. Следовательно, общее число маршрутов между пунктами А и В равно 2 + 1 + 3 = 6.

Обобщая изложенное, можно сформулировать правило сложения.

Если выбор каждого из объектов можно выполнить способами, причем никакие способы выбора каждого из объектов не совпадают со способами выбора любого другого объекта, то выбор «или , или , …, или » можно произвести способами.

Правило умножения

Пример 1. Пусть в урне различных между собой шаров. Сколькими способами можно двумя взятыми из урны шарами заполнить две ячейки, в каждую из которых помещается ровно один шар? Очевидно, первую ячейку можно заполнить способами. После заполнения первой ячейки в урне останется шар. Следовательно, вторую ячейку можно заполнить способом. Заметим, что с каждым из способов заполнения первой ячейки может совпасть любой из способов заполнения второй. Поэтому общее число способов заполнения двух ячеек равно .

Пример 2. Между пунктами А и В имеется 6 различных маршрутов, а между пунктами В и С – 4 маршрута. Каким числом различных маршрутов можно проехать из А через В в С? Искомое число маршрутов равно , так как, приехав из А в В одним из 6-ти маршрутов, можно выбрать для проезда из В в С любой из 4-х маршрутов.

Запишем теперь правило умножения в общем виде.

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

Выборки

Пусть имеется множество, состоящее из различных элементов , которое назовем генеральной совокупностью. Произвольное упорядоченное подмножество из элементов, входящих в генеральную совокупность, назовем выборкой объемом . Наглядно выборку объемом можно представить как результат последовательных случайных извлечений (выбора) элементов из урны, содержащей все элементы генеральной совокупности. Выбор может выполняться с возвращением и без возвращения. При выборе с возвращением извлеченный элемент после обследования вновь возвращается в генеральную совокупность, и поэтому один и тот же элемент может быть выбран несколько раз. В случае выбора без возвращения однажды выбранный элемент удаляется из генеральной совокупности, так что выборка не содержит повторяющихся элементов. Очевидно, что при выборе с возвращением объем выборки никак не связан с объемом генеральной совокупности, а при выборе без возвращения всегда .

Дата добавления: 2015-11-30