Теория

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

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

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

1). Правило суммы. Если из множества А элемент а1 можно выбрать n1 способами, элемент а2 – другими n2 способами и т.д., элемент аknк способами, отличными от предыдущих, то выбор элемента а1 , или элемента а2 , или и т.д. или элемента ак можно выполнить:

n = n1 + n2 + … + nk

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

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

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

Замечание 1. Правило суммы, сформулированное выше, относится к n1, n2, … , nk способам выбора элементов из множества А. Подчеркнём, что эти выборы являются взаимно исключающими. Кроме того, это правило может быть отнесено к различным конечным множествам, например, А={х1, х2, … , хm} и В={у1, у2, … , уn}, причём АВ=clip_image002. Применительно к этому случаю число способов выбора одного (произвольного) элемента из множества А clip_image004 В равно m + n.

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

Замечание 2. Применим это правило к конечным множествам А = {а1, а2, … , аm} и В = {b1, b2, … , bn}, содержащими соответственно m и n элементов. Пусть в начале из множества А выбирается один (произвольный) элемент, а затем из множества В – второй элемент. Тогда число возможных комбинаций вида ( аi, bj ), i =1, 2, … , m, j =1, 2, … , n, построенных в указанном порядке, т.е. аi Î А, bj Î В, равно mn. Смысл этого правила выясняется с помощью следующей таблицы.

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-ю способами (n1=5), второе действие – другими 3-мя способами (n2=3). Последовательное выполнение первого и второго действий – это переезд из А в С через В. По правилу произведения общее число способов перехода из А в С равно n = n1 n2 = = 5 ∙ 3 = 15.

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

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

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

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

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

или

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

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

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

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

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

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

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

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

Сclip_image019 = clip_image021 или Сclip_image019[1] = clip_image023. (1.3)

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

Сclip_image019[2] = Сclip_image025 (m clip_image027 n), (1.4)

Cclip_image029 + Cclip_image031 + Cclip_image033 + … + Cclip_image006[7] = 2n,

Сclip_image006[8] = Cclip_image036 + Cclip_image038 (1 < m < n).

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

(а + b)n = Cclip_image042[1]anb0 + Cclip_image048an-1b + … + Cclip_image050a0bn.

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

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

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

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

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

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

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

Рn = Аclip_image050[1] = clip_image067 = clip_image069 = 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 = 3! =1 ∙ 2 ∙ 3 = 6.

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

Пермь Питер Пятигорск