Комбинаторика. 
Элементы теории вероятностей

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

Комбинаторика происходит от латинского слова «combinatio» — соединение.

Группы, составленные из каких-либо предметов (например, кубиков, букв, чисел и т. п.), называются соединениями (комбинациями, подмножествами, выборками). Предметы, из которых состоят соединения, называются элементами.

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

Условно комбинаторика делится на две части:

Пусть имеется n различных элементов а₁, а₂, …а_n. Каждый из этих элементов в комбинацию может войти один раз. Это комбинаторика без повторений.

Дано n типов элементов: «мешок» элементов типа а₁, типа а₂, типа а₃ и т. д. В каждую комбинацию может войти несколько элементов одного типа. Либо имеется n различных элементов а₁, а₂, …а_n. При этом элемент после выбора снова возвращается в группу. Это комбинаторика с повторениями.

Важнейшими характеристиками комбинаций являются: 1) состав, входящих в них элементов; 2) порядок вхождения элементов в комбинацию.

Различают три типа соединений: размещения, перестановки, сочетания.

При решении задач на нахождение количества комбинаций необходимо:

определить тип элементов, входящих в комбинацию;

определить, что нас интересует в комбинации: состав элементов, порядок их вхождения в комбинацию или и то, и другое;

определить тип соединения и выбрать соответствующую формулу для расчета.

При решении задач на подсчет числа комбинаций в комбинаторике применяются два правила: правило сложения и правило умножения.

Правило сложения: Если элемент А₁ может быть выбран n₁ способом, элемент А₂ — другими n₂ способами, А₃ — отличными от первых двух n₃ способами и т. д., А_к -n_k способами, отличными от первых (k-1), то выбор одного из элементов: или А₁, или А₂, или А₃, … или А_к может быть осуществлен n₁+n₂+n₃+…+А_к способами.

Правило произведения: Если элемент А₁ может быть выбран n₁ способами, после каждого такого выбора А₂ может быть выбран n₂ способами и т. д., после каждого (k-1) элемент А_k может быть выбран n_k способами, то выбор элементов А₁, А₂,…, А_к в указанном порядке может быть осуществлен n₁n₂…n_k способами.

Размещения.

Размещениями из n элементов по k в каждом называются такие комбинации, которые характеризуются и порядком и составом входящих в них элементов.

Обозначения и формулы вычисления.

— число размещений из n по k без повторений.

— число размещений из элементов n типов по k с повторениями.

Сочетания.

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

Обозначения и формулы вычисления.

где 0? k? n— число сочетаний из n по k без повторений.

— число сочетаний из элементов n типов по k с повторениями.

Перестановки.

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

Обозначения и формулы вычисления.

Число перестановок из n элементов это то же самое, что число размещений из n элементов по n в каждом, поэтому.

P_n = n?(n-1)?(n-2)…2?1= n! —число перестановок из n без повторений.

— число перестановок с повторениями из k₁ элементов первого типа, k₂ элементов второго типа, … k_n элементов n типа.

Замечание. Между размещениями, сочетаниями и перестановками можно установить связь по следующей формуле.

Геометрическое определение вероятности.

Пусть в результате испытания возможно бесконечное число исходов. При этом исходы несовместны и ни один из них не имеет преимущества перед другими. Для решения задачи о вероятности используется геометрическая интерпретация вероятности. В данном случае? представляет собой подмножество пространства R¹(числовой прямой), R²(плоскости), Rⁿ (n-мерного евклидова пространства). В пространстве R¹ в качестве подмножеств будем рассматривать лишь промежутки или их объединения, то есть подмножества, которые имеют длину, в пространстве R² — площадь, в R³ — объем и т. д.

Под мерой м (А) подмножества, А будем понимать его длину, площадь или объем в зависимости от того, какому пространству принадлежит ?. Будем считать, что пространство элементарных исходов? имеет конечную меру, а вероятность попадания «случайно брошенной» точки в любое подмножество? пропорциональна мере этого подмножества и не зависит от его расположения и формы.

Вероятностью события, А в этом случае называется число Р (А), равное отношению меры множества, А к мере множества ?:

Геометрическое определение вероятности сохраняет свойства, рассмотренные в классической схеме.

Правила сложения и умножения вероятностей. Зависимые и независимые события Вероятность суммы двух событий равна сумме вероятностей этих событий без вероятности их совместного наступления Р (А + В) = Р (А) + Р (В) — Р (АВ).

Для несовместных событий их совместное наступление есть невозможное событие, а вероятность его равна нулю, следовательно, вероятность суммы двух несовместных событий равна сумме вероятностей этих событий.

Правило сложения вероятностей справедливо и для конечного числа п попарно несовместных событий.

В случае нескольких совместных событий необходимо по аналогии с рассуждениями о пересечении двух совместных событий исключить повторный учет областей пересечения событий. Рассмотрим три совместных события.

Для случая трех совместных событий можно записать.

Р (А + В + С) = Р (А) + Р (В) + Р (С) — Р (АВ) — Р (АС) — Р (ВС) + Р (АВС).

Сумма вероятностей событий А₁, А₂, А₃ , …, А_n, образующих полную группу, равна 1

Р (А₁) + Р (А₂) + Р (А₃) + … + Р (А_n) = 1 или

События, А и В называются независимыми, если вероятность каждого из них не зависит от того, произошло или нет другое событие.

Вероятности независимых событий называются безусловными.

События А и В называются зависимыми, если вероятность каждого из них зависит от того произошло или нет другое событие. Вероятность события В, вычисленная в предположении, что другое событие А уже осуществилось, называется условной вероятностью.

Вероятность произведения двух независимых событий, А и В равна произведению их вероятностей Р (А В) = Р (А)Р (В).

События А₁, А₂, …, А_n (п > 2) называются независимыми в совокупности, если вероятность каждого из них не зависит от того, произошли или нет любые события из числа остальных.

Вероятность произведения двух зависимых событий, А и В равна произведению вероятности одного из них на условную вероятность другого или.

Вероятность события В при условии появления события А.

Если события А1, А2 ,…, Аn — зависимые в совокупности, то вероятность наступления хотя бы одного из них равна.

Вероятность появления хотя бы одного события из п независимых в совокупности равна разности между 1 и произведением вероятностей событий, противоположных данным,.