Необходимые знания по комбинаторике
@honey_and_moneyДля подсчета вероятностей необходимо знать количество всех исходов, благоприятствующих и отрицательных.
Существует три базовых метода, выбор которых зависит от ситуации.
Давайте разберемся, как же эти ситуации различать:
- Перестановки
Если у вас есть фиксированное число элементов и вам надо узнать сколькими различными способами их можно переставить между собой, то надо пользоваться именно этим методом.
Число перестановок n элементов равно n! = 1 * 2 * 3 * ... * n
Приведу пример для ясности:
Есть цифры 1, 2 и 3
Вопрос: Сколько трёхзначных чисел можно составить из этих цифр?
Всего три цифры, следовательно число перестановок равно 3! = 1 * 2 * 3 = 6
И правда:
123, 132, 213, 231, 312, 321
Второй пример: Есть десятиместная скамейка, сколькими способами на неё можно посадить 10 человек?
Всего 10 человек, следовательно количество способов рассадки равно:
10! = 1 * 2 * ... * 9 * 10 = 3 628 800
Забыл указать важную деталь: в данных задачах предполагается, что все элементы разные, то есть все десять человек не могут быть абсолютно одинаковыми, иначе смысл задачи терялся бы, ведь рассадить 10 абсолютно одинаковых человек можно только одним способом, от их смены мест ничего не поменяется и комбинация останется прежней. Аналогично и с цифрами: Если было бы три цифры 2, то составить из них можно было бы только одно трёхзначное число.
Таким образом, задача: Сколько четырёхзначных чисел можно составить из цифр 1, 2, 3, 3; решается другим методом, обычные перестановки тут не помогут. Об этом методе расскажу позже.
2. Сочетания
Другой вид задачи: Вам надо выбрать из определенного количества элементов выбрать несколько элементов и посчитать сколькими способами это можно сделать.
(Важно! Количество выбираемых элементов меньше либо равно исходному количеству элементов)
Формула для подсчёта: C(m,n) = n!/((n-m)! * m!), где n - общее число элементов, а m - число выбираемых элементов
(Читается как "Цэ из эн по эм")
Приведу пример:
У нас есть три различных карандаша: Красный, синий и зеленый
Сколькими способами из данного набора можно выбрать два карандаша:
Применим формулу: С(2,3) = 3!/((3-2)! * 2!) = 3
Ответ: способами
Сочетания используются когда порядок выбираемых элементов не важен, то есть: Выбрали красный и синий карандаш, если выбрали бы синий и красный карандаш, то комбинация осталась бы прежней.
Когда порядок важен используется третий метод:
3. Размещения
Тоже самое что и сочетания, но важно в каком порядке выбираются элементы.
Соответственно и формула немного другая: A(m,n) = n!/(n-m)!
Приведу пример:
Даны цифры 1, 2 и 3
Сколько двузначных чисел можно составить из этих цифр?
Решение:
Если бы мы применили формулу для сочетаний, то в наших выбранных элементах числа 21 и 12 оказались бы одинаковыми, но это неверно.
Количество чисел равно 3!/(3-2)! = 2 * 3 = 6
С тремя базовыми методами закончили. Теперь возникает вопрос, как быть если в множестве элементов из которых что-либо выбирается некоторые элементы могут повторяться?
Приведу пример:
Есть книжная полка и 8 книг: 3 одинаковые книги, 4 одинаковые книги другого автора и ещё одна отличная от других книга. Сколькими способами можно расставить эти книги на полку?
Расставим книги по полке так, как написано в условии: Сначала три книги одного автора, потом четыре книги другого автора и еще одну книгу.
Очевидно, что если в этой расстановке менять местами первые три книги между собой, ничего не изменится - книги то одинаковые. Поэтому применение обычного метода перестановок не подходит.
Есть формула для перестановок с повторениями. Вот формула:
n!/(m! * k! * c! ...), где n - общее количество всех элементов,
m, k, c и т.д. - количество повторяющихся элементов (m - повторяющиеся элементы одного типа, k - другого и тому подобное).
То есть для нашего примера:
8!/(3! * 4!) = 280
Сочетания с повторениями:
Если вам надо выбрать несколько элементов из набора, в котором какие-то элементы повторяются, то этот способ для вас:
C(m, n + m - 1) = (n + m - 1)!/((n-1)! * m!), где n - количество групп, в которых элементы повторяются. m - сколько элементов надо выбрать.
Пример задачи:
Вы зашли в цветочный магазин и вам нужно купить 15 цветов. На выбор вам предлагают розы, тюльпаны и герберы в неограниченном количестве (важный критерий таких задач). Сколькими способами можно купить 15 цветов?
Решение:
n = 3, m = 15
C(15, 3 + 15 - 1) = 17!/(2! * 15!) = 8 * 17 = 136 способов
(Комбинации могут быть такими: все 15 роз, все 15 тюльпаны, все 15 герберы или 14 роз + 1 тюльпан и т.д.)
Если выбирать вам надо так, что важен порядок, то нужны размещения:
Размещения с повторениями:
Требования к задачи такие же как и в сочетаниях с повторениями, но добавляется то, что важен порядок выбираемых элементов (то есть комбинации AB и BA - разные)
В таком случае количество способов равно n^m (n в степени m), где n - количество групп элементов, m - количество выбираемых элементов.
Пример:
Вам надо придумать пин-код для банковской карты.
Пин-код состоит из четырёх цифр. На каждом из четырех мест могут быть любые цифры от 0 до 9.
Следовательно n = 10 (количество групп элементов, в нашем случае цифр, которые могут повторяться) m = 4 (количество позиций)
Количество пин-кодов равно 10^4 = 10000
Этих базовых методов достаточно для комфортной работы с вероятностями. Советую всем внимательно изучить каждый из этих шести методов. Для закрепления чуть позже опубликую завершающую статью по вероятности и примеры решения задач + задачи для самостоятельного решения.
t.me/honey_and_money - начни заниматься полезными вещами