Элементы комбинаторики

Комбинаторика – это наука о том, сколько различных комбинаций, удовлетворяющих определенным условиям, можно составить на элементах конечного множества.

Чтобы проводить комбинаторные рассуждения необходимо знать основные правила, схемы и формулы комбинаторики.

Пусть X – конечное множество, а – количество элементов в нем. Будем в этом случае говорить, что объект x из X может быть выбран n способами.

«Правило суммы»

Пусть , , … , – попарно непересекающиеся множества, т.е. при . Тогда, очевидно, выполняется равенство

.

Этот факт в комбинаторике называется «правилом суммы».

«Правило произведения»

«Если объект x может быть выбран m способами и после каждого из таких выборов объект y в свою очередь может быть выбран n способами, то выбор упорядоченной пары может быть осуществлен mn способами».

Доказательство. Воспользуемся правилом суммы. Пусть – множество элементов, из которых выбирается объект x. Для каждого рассмотрим множества , в которых первая компонента совпадает с . Множества попарно не пересекаются и . Тогда множество всех пар есть и (по правилу суммы)



Замечание. В общем случае правило произведения формулируется следующим образом: «Если объект может быть выбран способами, после чего объект может быть выбран способами и для любого i, где , после выбора объектов объект может быть выбран способами, то выбор упорядоченной последовательности может быть осуществлен способами».

Доказательство проводится методом математической индукции.

Размещения и сочетания

Определение 1. Набор элементов ,  ,…,  из множества называется выборкой объема r из n элементов (или, иначе, -выборкой).

Выборка называется упорядоченной, если порядок следования элементов в ней задан.

Замечание. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

Если порядок следования элементов не является существенным, то выборка называется неупорядоченной.

В выборках могут допускаться или не допускаться повторения элементов.

Определение 2. Упорядоченная -выборка, в которой элементы могут повторяться, называется -размещением с повторениями.

Определение 3. Упорядоченная -выборка, элементы которой попарно различны, называется -размещением без повторений (или, иначе, -размещением).

Замечание. -размещения без повторений называются перестановками множества X.

Определение 4. Неупорядоченная -выборка, в которой элементы могут повторяться, называется -сочетанием с повторениями.

Определение 5. Неупорядоченная -выборка элементы, которой попарно различны, называется -сочетанием без повторений (или, иначе, -сочетанием).

Замечание. Любое -сочетание можно рассматривать, как r-элементное подмножество n-элементного множества.

Пример 1. Пусть , т.е. . Найти какое-либо -сочетание без повторений.

Ответ: например, .

Пример 2. Пусть . Найти все -размещения и -сочетания (с повторениями и без повторений).

Ответ:

а)  – множество всех -размещений с повторениями (9 упорядоченных пар);

б)  – множество всех -размещений без повторений (6 упорядоченных пар);

в)  – множество всех -сочетаний с повторениями (6 неупорядоченных пар);

г)  – множество всех -сочетаний без повторений (3 неупорядоченные пары, являющиеся двухэлементными подмножествами трехэлементного множества).

Число -размещений с повторениями будем обозначать , а без повторений – через . Число перестановок n-элементного множества будем обозначать через (т.е. ). Число -сочетаний с повторениями будем обозначать через , а без повторений – через .

Теорема 1. .

Доказательство. Каждое -размещение с повторениями является упорядоченной последовательностью длины r, причем каждый элемент этой последовательности может быть выбран n способами. По правилу произведения получаем



Теорема 2. .

Доказательство. Каждое -размещение без повторений является упорядоченной последовательностью длины r, члены которой попарно различны и выбираются из множества с n элементами. Тогда первый член этой последовательности может быть выбран n способами, после каждого выбора первого члена последовательности второй член может быть выбран способами и так далее до r-го члена последовательности, который может быть выбран способами. По правилу произведения получаем



Следствие.

Теорема 3. .

Доказательство. Каждое -сочетание без повторений можно упорядочить r! способами. Объединение получаемых таким образом попарно непересекающихся множеств -размещений без повторений для всевозможных -сочетаний без повторений, даст все -размещения без повторений. Тогда (здесь суммирование производится по всевозможным -сочетаниям без повторений), т.е. . Отсюда



Теорема 4. .

Доказательство. Каждому -сочетанию В с повторениями, составленного из элементов множества поставим в соответствие такой вектор длины ( ), состоящий из r единиц и ( ) нулей, что число единиц находящихся между -м и i-м нулями, где , будет равно числу элементов , входящих в сочетание В. Число единиц, стоящих перед первым нулем равно числу элементов , а число единиц, стоящих после -го нуля равно числу элементов , входящих в сочетание В.

Это соответствие между В и будет взаимно однозначным. Поэтому, чтобы подсчитать количество -сочетаний с повторениями, достаточно подсчитать количество векторов .

Количество векторов равно числу r-элементных подмножеств (номеров единичных компонент в этих векторах) ( )-элементного множества (всех номеров компонент в этих векторах), т.е. числу -сочетаний без повторений:



Пример 3. Пусть , , , – -сочетание с повторениями, тогда .

Пример 4. Пусть , , , , тогда .