5. (Анализ) Комбинаторика. Элементы комбинаторики

По | 6 мая, 2022
комбинаторика

При решении задач на классическую вероятность приходится подсчитывать число исходов, благоприятствующих некоторому событию. Задачи такого рода называют комбинаторными, а сам раздел математики, занимающийся такими подсчётами, именуют «Комбинаторика». Иногда под комбинаторикой понимают более обширный раздел дискретной математики.

Комбинаторика. Правила комбинаторики

Большинство задач по ком решается с помощью двух основных правил:

Правило сложения. Пусть есть два множества объектов A = {a1, …, an} и B = {b1, …, bm}. Если два действия взаимно исключают друг друга, и одно из них можно выполнить n  способами, а другое m способами, то оба действия можно выполнить n+числом способов.

Пример: Пусть множество A состоит из десяти цифр, а множество B – из 33 букв русского алфавита. Тогда в силу правила сложения мы можем взять одну цифру или одну букву 43 способами.

Правило умножения. Пусть есть два множества объектов A = {a1, …, an} и B = {b1, …, bm}. Если количество способов выбрать один объект из A равно n, а количество способов выбрать один объект из B равно m , то количество способов выбрать сперва один объект из A, а
затем выбрать один объект из B равно n * m.

Как так получается? Давайте для множеств A = {a1, …, an} и B = {b1, …, bm} перечислим все последовательные способы выбора:

a1b1, a1b2, … a1bm,
a2b1, a2b2, … a2bm,

anb1, anb2, … anbm.


Как видите непосредственным перебором убеждаемся, что в этом наборе n * m элементов. Что нам это даёт? Помните классическое определение вероятности события? Так вот благодаря комбинаторике мы можем определить число исходов (m), благоприятствующих событию A и общее число исходов (n) опыта, не прибегая к реальным испытаниям. А это, в свою очередь, позволяет рассчитать вероятность осуществления интересующего нас события.

Сочетания, размещения и перестановки

Для подсчета n и m часто применяются следующие понятия и формулы комбинаторики:

  • Сочетания
  • Размещения
  • Перестановки

Рассмотрим множество объектов A = {a1, …, an} . Как можно извлечь из этого множества ровно m объектов? Для этого можно прибегнуть к следующим способам:

  1. Извлекать эти объекты последовательно (один за другим) без возвращения их обратно. Такое действие можно повторить m раз. Данному способу извлечения соответствует понятие комбинаторики: m размещения без повторений.
  2. Извлекать с возвращением. То есть извлечь один объект из множества A, затем вернуть его обратно. После этого извлечь следующий объект из того же множества, затем вернуть его обратно и т.д. Такое действие можно повторить m раз. Данному способу извлечения соответствует понятие комбинаторики: m размещения с повторениями.
  3. Извлекать без возвращения. То есть извлекаем сразу все m объектов, кучей без повторов (порядок не важен, но повторов быть не должно). Данному способу извлечения соответствует понятие комбинаторики: m сочетания без повторений.
  4. Извлекать неупорядоченно без возвращения k объектов, которые могут повторятся (порядок не важен, а повторы допустимы). Данному способу извлечения соответствует понятие комбинаторики: m сочетания с повторениями.

Комбинаторика. Факториал

Прежде чем перейти к подробному разбору понятий размещение и сочетание, необходимо сначала познакомимся с понятием «Факториал«. Это важно, так как факториал используется во формулах расчёта. Что же такое «Факториал«?

Факториал — это математическая функция, применяемая к неотрицательным целым числам, равная произведению всех натуральных чисел от 1 до числа, для которого она вычисляется 

факториал целого числа

Факториал обозначается следующим образом:

n!

,где n — это целое неотрицательное число, для которого вычисляется факториал.

Пример: 5! = 1*2*3*4*5 = 120, где 5! — это факториал числа 5

0! = 1

1! = 1

Общая формула факториала выглядит так:

n! = n * (n − 1)! = n * (n − 1) * (n − 2) * … ·* 2 * 1.

Если расписать вышеуказанный пример, то получим:

5! = 5 * (5-1)! = 5 * (5-1) * (5-2) * 2 * 1 = 5 * 4 * 3 * 2 * 1 = 120

Как видите нет ничего сложного. Вот небольшая таблица факториалов, чтобы не заниматься расчётом «вручную»:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000

Теперь, зная что такое факториал и как его вычислить, можно перейти к основным формулам комбинаторики, используемым в теории вероятностей.