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

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

Размещения элементов. Пусть А = {}. Размещением элементов из А по 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 ={ a₁,a₂,a₃ } перестановками будут: { a₁,a₃,a₂ }, { a₂,a₁,a₃ }, { a₂,a₃,a₁ }.

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

P(n)=n!

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

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

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

С_n^k=A_n^k/k! C_n^k=(n*(n-1)*(n-2)*...*(n-k+1))/k!

Из формул видно, что: C_n⁰=1, C_n¹=n,

C_n²=n*(n-1)/2=(n²-n)/2, C_n³=n*(n-1)*(n-2)/6...

C_n^n-1=n, C_nⁿ=1.

Свойство 1. C_n^k=C_n^n-k (при всех n>=0 и всех k от 0 до n; обычно говорят кратко - "при всех n и k").

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

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

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

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

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

1. C_n^k=n!/(k!*(n-k)!), C_n^k+1=n!/((k+1)!*(n-k-1)!), а C_n+1^k+1=

2. (n+1)!/((k+1)!*(n-k)!). Теперь приведем первые два равенства к общему знаменателю и сложим: C_n^k+C_n^k+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)!) = C_n+1^k+1, ч.т.д.