Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Соединения с повторениями. Основные правила комбинаторики.

Вопросы к государственному экзамену

«Дискретная математика»

 

1. Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Соединения с повторениями. Основные правила комбинаторики. 2

2. Деревья. Задачи о кратчайших расстояниях на графах. Основные алгоритмы для решения задач о кратчайших расстояниях. 4

3. Сеть. Поток в сети. Задача о максимальном потоке в сети. Алгоритм нахождения максимального потока. 6

4. Основные понятия теории графов: граф, способы задания, маршруты, связность, расстояния в графах, степени вершины. 8

Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Соединения с повторениями. Основные правила комбинаторики.

 

В простейших комбинаторных задачах требуется подсчитать число способов выбрать k элементов из n –элементного множества. То, что получается в результате выбора, называется выборкой из n по k или (n, k)–выборкой.

Понятие выборки отличается от понятия подмножества:

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

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

Пусть - какое-либо конечное множество. Соединением элементов из множества М называется любой набор, составленный из элементов множества М.

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

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

 

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

При n=k – это перестановка.

При n>k количество размещений из n по k равно:

Очевидно, что

 

· Всякое соединение из k элементов множества, где в котором порядок следования элементов друг за другом не учитывается, называется сочетанием из n по k. Количество сочетаний из n по k определяется следующей формулой:

 

 

· Размещение с повторениями из n элементов множества M по k - всякая конечная последовательность, состоящая из k членов данного множества M (при этом элементы в последовательности могут повторяться). Два размещения с повторениями считаются различными, если хотя бы на одном месте они имеют различные элементы множества М. Число k-размещений с повторениями равно

 

· Общая формулировка задач на сочетания с повторениями: имеются предметы n различных типов. Сколько k-комбинаций можно сделать из них, если не принимать во внимание порядок элементов в комбинации? Общее количество выборок в схеме выбора k элементов из n с возвращением и без учета порядка определяется формулой

 

· Задачи на перестановки с повторениями: Имеются предметы k различных типов. Сколько перестановок можно сделать из n₁ элементов первого типа, n₂ элементов второго типа,…, n_k элементов k-го типа?

 

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

Правило равенства. Если между конечными множествами A и B есть взаимно однозначное соответствие, то

Правило суммы. Если A и B – конечные множества и то

Правило произведения. Для любых конечных множеств A и B имеет место равенство:

 

Первые два правила очевидны, третье следует из того, что при каждый элемент множества A образует b пар с различными элементами множества B, поэтому,
если, то всего будет пар.

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

Для правила суммы обобщение очевидно: мощность объединения любого числа попарно непересекающихся множеств равна сумме их мощностей.

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

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

Тогда весь набор может быть выбран способами.