Лекция: Комбинаторные объекты дискретной математики. Алгоритмические задачи комбинаторики. Задача коммивояжера.

В комбинаторном анализе изучаются различные объекты, порождаемые элементами из конечного множества А={}, и числовые характеристики этих объектов. Часто рассматриваются, например, упорядоченные или неупорядоченные подмножества множества А, подмножества с повторяющимися элементами из множества А и т. д. Вместе с классами таких комбинаторных объектов естественным образом вводятся и так называемые комбинаторные числа, задающие число объектов в том или ином классе и зависящие от некоторых параметров, например, от мощности исходного множества А и мощности рассматриваемых подмножеств множества А.

Размещения элементов.Пусть А = {}. Размещением элементов из А по k (или размещением из n элементов по k) называется упорядоченное подмножество из k элементов множества А.

Для А = {} размещениями из А по 3 будут, например, {},{}, {}.

Обозначим число размещений из n элементов по k через A(n, k). При построении конкретного размещения первым элементом в нём можно взять любой из n элементов множества А, вторым элементом — любой из n — 1 оставшихся в А элементов и т. д. Поэтому

A(n, k) = n(n-1)...(n-k+1) при 1< k < n.

Или

При k > n не существует размещений из n по k, следовательно, A(n, k)= 0 при k >n; при k = 0 полагаем A(0,0) = A(n,0)= 1. Нетрудно заметить, что для чисел A(n, k) выполняются тождества

A(n, k) = n A(n-1, k-1)

A(n, k) = A(n, k-1)(n=k+1)

Перестановки элементов.Перестановками элементов множества А = {} (или перестановками из n элементов) называются всевозможные упорядоченные множества из n элементов

Для A ={a1,a2,a3} перестановками будут: {a1,a3,a2}, {a2,a1,a3}, {a2,a3,a1}.

Перестановки из n элементов — частный случай размещений из n элементов по n. Поэтому

P(n)=n!

Сочетания элементов.Сочетанием элементов из А = {} по k (или сочетанием из n элементов по k) называется неупорядоченное подмножество из k элементов множества А.

Для А — {a1,a2,a3} всевозможными сочетаниями по 2 элемента будут {a1,a2}, {a1,a3}, {a2,a3}.

В сочетании, в отличие от размещения, порядок следования элементов не учитывается. Поэтому из одного сочетания (из n элементов по k ) получается k размещений. Отсюда для числа C(n,k) сочетаний из n элементов по k получается формула

Сnk=Ank/k! Cnk=(n*(n-1)*(n-2)*...*(n-k+1))/k!

Из формул видно, что: Cn0=1, Cn1=n,

Cn2=n*(n-1)/2=(n2-n)/2, Cn3=n*(n-1)*(n-2)/6 ...

Cnn-1=n, Cnn=1.

Свойство 1. Cnk=Cnn-k (при всех n>=0 и всех k от 0 до n; обычно говорят кратко — «при всех n и k»).

Доказательство: Их у этого свойства будет два: первое — из формулы, второе — комбинаторное рассуждение.

1.) Cnk=n!/(k!*(n-k)!), а Cnn-k=n!/((n-k)!*(n-(n-k))!)=n!/((n-k)!*k!) — то же самое, что и Cnk, ч.т.д.

2.) Когда мы выбираем k предметов из n, то n-k предметов мы оставляем. Если мы, наоборот, выбранные k предметов оставим, а оставленные n-k — выберем, то получим способ выбора n-k предметов из n. Заметим, что мы получили взаимно-однозначное соответствие способов выбора k и n-k предметов из n. Значит, тех и других способов поровну. Но одних а Cnk, а других а Cnn-k, поэтому они равны, ч.т.д.

Свойство2. Cn+1k+1=Cnk+Cnk+1, при всех n и k.

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

1. Cnk=n!/(k!*(n-k)!), Cnk+1=n!/((k+1)!*(n-k-1)!), а Cn+1k+1=

2. (n+1)!/((k+1)!*(n-k)!). Теперь приведем первые два равенства к общему знаменателю и сложим: Cnk+Cnk+1 = n!*(k+1)/((k+1)!*(n-k)!)+n!*(n-k)/((k+1)!*(n-k)!) = n!*(k+1+n-k)/((k+1)!*(n-k)!) = (n+1)!/((k+1)!*(n-k)!) = Cn+1k+1, ч.т.д.