Перестановки с повторениями

ДМ. Лекция № 2.

Тема: «Элементы комбинаторики»

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

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

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

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

Пусть Х – конечное множество, состоящее из n элементов. Тогда говорят, что объект х из Х может быть выбран n способами и пишут | X | = n. Пусть Х₁, …, Х_n – попарно пересекающиеся множества, т.е. Х_i ∩ X_j = Æ при i ≠ j. Тогда очевидно выполняется равенство

В комбинаторике этот факт называется правилом суммы. Для k = 2 оно формулируется следующим образом: «Если объект x может быть выбран m способами, а объект y – другими n способами, то выбор «либо x, либо y» может быть осуществлен m + n способами».

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

Доказательство.

 

Мы сформулировали и доказали правило произведения для последовательности из двух объектов. В общем случае правило произведения формулируется следующим образом: «Если объект x₁ может быть выбран n₁ способами, после чего объект x₂ может быть выбран n₂ способами и для любого i, где 2 ≤ i ≤ m -1 после выбора объектов x₁,..., x_i объект x_i+1 может быть выбран n_i+1 способами, то выбор упорядоченной последовательности из m объектов (x₁, x₂,..., x_n) может быть осуществлён n₁∙n₂∙…∙n_m способами».

Обобщенное правило произведения является следствием правила произведения для упорядоченной пары объектов и доказывается методом математической индукции.

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

def. Набор элементов , …, из множества Х = { x₁,.., x_n } называется выборкой объема k из n элементов или иначе (n,k)-выборкой.

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

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

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

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

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

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

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

Пример 1. Пусть Х ={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,1},{1,2},{1,3},{2,2},{2,3},{3,3} – (3,2)-сочетания с повторениями;

4) {1,2},{1,3},{2,3} – (3,2)-сочетания.

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

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

Доказательство.

 

 

Соглашение. В дальнейшем для общности формул будем считать что 0! = 1.

Утверждение 2. = n ∙ (n-1) ∙ … ∙ (n-k+1) = при k ≤ n и = 0 при k > n.

Доказательство.

Следствие. P_n = = n ∙ (n - 1) ∙ … ∙ 1 = n!.

Утверждение 3. = = при k ≤ n и = 0 при k > n.

Доказательство.

 

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

Доказательство.

 

 

Пример 2. Пусть n = 4, k = 6, X = {1,2,3,4}, B ={2,2,3,3,3,4} – (4,6)-сочетание с повторениями. Тогда a(В) =. С другой стороны, если, например,

a(В) = 110010000, то однозначно получаем, что В = { }.

Замечание. При определении выборки предполагалось, что она содержит, по крайней мере, один элемент. Однако для общности рассуждений в число выборок часто включают и пустую выборку, не содержащую элементов. Она единственна для всех рассмотренных нами случаев, т.е. = = = = 1; при этом формулы, приведенные в утверждениях (1) – (4) остаются справедливыми.

Перестановки с повторениями

Имеется n элементов, которые можно разбить на k групп, так что элементы, входящие в одну группу не различимы между собой и отличны от элементов в другие группы. Число элементов в каждой группе равно соответственно n₁, n₂,..., n_k, т.е.

n₁ + n₂ + … + n_k = n.

def. Перестановкой с повторениями из n элементов называется кортеж длины n, составленный из этих элементов.

Обозначается через .

Утверждение 5. = .

Доказательство.

 

Поделиться:

Воспользуйтесь поиском по сайту: