4. Лабораторная работа № 4 Элементы комбинаторики

   1. Цель работы: Изучить основные понятия комбинаторики и научиться решать комбинаторные задачи

   2. Теоретические сведения

Объектами комбинаторики являются элементы множества Х={x₁;x₂;...;x_n} мощности n и правила их отображения на другое множество Y={y₁;y₂;...;y_k} мощностиk, определяющие способы выбораk элементов множества Х в соответствии с поставленной задачей.

Специфика комбинаторного анализа состоит в правилах выбора элементов множества Х для формирования y^k, правилах одно-или многократного использования элементов множества Х внутри каждой выборки и правилах наведения порядка внутри каждой выборки. Выборки элементов множества Х, т.е. y^kY называют комбинаторными объектами, а их число - комбинаторным числом.

Например, для четырехэлементного множества Х={x₁;x₂;х₃;x₄} могут быть сформированы такие трехэлементные множества:

1){(x₁;x₂;х₃);(x₂;х₁;x₃);(x₂;х₃;x₁);(x₃;x₂;х₁);...; (x₄;х₃;x₂)};

2){ {x₁;x₂;х₃}; {x₁;х₃;x₄}; {x₂;х₃;x₄}};

3){ (x₁;x₁;х₁);(x₁;x₁;х₂);(x₁;x₂;х₁);(x₂;х₁;x₁);...;(x₄;x₄;x₄)};

В первом случае важным при формировании выборок является порядок элементов внутри выборки. Так формируется кортеж.

Во втором случае важным является не порядок элементов внутри, а только их различие. Так формируются подмножества.

В третьем случае главным является повторяемость использования одного элемента. В этом случае также формируется кортеж, а повторяемость задается, как правило, спецификацией K={k₁;k₂;...;k_n}, где

k_i- число повторений в выборке i-го элемента генеральной совокупности;

K=(k₁+k₂+...+k_n)=k.

Итак, выборки бывают упорядоченными(см. случаи 1 и 3), когда важным является место элемента в выборке и неупорядоченными(см. случай 2), когда важным является различие элементов, используемых в выборке.

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

Размещение из n элементов по k без повторений,

Пусть дано множество Х={x₁;x₂;...;x_n} - множество шаров, частиц, книг, файлов и т.п. и множество Y={y₁;y₂;...;y_k} - множество ячеек, урн, стеллажей, дискет и т.п. Сколько существует способов размещения каждого элемента множества Х на каждое место множества Y. То есть необходимо выяснить разнообразие по участию всех элементов множества Х и месту их расположения в выборке. Очевидно, что при формировании выборок будут получены кортежи.

Множество комбинаторных объектов для размещения может быть описано так: А_n^k={(x₁;x₂;...);(x₂;x₁;...);...}.

Комбинаторное число размещения из n элементов по kбез повторения определяется по формуле: (n)_k=n(n-1)...(n-k+1).

Пусть Х={x₁;x₂;x₃}. Необходимо разместить элементы этого множества по двум ячейкам Y={y₁;y₂}. Множество комбинаторных объектов равно:

y₂

x₂

x₃

x₁

x₃

x₁

x₂

y₁

x₁

x₁

x₂

x₂

x₃

x₃

А₃²={(x₁;x₂);(x₂;x₁);(x₁;x₃);(x₃;x₁);(x₂;x₃);(x₃;x₂)}.

Комбинаторное число размещения из 3 элементов по 2 без повторений равно: (3)₂=32=6.

На рис. 2 графически представлен результат размещения из 3-х элементов по 2 без повторения.

Рис. 2. Размещение без повторения

Х={x₁;x₂;x₃}; Y={y₁;y₂}.

Размещение из n по k с повторением.

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

Множество комбинаторных объектов для этой процедуры равно:

А_{n повт}^k={(x₁;x₁;...);(x₂;x₂;...);...}.

Комбинаторное число размещения из n элементов по kс повторением, определяется формулой: (n)_k^повт.=n^k.

Пусть Х={x₁;x₂}. Необходимо разместить элементы этого множества по трем ячейкам Y={y₁;y₂;y₃}.

Множество комбинаторных объектов равно:

А_{2 повт.}³={(x₁;x₁;x₁);(x₁;x₁;x₂);(x₁;x₂;x₁);(x₁;x₂;x₂);(x₂;x₁;x₁);(x₂;x₁;x₂);

(x₂;x₂;x₁);(x₂;x₂;x₂)}.

Комбинаторное число размещения из 2-х элементов по 3 с повторением равно: (2)₃^повт.=2³=8.

На рис. 3 графически представлен результат размещения из 2-х элементов по 3 с повторением.

y₃

x₁

x₂

x₁

x₁

x₁

x₂

x₂

x₂

y₂

x₁

x₁

x₂

x₁

x₂

x₂

x₁

x₂

y₁

x₁

x₁

x₁

x₂

x₂

x₁

x₂

