Правила суммы и произведения в комбинаторике

Рассмотрим основополагающие правила комбинаторики – правила суммы и произведения.

Пусть Х – конечное множество, состоящее из n элементов x. Тогда говорят, что элемент x из X может быть выбран n способами и пишут Правила суммы и произведения в комбинаторике - student2.ru . Эта запись совпадает с записью мощности множества X.

Пусть Правила суммы и произведения в комбинаторике - student2.ru – попарно непересекающиеся множества, т.е. Правила суммы и произведения в комбинаторике - student2.ru , Правила суммы и произведения в комбинаторике - student2.ru .

Очевидно, что в этом случае

Правила суммы и произведения в комбинаторике - student2.ru .

Таково комбинаторное правило суммы. Для Правила суммы и произведения в комбинаторике - student2.ru оно формулируется следующим образом. Если объект x может быть выбран n способами из множества X, а объект y из непересекающегося с ним множества Y – другими m способами, то выбор «x или y» может быть осуществлён Правила суммы и произведения в комбинаторике - student2.ru способами.

Правило произведения для Правила суммы и произведения в комбинаторике - student2.ru формулируется следующим образом. Если объект x может быть выбран n способами и после каждого из таких выборов объект y в свою очередь может быть выбран m способами, то выбор упорядоченной пары – вектора Правила суммы и произведения в комбинаторике - student2.ru – может быть осуществлён Правила суммы и произведения в комбинаторике - student2.ru способами, например, Правила суммы и произведения в комбинаторике - student2.ru , Правила суммы и произведения в комбинаторике - student2.ru .

Тогда упорядоченные пары Правила суммы и произведения в комбинаторике - student2.ru описываются декартовым произведением:

Правила суммы и произведения в комбинаторике - student2.ru .

Выбор упорядоченной последовательности из k объектов вектора Правила суммы и произведения в комбинаторике - student2.ru может быть осуществлён Правила суммы и произведения в комбинаторике - student2.ru – способами, где ni – число способов выбора i-го объекта xi, i меняется от 1 до k (записывается: Правила суммы и произведения в комбинаторике - student2.ru ).

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

Размещения

Пусть задано некоторое конечное множество Правила суммы и произведения в комбинаторике - student2.ru – генеральная совокупность. Из элементов генеральной совокупности образуются выборки Правила суммы и произведения в комбинаторике - student2.ru , где Правила суммы и произведения в комбинаторике - student2.ru .

Выборки классифицируются следующим образом:

­ в зависимости от того, существенен порядок элементов выборки или нет, её называют упорядоченной или неупорядоченной;

­ в зависимости от того, могут или не могут элементы выборки повторяться, её называют выборкой сповторениями или выборкой без повторений.

Число элементов выборки называют её объёмом. Выборку объёма r называют r-выборкой.

Размещением из n элементов по m называется упорядоченная m-выборка из n-элементной генеральной совокупности.

Пример. Даны три буквы – a, b, c. Размещения из трех элементов (букв) по два в каждом:

(a, b), (b, a), (a, c), (c, a), (b, c), (c, b).

Если говорить о размещениях с повторениями, то к этому списку добавится еще три:

Правила суммы и произведения в комбинаторике - student2.ru .

Число размещений из n элементов по m без повторений обозначают Правила суммы и произведения в комбинаторике - student2.ru , а с повторениями Правила суммы и произведения в комбинаторике - student2.ru . Например, Правила суммы и произведения в комбинаторике - student2.ru .

Получим общие формулы для числа размещений. Если элементы размещения не могут повторяться, то число способов, каким можно выбрать каждый очередной элемент размещения, будет на единицу меньше, чем для предшествующего ему, а так как первый элемент размещения выбирается n способами, то с помощью правила произведения получаем формулу

Правила суммы и произведения в комбинаторике - student2.ru .

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

Число размещений можно еще вычислить по формуле

Правила суммы и произведения в комбинаторике - student2.ru . Правила суммы и произведения в комбинаторике - student2.ru

Разделим и умножим эту формулу на Правила суммы и произведения в комбинаторике - student2.ru , получим

Правила суммы и произведения в комбинаторике - student2.ru ;

Правила суммы и произведения в комбинаторике - student2.ru . Правила суммы и произведения в комбинаторике - student2.ru

Сочетания

Сочетанием из n элементов по m называют неупорядоченную m-выборку из n элементов генеральной совокупности. Выборки отличаются только составом элементов, порядок следования их не учитывается.

