Лекция 9.
Основные формулы вычисления вероятностей
Классическая вероятностная схема
Вероятность определена как числовая характеристика возможности появления случайного события. При этом предполагается, что условия эксперимента могут быть воспроизведены неограниченное число раз. Рассмотрим некоторый случайный эксперимент, для которого определено множество равновозможных элементарных исходов . Равновозможность исходов есть проявление симметрии случайного эксперимента.
Классической схемой, или схемой случаев, называется испытание, при котором число элементарных исходов конечно, и все они несовместны и равновозможны.
Пусть данный эксперимент имеет возможных исходов и все они равновозможны (имеют одинаковые шансы) и несовместны (никакие два из них не могут наступить одновременно). Вероятность
события
называется отношение числа благоприятных исходов
к общему числу несовместных равновозможных исходов
:
.
Это классическое определение вероятности удовлетворяет основным требованиям, предъявляемым к математическим определениям вероятностей, а именно, оно удовлетворяет аксиомам теории вероятности, а также позволяет определить вероятность событий a priori, т.е. не проводя экспериментов. Итак, чтобы пользоваться классическим определением вероятности, нужно уметь подсчитывать число благоприятных исходов и общее число исходов
. Раздел математики, в котором исследуются различные задачи на перебор, называется комбинаторикой. Кроме теории вероятностей комбинаторика используется в некоторых задачах экономики, биологии, теории вычислительных машин, теории автоматов и т.д.
При решении ряда теоретических и практических задач требуется из конечного множества элементов по заданным правилам составлять различные комбинации и производить подсчет числа всех возможных таких комбинаций. Такие задачи принято называть комбинаторными.
Правила суммы и произведения
Решение многих комбинаторных задач основывается на двух фундаментальных правилах, называемых, соответственно, правилами суммы и произведения.
Правило суммы выражает вполне очевидный факт: если и
– два непересекающихся конечных множества, то число элементов, содержащихся в объединении этих множеств, равно сумме чисел элементов в каждом из них.
Если обозначить число элементов конечного множества через
, то правило суммы запишется следующим образом:
, если
и
не имеют общих элементов.
Обычно правило суммы формулируют следующим образом: если элемент может быть выбран
способами, а элемент
– способами, то один из этих элементов можно выбрать
способами.
Обобщение правила суммы на любое число множеств не менее очевидно: если
– попарно непересекающиеся конечные множества, то
.
Задачи, которые можно решить применением одного лишь правила суммы, тривиальны. Для решения более сложных задач используется также и правило произведения.
Правило произведения может быть сформулировано следующим образом: если элемент может быть выбран
способами, при каждом выборе
элемент
может быть выбран
способами, при каждом выборе пары
элемент
может быть выбран
способами и т.д., и после каждого выбора
элемент
можно выбрать способами, то последовательность (
) из этих элементов в указанном порядке можно выбрать
способами.
Более корректно правило произведения можно сформулировать в виде теоремы.
Теорема. Пусть имеется ,
, групп элементов, причем
–я группа содержит
элементов,
. Выберем из каждой группы по одному элементу. Тогда общее число
способов, которыми можно произвести такой выбор, равняется
.
Доказательство. Теорема доказывается методом индукции.
Пусть . Обозначим через
различные значения элемента
, а через
– различные значения элемента
. Если выбрано значение
элемента
, то можно составить
различные пары, содержащие этот элемент. Это справедливо и для любого другого значения элемента
. Таким образом, всего можно составить
различные пары, т.е. для
правило выполняется.
Предположим, что оно выполняется для групп из элементов. Тогда любую группу (
) можно рассматривать как пару элементов
. Первый элемент этой пары, по предположению индукции, может быть выбран
способами; при любом из них элемент
может быть выбран
способами. Таким образом, число различных групп (
) будет равно
.
Ищете обращайтесь и найдете!