2 клетки и 4 краски. Сколько спсособов раскраски?

Приветствую.

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

Задача

Есть две клетки и четыре цвета, которыми можно закрасить данные клетки. Будем считать, что цвет "расходуется" при покраске, и один и тот же цвет нельзя использовать дважды. Сколько существует способов раскраски?

Визуализация формулировки задачи.

Для ясности изобразим некоторые из возможных способов покраски.

Некоторые варианты покраски.

Как подсчитать общее число?

Для первой клетки можно использовать любую из 4 красок. Для каждого выбора краски для первой клетки можно выбрать любую из оставшихся трёх красок для второй клетки. Всего возможностей 4*3=12. Они все показаны ниже:

Все возможные раскраски. Отметим, что число возможностей равнялось бы 16 (4*4), если бы можно было использовать один и тот же цвет для обеих клеток.

Размещения

С точки зрения математики данная задача – задача о размещениях. Т.е. здесь нужно найти количество способов "разместить" четыре краски в двух клетках.

Размещением называется упорядоченное множество из k элементов, составленное из данных n элементов, причём k<n. При k=n размещения совпадают с перестановками.

Если проще, размещение – способ разместить n элементов внутри k ячеек, где k<n, причём каждая ячейка заполняется только одним элементом (например, размещение 11 студентов на 7 стульях; 15 машин в 11 гаражей и т.п.). Задача выше – яркий пример (в нём n=4 (краски), k=2 (клетки)).

Число размещений

Число размещений, содержащих k элементов и составленных из данных n элементов.

Число размещений обозначают буквой 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)). Формула доказана.

Подписывайтесь на канал, оставляйте комментарии и лайки.

Спасибо за внимание