x₂

Рис. 3. Размещение с повторением Х={x₁;x₂}; Y={y₁;y₂;y₃}.

Размещение из n по k с ограничением спецификацией.

Отличительной способностью данного размещения является ограничение повторений спецификацией K={k₁;k₂;...;k_n} при условииK=(k₁+k₂+...+k_n)=k.

Комбинаторное число такого размещения определяется выражением: (n)_k1;k2;...kn^повт.=(k!)/(k₁!k₂!...k_n!)

y₁

x₁

x₁

x₂

y₂

x₁

x₂

x₁

y₃

x₂

x₁

x₁

Рис. 4. Размещение с повторением по спецификации Х={x₁;x₂}; Y={y₁;y₂;y₃}, K={2₁;1₂}.

Пусть Х={x₁;x₂}. Необходимо разместить элементы этого множества по трем ячейкам Y={y₁;y₂;y₃} с заданной спецификацией K={2₁;1₂}.

Множество комбинаторных объектов есть

А_{n спец}^k={(x₁;x₁;x₂);(x₂;x₁;x₁);(x₁;x₂;x₁)}.

(2)

Комбинаторное число размещения 2-х элементов по трем ячейкам с повторением по заданной спецификации равно:

=3!/(2!1!)=3.

^спец

³

На рис. 4 дана графическая интерпретация этой задачи.

Перестановка элементов множества.

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

Если применить все вышеприведенные формулы для условия k=n, то получим:

а) комбинаторное число перестановок без повторения:

(n)_n=n! (см. рис. 5).

y₁

x₁

x₁

x₂

x₂

x₃

x₃

y₂

x₂

x₃

x₁

x₃

x₁

x₂

y₃

x₃

x₂

x₃

x₁

x₂

x₁

Рис. 5. Перестановки Х={x₁;x₂;x₃}; Y={y₁;y₂;y₃}.

б) комбинаторное число перестановок с повторением не более n раз

(n)_n^повт.=nⁿ

в) комбинаторное число перестановок с повторением по спецификации

(n)_k^спец=(n!)/(k₁!k₂!...k_n!), где |k₁+k₂+...+k_n|=n.

Пусть необходимо застроить улицу 10 домами, среди которых 3 дома типа а₁, 5 домов типа а₂, 2 дома типа а₃. Сколько способов застройки улицы?

Исходя из условия задачи множество типов домов есть Х={а₁;а₂;а₃}, а спецификация К={3₁;5₂;2₃}.

Число вариантов застройки улицы равно: (n)_спец.=(10!)/(3!5!2!)=2520 вариантов.

Сочетание из n элементов по k без повторений.

Пусть дано множество Х={x₁;x₂;...;x_n} и множество Y={y₁;y₂;...;y_k}. Сколько существует подмножеств множества Х мощностиk, отличающихся между собой не порядком расположения элементов в выборке, а только различием хотя бы одним элементом? Такое формирование выборок иначе можно назвать “укладывание элементов множества Х в “мешок”, т.е. формируются неупорядоченные выборки мощностиk.

Множество комбинаторных объектов такого отображения есть:

С_n^k={(x₁;x₂;...);(x₁;x₃;...);(x₂;x₃;...);...}.

Комбинаторное число сочетаний из n по kбез повторения есть

(

n

k

)

=(n!)/(k!(n-k)!).

Пусть Х={x₁;x₂;x₃}. Необходимо найти комбинаторные объекты и комбинаторное число сочетаний из 3-х элементов по 2 без повторения, т.е. Y={y₁;y₂}.

Множество комбинаторных объектов есть: С₃²={(x₁;x₂);(x₁;x₃);(x₂;x₃)}.

(

)

3

2

Комбинаторное число сочетаниq из 3-х элементов по 2 равно:

=(3!)/(2!1!)=3.

Графически эта процедура представлена на рис. 6.

y₁

x₁

x₁

x₂

y₂

x₂

x₃

x₃

Рис. 6. Сочетания без повторения Х={x₁;x₂;x₃}; Y={y₁;y₂}.

Сочетание из n элементов по k с повторением.Отличительной особенностью данного способа сочетания является многократное, но не болееkраз, использование при выборке одного и того же элемента множества Х.

Множество комбинаторных объектов для этой процедуры равно:

С_{n повт}^k={(x₁;x₁;x₁;...);(x₁;x₂;x₂;...);(x₂;x₂;x₃;...)}.

(

n

k

)

Комбинаторное число сочетания из n поkс повторением равно:

= (n+k -1)!/( k !(n-1)!).

Пусть Х={x₁;x₂;x₃} и Y={y₁;y₂}. Необходимо выполнить процедуру сочетания из 3-х элементов по 2 с повторением, т.е.

С_{3 повт.}²={(x₁;x₁);(x₂;x₂);(x₃;x₃);(x₁;x₂);(x₁;x₃);(x₂;x₃)}.

(

)