Пример: Правила суммы и произведения в комбинаторике - student2.ru .

Выпишем всевозможные сочетания из трех букв по две (без повторений): Правила суммы и произведения в комбинаторике - student2.ru .

Если говорить о сочетаниях с повторениями, то к этому списку добавится еще три: Правила суммы и произведения в комбинаторике - student2.ru .

Число сочетаний из n по m-элементам обозначают Правила суммы и произведения в комбинаторике - student2.ru , а с повторениями Правила суммы и произведения в комбинаторике - student2.ru , например Правила суммы и произведения в комбинаторике - student2.ru , Правила суммы и произведения в комбинаторике - student2.ru .

Выведем формулу для Правила суммы и произведения в комбинаторике - student2.ru . Всякое размещение можно получить как произведение сочетания на перестановку:

Правила суммы и произведения в комбинаторике - student2.ru ;

Правила суммы и произведения в комбинаторике - student2.ru

откуда Правила суммы и произведения в комбинаторике - student2.ru

Правила суммы и произведения в комбинаторике - student2.ru . (1.3)

Сочетания с повторениями

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

Пример. Пусть n=3, m=5. Исходное множество a, b, c – n=3. Сочетания с повторениями из пяти элементов, например:

aaabc – кодировка 1110101;

abbbb – кодировка 1011110;

ccccc – кодировка 0011111.

Заметим, что в кодирующей последовательности ровно Правила суммы и произведения в комбинаторике - student2.ru элементов Правила суммы и произведения в комбинаторике - student2.ru , m – единиц (столько, сколько элементов в сочетании) и Правила суммы и произведения в комбинаторике - student2.ru нулей (отделяющих друг от друга n наборов единиц, соответствующих n элементам исходного множества). Очевидно, что любой последовательности такого вида соответствует некоторое сочетание с повторениями из n по m.

Пример: n=3, m=5; a, b, c; последовательности 1110011 соответствует ааасс, а 0111110 – bbbbb.

Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из n по m и множеством последовательностей из m единиц и Правила суммы и произведения в комбинаторике - student2.ru нулей. Число этих последовательностей равно Правила суммы и произведения в комбинаторике - student2.ru или Правила суммы и произведения в комбинаторике - student2.ru . Это соответствие: Правила суммы и произведения в комбинаторике - student2.ru .

Примеры задач на сочетания с повторениями

1.Каким числом способов можно разместить n одинаковых шаров по k различным урнам?

Решение. Присвоим урнам номера от 1 до k. Будем считать, что, помещая шар в урну, мы присваиваем ему её номер. Тогда размещение шаров по урнам сводится к построению последовательности, в которой n элементов, и каждый из них принимает одно из k значений. Таким образом, ответ к задаче – Правила суммы и произведения в комбинаторике - student2.ru :

Правила суммы и произведения в комбинаторике - student2.ru . Правила суммы и произведения в комбинаторике - student2.ru

2. Найти число решений уравнения Правила суммы и произведения в комбинаторике - student2.ru в неотрицательных целых числах.

Решение. Задача опять сводится к числу распределений одинаковых шаров по различным урнам, если считать, что xi – количество шаров, помещаемых в i-ю урну, n – общее число шаров, k – общее число урн. Ответ: Правила суммы и произведения в комбинаторике - student2.ru .

Перестановки

Перестановки – это частный случай размещения, когда n=m, т.е. Правила суммы и произведения в комбинаторике - student2.ru .

В выборке элементы отличаются только порядком следования, состав элементов – одинаковый. Обозначается Pn. По формуле Правила суммы и произведения в комбинаторике - student2.ru при n=m (0!=1) число перестановок равно:

Рn=n!. Правила суммы и произведения в комбинаторике - student2.ru

Комбинаторные тождества

В ниже перечисленных соотношениях значения параметров предполагается такими, чтобы все биномиальные коэффициенты имели смысл. Если в формуле присутствует Правила суммы и произведения в комбинаторике - student2.ru , то Правила суммы и произведения в комбинаторике - student2.ru .

Имеют места следующие тождества:

1. Правила суммы и произведения в комбинаторике - student2.ru .

2. Правила суммы и произведения в комбинаторике - student2.ru .

3. Правила суммы и произведения в комбинаторике - student2.ru

4. Правила суммы и произведения в комбинаторике - student2.ru – свертка Вандермонда.

Наши рекомендации