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

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

Основное правило комбинаторики (правило умножения) состоит в следующем: пусть требуется выполнить одно за другим К действий, при этом 1-е действие можно выполнить n1 способами, 2-е – n2 способами,…,к-е – nК способами. Тогда все K действий вместе могут быть выполнены n1·n2·…·nК способами.

Пример 12. Сколько четырехзначных чисел можно составить из цифр 0,1,2,3,4,5, если 1) ни одна из цифр не повторяется более одного раза; 2) цифры могут повторяться; 3) числа должны быть нечетными.

Решение. 1). Первой цифрой числа может быть любая из 1,2,3,4,5. Если первая цифра выбрана, то вторая может быть выбрана 5 способами, третья– 4 способами, четвертая–3 способами. Следовательно, общее число способов составления четырехзначных чисел с неповторяющимися цифрами в них равно 5·5·4·3=300.

2). Здесь первая цифра числа также может быть выбрана 5 способами. Для каждой из последующих цифр возможен один из шести случаев: 0,1,2,3,4,5. Следовательно, общее число способов равно 5·6 =1080.

3). Число нечетных чисел равно 5·6·6·3=540.

Для нас будут полезны такие типы соединений как: размещения, перестановки, сочетания.

1. Размещениями из n элементов по m элементов называют соединения, состоящие из m элементов, взятых из данных n элементов и отличающихся друг от друга или самими элементами или их порядком. Иными словами – это упорядоченные m – элементные подмножества множества, состоящего из n элементов. Число размещений из n элементов по m элементов обозначается символом и вычисляется по формуле

. Пусть, например, имеются буквы а, b, c. Упорядоченные двумерные подмножества этого множества букв имеют вид ab, ac, ba, bс, ca, cb, их число равно

2. Перестановки – это размещения при m = n. Число перестановок, следовательно, вычисляют по формуле . Из трех букв a, b, c можно составить следующие перестановки: abc, acb, bac, bca, cab, cba, число перестановок равно

3. Сочетаниями из n элементов по m элементов называют m – элементные соединения, взятые из данных n элементов и отличающиеся друг от друга хотя бы одним элементом. Иначе говоря, это m – элементные неупорядоченные подмножества множества, состоящего из n элементов. В отличие от размещений порядок элементов в сочетаниях не учитывается. Число сочетаний из n элементов по m элементов обозначается символом и вычисляется по формуле . Так, из трех букв a, b, c можно составить такие сочетания по две буквы: ab, ac, bc, число таких сочетаний равно При вычислениях, когда число m больше половины числа n, полезна формула .

4. Размещениями с повторениями из n элементов по m элементов называются соединения по m элементов, причем каждый из m элементов может быть любым из n элементов. Число размещений с повторениями обозначается символом и вычисляется по следующей формуле: Так, из трех букв a, b, c можно составить такие размещения с повторениями по две буквы: аа, ab, ac, ba, bb, bc, ca, cb,cc, тогда

5. Перестановками с повторениями из n элементов, среди которых имеется элементов первого типа_, элементов второго,…, элементов k-го типа, при этом , называются соединения, содержащие все данные n элементов с указанными числами повторений одинаковых элементов. Все эти соединения отличаются друг от друга только порядком элементов. Число перестановок из n элементов по k элементов с заданными числами повторений обозначается символом и находится по формуле: . Так, число различных слов, которые можно получить перестановкой букв в слове мама, , вот эти слова: мама, амма, маам, аамм, ммаа, амам.

Отметим, что если k = 2, то среди n элементов элементов первого типа и элементов второго типа , следовательно, . В этом случае вместо обозначения часто используется обозначение .

Могут быть и сочетания с повторениями. Число сочетаний с повторениями вычисляется по формуле Из букв a, b, c можно составить такие сочетания с повторениями: aa, ab, ac, bb, bc, cc, тогда

Пример 13. По к воздушным целям запускается р ракет, . Каждая ракета независимо от других выбирает себе цель. Выбор любой цели равновозможен. Найти вероятность, что ракеты выберут разные цели – событие А.

Решение. Здесь , так как каждое размещение ракет по целям есть р – элементное соединение, в котором для каждой ракеты выбирается любая из к целей. Число , так как если рассмотреть благоприятные событию A исходы, то получим схему: первая ракеты выбрала одну из к целей, для второй ракеты остается выбор любой из (к-1) оставшихся целей, для третьей – выбор из (к-2) оставшихся и т.д. Отсюда

.

Пример 14. Две радиостанции могут работать на одной из трех фиксированных частот каждая. Найти вероятность того, что при одновременном и независимом выходе в эфир они будут работать на различных частотах – событие А.

Решение. Независимый выход в эфир здесь означает, что каждая станция выбирает себе частоту работы независимо от того, какие частоты выбрала себе другая. Общее число исходов здесь вычисляется по формуле , так как каждая станция может выбрать одну из трех частот независимо от другой. Число (см. предыдущий пример) .

Пример 15. Пусть требуется разместить n различных частиц по к ячейкам (к<n) так, чтобы в первой ячейке было частиц, во второй – , и т.д., в к-й ячейке – частиц. Каким числом способов это можно сделать?

Решение. Число исходов опыта можно найти по правилу умножения. В первую ячейку частицы можно разместить способами, во вторую – способами, и т.д., в к-ю ячейку – способами. Тогда

(см. также определение перестановок с повторениями).

Пример 16. Девять человек выбирают 3 различные экскурсии независимо друг от друга. Выбор каждой экскурсии равновозможен. Найти вероятность, что каждую экскурсию выберет одинаковое число экскурсантов – событие А.

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

Пример 17. Партия из S деталей содержит R бракованных. Для контроля из партии выбирают s деталей. Найти вероятность, что среди них будет r бракованных – событие A.

Решение. Общее число элементарных исходов , так как по условию задачи в соединениях по s элементов интерес представляют сами элементы, порядок следования элементов безразличен. Для вычисления числа m отметим, что r бракованных выбираются из общего числа R бракованных изделий, остальные (кондиционные) s–r выбираются из оставшихся S–R кондиционных. Число m тогда, согласно основному правилу (принципу) комбинаторики, равно .

Полученную формулу при различных значениях называют гипергеометрическим распределением.

Пример 18. Сколькими способами можно упорядочить множество так, чтобы каждое четное число имело четный номер.

Решение. Четных чисел в заданном множестве n, столько же мест с четными номерами, потому существует n! способов размещения n четных чисел по n местам с четными номерами. Каждому такому размещению отвечает ровно n! способов размещения n нечетных чисел по n местам с нечетными номерами. Потому общее число способов размещения n четных чисел по n местам с четными номерами равно .

Пример 19. Сколько целых неотрицательных решений имеет уравнение ?

Решение. Число таких решений совпадает с числом сочетаний с повторениями из n элементов по m элементам. Если обозначить число таких решений за р, то .

Пример 20. Сколько частных производных порядка m существует у бесконечное число раз дифференцируемой функции n переменных?

Решение. Предположим сначала, что все смешанные производные функции по одним и тем же аргументам равны между собой. Тогда, обозначив число частных производных порядка m у функции n переменных через р, получим равенство . Например, функция трех переменных имеет 6 различных частных производных второго порядка, так как Вот они:

.

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