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

Согласно классическому определению подсчет вероятности события сводится к подсчету числа благоприятных ему исходов. Делают это обычно комбинаторными методами.

Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций можно составить из заданных объектов.

Задачи комбинаторики отвечают на вопрос: «Сколькими способами?...»

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

Правило 1. Правило умножения (основной принцип).

Если из некоторого конечного множества первый объект (элемент ) можно выбрать способами и после каждого такого выбора второй объект (элемент ) можно выбрать способами, то оба объекта ( и ) в указанном порядке можно выбрать способами. (Этот принцип распространяется на случай трех и более объектов).

Пример 4. Сколько трехзначных чисел можно составить из цифр 1,2,3,4,5, если:

а) цифры не повторяются;

б) цифры могут повторяться?

Решение.

а) Имеется 5 различных способов выбора цифры для первого места (слева в трехзначном числе). После того, как первое место занято, осталось четыре цифры для заполнения второго места. Для заполнения третьего места остается выбор из трех цифр. Согласно правилу умножения имеется способа расстановки цифр.

б) Если цифры могут повторяться, то трехзначных чисел способов.

Правило 2. Правило суммы.

Если некоторый объект можно выбрать n способами, а объект можно выбрать способами, причем первые и вторые способы не пересекаются, то любой из указанных объектов ( или ) можно выбрать способами. (Это правило распространяется на любое конечное число объектов)

Пример 5. В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать для выполнения различных заданий двух девушек или двух юношей (двух студентов одного пола)?

Решение. По правилу умножения двух девушек можно выбрать способами, а двух юношей – способами. Следует выбрать двух студентов одного пола: двух студенток или двух юношей. Согласно правилу сложения таких способов выбора .

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

Существует две схемы выбора элементов ( ) из исходного множества:

1. Без возвращения (без повторений).

2. С возвращением (с повторением).

В первом случае выбранные элементы не возвращаются обратно; можно отобрать сразу все элементов или последовательно отбирать их по одному.

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