Применение комбинаторики к вычислению классической вероятности

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

При решении многих комбинаторных задач часто используются два важных правила: правило суммы (сложения) и правило произведения (умножения).

1). Правило суммы. Если из множества А элемент а₁ можно выбрать n₁ способами, элемент а₂ – другими n₂ способами и т.д., элемент а_k – n_к способами, отличными от предыдущих, то выбор элемента а₁ , или элемента а₂ , или и т.д. или элемента а_к можно выполнить:

n = n₁ + n₂ + … + n_k

способами. (Союз «или» здесь является ключевым.)

Пример 1. В ящике 200 деталей, причём 130 из них первого сорта, 20 – второго, а остальные – третьего сорта. Сколькими способами можно извлечь из ящика одну деталь первого или второго сорта?

Решение. Деталь первого сорта может быть извлечена n₁ = 130 способами, второго сорта n₂ = 20 способами. По правилу суммы существует n₁ + n₂ = 130 + 20 = 150 способов извлечения одной детали первого или второго сорта.

Замечание 1. Правило суммы, сформулированное выше, относится к n₁, n₂, … , n_k способам выбора элементов из множества А. Подчеркнём, что эти выборы являются взаимно исключающими. Кроме того, это правило может быть отнесено к различным конечным множествам, например, А={х₁, х₂, … , х_m} и В={у₁, у₂, … , у_n}, причём А ∩ В=. Применительно к этому случаю число способов выбора одного (произвольного) элемента из множества А В равно m + n.

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

Замечание 2. Применим это правило к конечным множествам А = {а₁, а₂, … , а_m} и В = {b₁, b₂, … , b_n}, содержащими соответственно m и n элементов. Пусть в начале из множества А выбирается один (произвольный) элемент, а затем из множества В – второй элемент. Тогда число возможных комбинаций вида ( а_i, b_j ), i =1, 2, … , m, j =1, 2, … , n, построенных в указанном порядке, т.е. а_i Î А, b_j Î В, равно m∙n. Смысл этого правила выясняется с помощью следующей таблицы.

ai \ bj	b1	b2	b3	…	bj	…	bn
а1	(a1, b1)	(a1, b2)	(a1, b3)	…	(a1, bj)	…	(a1, bn)
а2	(a2, b1)	(a2, b2)	(a2, b3)	…	(a2, bj)	…	(a2, bn)
a3	(a3, b1)	(a3, b2)	(a3, b3)	…	(a3, bj)	…	(a3, bn)
…	…	…	…	…	…	…	…
ai	(ai, b1)	(ai, b2)	(ai, b3)	…	(ai, bj)	…	(ai, bn)
…	…	…	…	…	…	…	…
am	(am, b1)	(am, b2)	(am, b3)	…	(am, bj)	…	(am, bn)

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

Пример 2. Из одного объекта ( объекта А) в другой объект (объект В) ведут 5 дорог, а из объекта В в объект С ведут 3 дороги. Сколько путей, проходящих через В, ведут из А в С?

Решение. Первое действие – переезд из А в В, второе действие – переезд из В в С. Первое действие можно осуществить 5-ю способами (n₁=5), второе действие – другими 3-мя способами (n₂=3). Последовательное выполнение первого и второго действий – это переезд из А в С через В. По правилу произведения общее число способов перехода из А в С равно n = n₁ ∙ n₂ = = 5 ∙ 3 = 15.

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

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

В данном кратком изложении основ теории вероятностей в дальнейшем рассматривается только схема а) ‒ без возвращения и 3 вида комбинаций: размещения, перестановки, сочетания.

Размещение из n элементов по m элементов – это любое упорядоченное подмножество данного множества, содержащее m элементов. Иными словами – размещения – это выборки элементов, которые отличаются друг от друга либо составом элементов, либо порядком их расположения. Размещения обозначаются А (читается “А из n по m“). Из правила произведения следует:

А = n ∙ (n – 1) ∙ (n – 2) ∙ … ∙ (n – (m – 1)), (1.1)

или

А = , где n! = 1 ∙ 2 ∙ 3 ∙ … ∙ n, 1! = 1, 0! = 1. (1.2)

Формула (1.1) получается так. Для получения размещения А необходимо выбрать m элементов из множества с n элементами и упорядочить их в выборке с m местами. Для этого первый элемент можно выбрать n способами, т.е. на первое место в выборке можно поставить любой из n элементов. После этого второй элемент можно выбрать из оставшихся (n – 1) элементов (n – 1) способами и т.д., а для последнего m-го элемента остаётся n – (m – 1) способов. Следовательно, по правилу произведения всего существует n ∙ (n – 1) ∙ (n – 2) ∙ … ∙ (n – (m – 1)) способов выбора m элементов из данных n элементов. Таким образом, для размещения А получается формула (1.1). Формула (1.2) получается путем умножения числителя и знаменателя на (n – m)!, где

Пример 3. Из множества, состоящего из трёх элементов, обозначаемых a, b, c, составить размещения по два элемента.

Решение. Из трёх указанных элементов составляются следующие размещения: ab, ac, bc, ba, ca, cb. Получается число размещений 6. По формуле (1.1) также получаем А = 3 ∙ 2 = 6.

Замечание 4. В формуле (1.1) для размещений А входит m сомножителей, так что, например, А = 6 ∙ 5 ∙ 4 (n = 6, m = 3); А = 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 (n = 7, m = 5).

Сочетания из n элементов по m – это любое неупорядоченное подмножество, содержащее m элементов. Обозначается С (читается “С из n по m “).

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

Число сочетаний из n элементов по m вычисляется по формуле:

С = или С = . (1.3)

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

С = С (m n), (1.4)

C + C + C + … + C = 2ⁿ,

С = C + C (1 < m < n).

Формулу (1.4) рекомендуется использовать при вычислении сочетаний с выборкой, в которой m > . Числа C, C,…, C в этой формуле есть коэффициенты в разложении бинома Ньютона:

(а + b)ⁿ = Caⁿb⁰ + Ca^n-1b + … + Ca⁰bⁿ.

Пример 4. Составить различные сочетания из 3-х элементов по 2 элемента.

Решение. Пусть исходное множество есть {а, b, с}. Для выбранного множества получаются следующие комбинации – сочетания: (а, b); ( a, c); (b, c), т.е. составляются три комбинации. По формуле (1.3) получим С= Заметим, что здесь каждая пара полученных комбинаций (пар элементов) отличается только одним элементом.

Пример 5. В группе горных рабочих имеются 10 электриков и 3 разнорабочих. Сколькими способами можно сформировать бригаду, состоящую из 5 электриков и 2-х разнорабочих?

Решение. Электриков можно выбрать С= способами. Выбрать два разнорабочих из имеющихся трёх можно С==3 способами. Поэтому бригаду из пяти электриков и двух разнорабочих можно сформировать С ∙ С = 756 способами (по правилу произведения).

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

Р_n = n! (0!=1). (1.5)

Эта формула следует из определения перестановки:

Р_n = А = = = n!.

Пример 6. Составить различные перестановки из элементов А = {1, 5, 8} и подсчитать их число.

Решение. Из этих элементов можно составить следующие комбинации: (1,5,8), (1,8,5), (5,1,8), (5,8,1), (8,1,5), (8,5,1). По формуле (1.5) получим

Р₃ = 3! =1 ∙ 2 ∙ 3 = 6.

Замечание 5. Для обозначения перестановок используется латинская буква P с обязательным нижним индексом (не путать с обозначением вероятности).