В математике важную роль играют комбинаторные задачи, связанные с подсчетом числа элементов различных конечных множеств, перебором конечного числа вариантов и т.п.
Одним из основных правил, которые применяются при решении таких задач, является правило произведения.
Пусть элемент можно выбрать способами, а элемент ― способами, тогда пару элементов можно выбрать способами. Это правило следует из определения декартова произведения двух множеств.
З а м е ч а н и е: Это правило распространяется и на множеств.
Приведем примеры решения комбинаторных задач с помощью правила произведения.
З а д а ч а 1. Пусть дан упорядоченный набор длины , т.е. , каждый элемент которого может принимать одно из двух значений (например, 0 или 1). Требуется узнать, сколько будет таких наборов (их называют двоичными). Для решения построим клетку с ячейками, каждую из которых можно заполнить двумя способами (например, 0 или 1; или «и» и «л» и т.п.):
2 способа | 2 способа | 2 способа | … | 2 способа |
… | n |
Следовательно, число двоичных наборов длины n равно . В частности, таблица истинности для логической формулы с n высказывательными переменными имеет строк, так как каждая строка таблицы представляет собой двоичный набор длины n.
|
|
З а д а ч а 2. Пусть дано множество . Нужно определить число всех его подмножеств . Пусть . Тогда этому подмножеству можно поставить в соответствие двоичный набор длины n, в котором на i -ом месте стоит 1, если , либо 0, если . Тогда .
Перестановки, размещения и сочетания
Перестановки. Одна из наиболее распространенных комбинаторных задач такова: сколькими способами можно переставить элементы некоторого конечного множества? Например: сколько 9-значных чисел с различными цифрами можно составить из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9?
При каждой перестановке n- элементного множества образуется упорядоченный набор длины n, все элементы которого различны. Число всех возможных перестановок в данном множестве совпадает с числом всех таких наборов.
О п р е д е л е н и е 4: Перестановкой из n элементов называется упорядоченный набор длины n с различными элементами, взятыми из некоторого n- элементного множества.
Число перестановок из n элементов обозначают Рn. Выведем формулу для вычисления Рn.
Пусть некоторое множество М состоит из n элементов. Рассмотрим произвольную перестановку элементов этого множества, то есть упорядоченный набор (), где аi ∈ М. Элемент а1 в этом наборе можно выбрать n различными способами (взять любой элемент из множества M); элемент а2 выбирается n-1 способами (так как один элемент уже использован для а1, а элементы в перестановке не повторяются); а3 выбирается n-2 способами («заняты» два элемента) и т.д. Последний элемент аn можно выбрать только одним способом. По правилу произведения, будет всего указанных наборов.
|
|
Произведение , где n ― натуральное число, большее 1, называется n-факториалом и обозначается n! Дополнительно полагают: 1!=0!=1. Таким образом, .
Получена формула числа перестановок из n элементов. Применяя эту формулу, можно, в частности, получить, что из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 можно составить 9!, то есть 362880 9-значных чисел с различными цифрами.
Размещения. Другой важный тип комбинаторной задачи можно продемонстрировать на следующем примере: сколькими способами из 10 учебных предметов можно составить расписание занятий на один день, включив в него 4 различных предмета? Очевидно, что один вариант расписания может отличаться от другого как предметами, так и порядком их следования. Поэтому данную задачу можно сформулировать так: сколько существует упорядоченных наборов длины 4 с различными элементами, взятыми из 10-элементного множества? Число всех таких наборов называется числом размещений из 10 элементов по 4.
О п р е д е л е н и е 5: Размещением из n элементов по m (m≤n) называется упорядоченный набор длины m различными элементами, взятыми из некоторого n -элементного множества.
Еще раз напомним, что упорядоченные наборы с одними и теми же элементами, но разным порядком их следования считаются различными.
Обозначим число размещений из n элементов по n через и выведем формулу для вычисления .
Рассмотрим n -элементное множество M и произвольный упорядоченный набор (), где ai ∈M для всех i, i = =1,2,...,m. Элемент а1 выбирается n различными способами; a2 выбирается n-1 способами и т.д. Последний элемент аm можно выбрать
(n - (m - 1)), то есть (n - m + 1) способами. По правилу произведения, имеется всего указанных наборов.
Искомая формула имеет вид:
(1)
Заметим, что произведение в правой части состоит в точности из m множителей. Это облегчает применение формулы.
Вернемся к задаче о расписании. Число всех вариантов расписания можно посчитать по формуле (1): .
Имеет место другая формула для :
Для ее вывода достаточно преобразовать правую часть формулы (1).
Сочетания. Рассмотрим теперь такую задачу: сколькими способами можно из 10 учебных предметов выбрать 4 для составления расписания на день? Заметим, что в этой задаче, в отличие от задачи предыдущего пункта, не требуется составлять расписание, то есть упорядочивать предметы. Нужно узнать, сколькими способами из множества, состоящего из 10 элементов, можно выбрать 4-элементное подмножество (а не упорядоченный набор). Число таких подмножеств называют числом сочетаний из 10 элементов по 4.
О п р е д е л е н и е 6: Сочетанием из n элементов по m
(m≤n) называется m -элементное подмножество n -элементного множества.
Подчеркнем, что в данном случае не различаются подмножества, состоящие из одних и тех же элементов, в каком бы порядке эти элементы не перечислялись.
Число сочетаний из n элементов по m обозначают . Выведем формулу для нахождения этого числа.
Пусть дано множество из n элементов. Возьмем произвольное m -элементное подмножество этого множества и составим из него все возможные упорядоченные наборы. Их будет m! Проделав такое действие с каждым подмножеством, получим множество всех упорядоченных наборов длины m, то есть всех размещений из n элементов по m. Их число .
Таким образом, . Отсюда: .
Иногда последнюю формулу записывают по-другому:
.
Применив полученную формулу, найдем :
.
Число 210 дает ответ задачи, поставленной в начале этого пункта.