Приветствую.
Для лучшего понимания статьи рекомендуется прочитать предыдущие статьи о комбинаторике: (об энтропии, о комбинаторном правиле умножения, о перестановках).
Задача
Есть две клетки и четыре цвета, которыми можно закрасить данные клетки. Будем считать, что цвет "расходуется" при покраске, и один и тот же цвет нельзя использовать дважды. Сколько существует способов раскраски?
Для ясности изобразим некоторые из возможных способов покраски.
Как подсчитать общее число?
Для первой клетки можно использовать любую из 4 красок. Для каждого выбора краски для первой клетки можно выбрать любую из оставшихся трёх красок для второй клетки. Всего возможностей 4*3=12. Они все показаны ниже:
Размещения
С точки зрения математики данная задача – задача о размещениях. Т.е. здесь нужно найти количество способов "разместить" четыре краски в двух клетках.
Размещением называется упорядоченное множество из k элементов, составленное из данных n элементов, причём k<n. При k=n размещения совпадают с перестановками.
Если проще, размещение – способ разместить n элементов внутри k ячеек, где k<n, причём каждая ячейка заполняется только одним элементом (например, размещение 11 студентов на 7 стульях; 15 машин в 11 гаражей и т.п.). Задача выше – яркий пример (в нём n=4 (краски), k=2 (клетки)).
Число размещений
Число размещений обозначают буквой A, причём используют символы k и n в качестве индексов.
Докажем формулу
- Пусть есть n элементов и k ячеек (k<n). В первую ячейку можно поместить любой из n элементов. Всего возможностей n.
- Для каждого из выборов первого элемента для первой ячейки существует n-1 вариант выбора второго элемента для второй ячейки. Число возможностей растёт до произведения n*(n-1).
- Для каждого из n*(n-1) вариантов заполнения первых двух ячеек существует (n-2) возможности заполнения третьей ячейки. Общее число возможностей растёт до n*(n-1)*(n-2)
- <и так далее>
- Наконец, для каждой из n*(n-1)*(n-2)*...*(n-(k-2)) возможностей заполнения k-1 ячеек существует (n-(k-1)) вариантов заполнения k-той ячейки. Всего возможностей становится равным n*(n-1)*(n-2)*...*(n-(k-1)). Формула доказана.