Диск. Лекция 9. Лекция Комбинаторика. Размещения и сочетания

• Название: Лекция Комбинаторика. Размещения и сочетания
• Дата: 14.06.2021
• Размер: 47.28 Kb.
• Имя файла: Лекция 9.docx
• Тип: Лекция; #217143

Лекция 9. Комбинаторика. Размещения и сочетания

Цель: ознакомить студентов с основными комбинаторными формулами.

Структура лекции:

1. Упорядоченные и неупорядоченные выборки.

2. Сочетания и размещения.

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

Наиболее часто применяются в комбинаторике при доказательствах два правила: суммы и произведения.

Пусть Х конечное множество, состоящее из n элементов; тогда говорят, что объект х из Х может быть выбран n способами и пишут Х=n.

Если Х₁, …, Х_n – попарно непересекающиеся множества, т.е. Х_i Х_j= при i  j, то

- это правило суммы.

Для k=2 оно может быть сформулировано так: если объект х может быть выбран m способами, а у - другими n способами, то выбор "либо х, либо у" может быть осуществлен m+n способами (выборы элементов х и у взаимно исключены).

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

В общем случае, если объект х₁ может быть выбран n₁ способами, после чего объект х₂ может быть выбран n₂ способами и для любого 2 i  m-1 после выбора объектов х₁, х₂, …, х_i объект х_i+1 может быть выбран n_i+1 способами, то выбор упорядоченной последовательности из m объектов (х₁, х₂, …, х_m) может быть осуществлен n₁  n₂ … n_m способами.

Набор элементов х_i1, …, х_ir из множества Х={х₁, …, х_n} называется выборкой объема r из n элементов, или (n, r) - выборкой.

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

В выборках могут допускаться или не допускаться повторения элементов. Упорядоченная (n, r) - выборка, в которой элементы могут повторяться, называется (n, r)-размещением с повторениями; если все элементы упорядоченной (n, r)-выборки попарно различны, то она называется (n, r)-размещением без повторений, или просто (n, r)-размещением.

(n, n)-размещения без повторений называются перестановками множества Х.

Неупорядоченная (n, r)-выборка, в которой элементы могут повторяться, называется (n, r)-сочетанием с повторениями. Если элементы неупорядоченной (n, r)-выборки попарно различны, то она называется (n, r)-сочетанием без повторений, или просто (n, r)-сочетанием. Заметим, что любое (n, r)-сочетание можно рассматривать как r-элементное подмножество n-элементного множества.

Например, пусть Х={1, 2, 3}.

1) (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) - (3, 2)-размещения с повторениями;

2) (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) - (3, 2)-размещения без повторений;

3) (1, 2, 3), (1, 3, 2), (3, 2, 1), (2, 1, 3), (3, 1, 2), (2, 3, 1) - перестановки множества Х;

4) {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3} - (3, 2)-сочетания с повторениями;

5) {1, 2}, {1, 3}, {2, 3} - (3, 2)-сочетания без повторений.

Число (n, r)-размещений с повторениями обозначают , без повторений . Число перестановок n-элементного множества обозначается P_n (т.е. P_n = ). Число (n, r)-сочетаний с повторениями обозначается , а без повторений - .

Утверждение 1. = n^r.

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

(В частности, это соотношение определяет количество различных чисел, записанных в r позициях, в системе счисления с основанием n).

Утверждение 2. = n (n-1)(n-2) … (n-r+1) = , при r  n и =0, r > n.

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

Следствие

= P_n = n (n - 1) … (n – n + 1) = n!

Утверждение 3. , при r  n, =0 при r>n.

Действительно, каждое (n, r)-сочетание можно упорядочить r! способами, т.е. в r! раз меньше, чем . Из этой формулы видно = .

Утверждение 4. .

Действительно, каждому (n, r)-сочетанию В с повторениями, составленному из элементов множества Х = {x₁, …, x_n}, поставим в соответствие вектор (В) длины n+r-1 из r нулей и n-1 единиц такой, что число нулей, находящихся между (i-1)-ой и i единицами, где 2 i  n-1 будет равно числу элементов x_i, входящих в сочетание В, а число нулей, стоящих перед первой единицей (после (n-1)-ой единицы) равно числу элементов x₁ (соответственно x_n), входящих в В.

Например, пусть Х={1, 2, 3, 4}, n=4, пусть r=6, тогда если В={2, 2, 3, 3, 3, 4} - (4, 6)-сочетание с повторением, то (В) = 100100010.

С другой стороны, если (В₁)=110010000, то В₁ = {3, 3, 4, 4, 4, 4}.

Это соответствие между (n, r)-сочетаниями с повторениями и векторами, содержащими n-1 единицу и r нулей, взаимно однозначны. Число векторов размерности n+r-1 с n-1 единицами и r нулями равно , что и доказывает утверждение.

Заметим, что = = .

Размещения и функциональные отображения.

Классической задачей комбинаторики является задача определения числа способов размещения некоторых объектов в каком-то количестве "ящиков" так, чтобы были выполнены заданные ограничения. Формально эта задача формулируется так:

Пусть Х = r, Y = n. Обозначим через Y^Х множество всех отображений f : X  Y. Сколько существует функциональных отображений f : X  Y, удовлетворяющих заданным ограничениям? Если на эти отображения ограничений нет, то имеет место

Утверждение 5. Y^Х  = = n^r = Y^X.

Действительно, пусть Х = {x₁, …, x_r}. Тогда любое отображение f : ХY можно представить в виде упорядоченной последовательности (f(x₁), f(x₂), …, f(x_r)), где f(x_i)Y, т.е. мы установили взаимно однозначное соответствие между множеством функциональных отображений и множеством упорядоченных выборок с повторениями объема r из множества Y объема n, а их число равно n^r.

(Если Х - объекты, а Y- "ящики", то функция f указывает для каждого объекта хХ "ящик" f(x)Y, в котором данный объект находится).

Легко найти число размещений, для которых каждый "ящик" содержит не более одного объекта – такое размещение соответствует однозначным функциям (инъективным отображениям).

Утверждение 6. Число инъективных отображений f : X  Y (т.е. таких, что из f(x₁)= f(x₂)  х₁=х₂ ) равно .

Действительно, в этом случае все члены упорядоченной последовательности (f(x₁), f(x₂), …, f(x_r)) должны быть различны, то есть эта последовательность является размещением без повторений.

Следствие. Если S_n - множество всех биективных отображений n-элементного множества в себя (т.е. осуществляющих взаимно однозначное отображение элементов множества в себя), то их количество | S_n | равно