Большинство комбинаторных задач решается с помощью двух основных правил - правила суммы и правила произведения.
Правило суммы. Если некоторый объект A можно выбрать n способами, а другой объект B можно выбрать m способами, то выбор "либо A, либо B" можно осуществить n+m способами.
Правило произведения. Если объект А можно выбрать n способами, а после каждого такого выбора другой объект B можно выбрать (независимо от выбора объекта A) m способами, то пары объектов A и B можно выбрать n*m способами.
Перечислительная комбинаторика
К перечислительной комбинаторике относятся задачи поиска числа способов построения кортежей из элементов конечного множества, как с разными, так и одинаковыми. Простейшими кортежами являются перестановки, размещения и сочетания.
Пусть A – конечное множество, состоящее из n элементов, т.е. мощность этого множества │A│ = card A = n.
Перестановки
Перестановкой элементов множества A называется любой кортеж <a1, a2, ..., an> состоящий из n различных элементов множества A.
Pn =n!
Перестановки с повторениями
Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n1, n2, ... ,nk) из элементов (a1, a2, ... ,ak) называется кортеж длиной n = n1 + n2 + ...+ nk, в который a1 входит n1 раз, a2 входит n2 раз и т.д. Число таких перестановок
Размещения
Кортежи длины k (1≤k≤n), состоящие из различных элементов n-элементного множества A (кортежи отличаются один от другого как самими элементами, так и их порядком), называются размещениями из n элементов множества A по k. Число таких
размещений обычно обозначается А из Н по К(буква A от французского слова arrangement -размещение)
Упорядоченное размещение
Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два размещения назовем равными, если в каждом ящике содержится одна и та же последовательность объектов. Размещения такого типа называются упорядоченными размещениями п объектов по m ящикам. Обозначим число таких упорядочений через |m|^n
Сочетания с повторениями