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

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

Размещениями из n элементов по m называют упорядоченные подмножества n -элементного множества, состоящие из m элементов. Число всех размещений из n элементов по m определяется по формуле

.

Из определения видно, что размещения различаются как самими элементами (хотя бы одним элементом), так и порядком этих элементов.

Например, необходимо вычислить, сколькими способами можно из бригады в 8 человек выбрать бригадира и мастера. При решении этой задачи следует применять формулу числа размещений, так как группы типа: Иванов – бригадир, Петров – мастер и Иванов – мастер, Петров – бригадир – различны. Искомое количество способов равно .

Размещения из n элементов по n называют перестановками из n элементов. Очевидно, что различные перестановки отличаются между собой только порядком элементов. Число перестановок подсчитывается по формуле (по определению )

=

Если из всех размещений из n элементов по m отобрать только те, которые отличаются хотя бы одним элементом (порядок неважен), то получатся подмножества, называемые сочетаниями. Число сочетаний из n элементов по m вычисляется по формулам

, или .

Например, необходимо вычислить, сколькими способами можно выбрать 5 чисел из 36 в карточке "Спортлото", чтобы 3 числа были "счастливыми". Из условия следует, что выбор трех "счастливых" чисел должен быть из числа пяти "счастливых", и каждый такой набор должен сочетаться с двумя "несчастливыми", выбранными из оставшегося 31-го "несчастливого" числа. Таким образом, искомое количество способов равно (по правилу произведения), так как очевидно, что порядок выбора чисел непринципиален.

Размещениями с повторениями называют упорядоченные последовательности, составленные из n элементов по m в каждой, где некоторые элементы (или все) могут быть одинаковы. Число размещений с повторениями равно .

Например, необходимо вычислить, сколькими способами можно распределить 7 пассажиров лифта по 4 этажам.

Очевидно, что на каждом из 4 этажей может выйти любое количество пассажиров, а общее число способов равно числу размещений с повторениями из 4 элементов по 7: .

Пусть размещения с повторениями содержат n элементов и при этом элемент повторяется раз; элемент – раз;..., элемент – раз (). Такие упорядоченные последовательности называют перестановками с повторениями. Их число

= .

Если опыт состоит в выборе с возвращением m элементов множества, содержащего n элементов, но без последующего упорядочения, то различными исходами такого опыта будут всевозможные m -элементные наборы, отличающиеся составом. При этом отдельные наборы могут содержать повторяющиеся элементы. Получающиеся в результате данного опыта комбинации называют сочетаниями с повторениями. Их число

= .

Например, в кондитерской имеется 7 видов пирожных. Сколько различных наборов по 4 пирожных можно составить? Очевидно, что в данном случае следует использовать формулу числа сочетаний с повторениями .

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

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

Дата добавления: 2014-11-18