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

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

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

Пусть – попарно непересекающиеся множества, т.е. , .

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

.

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

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

Тогда упорядоченные пары описываются декартовым произведением:

.

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

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

Размещения

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

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

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

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

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

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

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

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

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

.

Число размещений из n элементов по m без повторений обозначают , а с повторениями . Например, .

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

.

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

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

.

Разделим и умножим эту формулу на , получим

;

.

Сочетания

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

Пример: .

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

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

Число сочетаний из n по m -элементам обозначают , а с повторениями , например , .

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

;

откуда

. (1.3)

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

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

 

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

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

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

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

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

 

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

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

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

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

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

.

 

2. Найти число решений уравнения в неотрицательных целых числах.

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

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

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

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

Р_n = n!.

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

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

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

1. .

2. .

3.

4. – свертка Вандермонда.