Комбинаторное число этой процедуры равно:

=(3+2-1)!/(2!(3-1)!)=(1234)/(1212)=6.

32

Графически эта процедура для сочетания из 3-элементов по 2 с повторением представлена на рис. 7.

y₂

x₁

x₂

x₃

x₂

x₃

x₃

y₁

x₁

x₁

x₁

x₂

x₂

x₃

Рис. 7. Сочетание с повторением Х={x₁;x₂;x₃}; Y={y₁;y₂}.

Правила комбинаторики.

Рассмотренные выше процедуры обеспечивают формирование различных комбинаторных объектов. Однако при выдвижении нескольких условий и необходимости использования нескольких процедур следует применить дополнительные правила комбинаторного анализа:

1)правило суммы:если комбинаторный объект х_iХ_iможет быть выбран из исходного множества Х “s” способами, а комбинаторный объект х_jХ_jиз того же исходного множества Х другими “t” способами, то выбор “либо х_i, либо х_j“ может быть осуществлен “(s+t)” способами.

2)правило произведения:если комбинаторный объект х_iХ_iможет быть выбран из исходного множества Х “s” способами и после каждого из таких выборов комбинаторный объект х_jХ_j, в свою очередь, может быть выбран “t” способами, то выбор “х_iи х_j“ в указанном порядке может быть осуществлен “(st)” способами.

3)принцип включения-исключения:если существует множество Х и множество свойств Y={y₁;y₂;...;y_t}, которыми могут обладать элементы множества Х, то может быть выполнено разбиение множества Х на подмножества по числу свойств, которыми они обладают. В этом случае разбиение множества на подмножества удовлетворяет следующему условию:

|X₀|=|X|-|X₁|+|X₂|-|X₃|...+(-1)^t|X_t|, где

|X₀| - число элементов множества Х, не обладающих ни одним свойством множества Y;

|X| - общее число элементов множества Х;

|X₁| - число элементов множества Х, обладающих только одним свойством множества Y;

|X₂| - число элементов множества Х, обладающих двумя свойствами множестваY;

|X₃| - число элементов множества Х, обладающих тремя свойствами множества Y;

|X_t| - число элементов множества Х, обладающих t-ым количеством свойств множества Y;

t- количество свойств или число элементов множества Y.

Следует обратить внимание, что знак “+” ставят для четного количества свойств множества Y, а знак “-” - для нечетного количества свойств множества Y.

Путь дано множество Х, состоящее из подмножеств А, В, С. Элементы множества Х могут принадлежать одному, двум и трем подмножествам. Согласно принципу включения-исключения можно составить тождество:

=|ABC|-|A|-|B|-|C|+|AB|+|AC|+|BC|-|ABC|.

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

Например, число элементов множества Х, принадлежащих объединению трех подмножеств А, В и С равно:

|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|.

Для примера рассмотрим студенческую группу и отношение студентов к спорту и учебе. Пусть в студенческой группе обучается 50 человек, т.е. |X|=50. В группе 20 юношей (студент обладает одним свойством -”быть юношей”), т.е. |X₁₁|=20. В группе 20 студентов имеют хорошую успеваемость ( студент обладает также одним свойством -”быть хорошо успевающим”), т.е. |X₁₂|=20. В группе 20 студентов увлекаются спортом (студент обладает также одним свойством -”увлекается спортом”), т.е. |X₁₃|=20. 5 юношей имеют хорошую успеваемость (студент обладает двумя свойствами -”быть юношей” и “быть хорошо успевающим”), т.е. |X₂₁|=|X₁₁X₁₂|=5. 10 юношей увлекаются спортом (студент обладает двумя свойствами - “быть юношей” и “увлекается спортом”), т.е. |X₂₂|=|X₁₁X₁₃|=10. 10 хорошо успевающих студента увлекаются спортом ( студент обладает двумя свойствами - “быть хорошо успевающим” и “увлекаются спортом”), т.е. |X₂₃|=|X₁₂X₁₃|=10. 5 юношей имеют хорошую успеваемость и увлекаются спортом (студент обладает тремя свойствами - “ быть юношей”, “быть хорошо успевающим” и “ увлекается спортом”), т.е. |X₃₁|=|X₁₁X₁₂X₁₃|=5. Сколько девушек (дополнение к множеству X₁₁) имеют слабую успеваемость (дополнение к множеству X₁₂) и не увлекаются спортом ( дополнение к множеству X₁₃), т.е.(X₁₁X₁₂X₁₃)=(X₁₁X₁₂X₁₃)?

|(X₁₁X₁₂X₁₃)|=|X|-|X₁₁|-|X₁₂|-|X₁₃|+|X₂₁|+|X₂₂|+|X₂₃|-|X₃₁|

|(X₁₁X₁₂X₁₃)|=50-20-20-20+5+10+10-5=10.

Итак, 10 девушек имеют слабую успеваемость и не увлекаются спортом.