- •Учебное пособие
- •Тема. Комбинаторика
- •Биномиальные коэффициенты
- •Бином Ньютона
- •Треугольник Паскаля
- •Разбиения множества
- •Числа Стирлинга второго рода
- •Число Белла
- •Числа Стирлинга первого рода
- •Формулы включений и исключений
- •Лекция 5. Производящие функции. Основные операции. Примеры использования.
- •Производящие функции
- •Основные операции
- •Примеры использования ПФ
- •Лекция 6. Генерирование комбинаторных объектов. Перестановки. Сочетания. Разбиение чисел. Подмножества множеств.
- •Перестановки
- •Сочетания
- •Разбиения чисел
- •Подмножества множества
- •Тема. Теория конечных графов
- •Ребро
- •Цвет
- •Букет
- •Букет
- •Пуст
- •Лекция 1. Введение в комбинаторику.
- •Некоторые области применения задач комбинаторики.
n−1
Пример 5.2. Найти ∑(n −k)(n − k)Cn−−k .
n 1
k +2
n−2
Решение: Запишем исходную сумму в виде ∑k 2Ck− .
n 1
k =1
Обозначим |
x |
= k2Ck |
, y |
= kCk |
, z |
k |
=Ck |
. |
|
k |
n−1 |
k |
n−1 |
|
n−1 |
|
|
Соответствующие ПФ имеют вид: |
|
|
|
|||||
∞ |
|
∞ |
|
n−1 |
|
|
|
|
X (s) = ∑xk sk =∑k 2Cnk−1sk =∑k 2Cnk−1sk , |
|
|||||||
k =0 |
|
k =0 |
|
k =1 |
|
|
|
|
n−1 |
|
|
n−1 |
|
|
|
|
|
Y (s) = ∑kCnk−1sk , Z (s) =∑Cnk−1sk = (1 + s)n−1. |
||||||||
k =1 |
|
|
k =1 |
|
|
|
|
|
Т.к. yk=kzk , то Y(s)=sZ'(s). Т.к. xk=kyk, то X(s)=sY'(s)=sZ'(s)+s2z4(s)=s(n-1)(1+s)n+2+s2(n-1)(n-2)(1+s)n-3.
Далее, поскольку
n−1
X (1) = ∑k 2Ck− ,
n 1
k =1
то искомая сумма равна X(1)-(n-1)2=n(n-1)2n-3-(n-1)2.
Лекция 6. Генерирование комбинаторных объектов. Перестановки. Сочетания. Разбиение чисел. Подмножества множеств.
Перестановки
Определение. Если δ={δ1,…, δn} и τ={τ1,…,τn} - перестановки, то δ лексикографически меньше τ, если и только если для некото-
рого k≥1 мы имеем δj=τj, для всех j<k и δk<τk.
Иными словами последовательность перестановок на множестве {1,…,n} представлена в лексикографическом порядке, если она записана в порядке возрастания получающихся чисел.
Например: лексикографическая последовательность перестановок трех элементов имеет вид: 123, 132, 213, 231, 312, 321.
Алгоритм лексикографического порождения перестановок мо21
жет быть следующим. Начиная от перестановки (1,2,…,n), мы переходим далее от Π=(π1,…,πn) и ее последующей путем просмотра Π справа налево в поисках самой правой позиции, в которой πi+πi+1. Найдя ее, мы теперь ищем πj, наименьший элемент, расположенный справа от πi и больший его; затем осуществляется транспозиция элементов πi и πj и отрезок πi+1,…, πn переворачивается.
Например, для n=8 и Π=(2,6,5,8,7,4,3,1) мы имеем πi=5, πj=7,
меняя их местами, получаем (2,6,7,8,5,4,3,1). Переворачивая отрезок πi+1,…, πn получаем новую перестановку (2,6,7,1,3,4,5,8), следующую за Π в лексикографическом порядке.
Следующий алгоритм реализует эту процедуру (в квадратных скобках даны комментарии):
Листинг 6.1 Алгоритм генерации перестановок в лексикографическом порядке.
for j=0 to n do πj← j; i← 1;
while i≠0 do begin
вывести Π=(π1,…,πn);
[Найти самое правое место, где πi<πi+1.] i← n-1;
while πi>πi+1 do i← i-1;
[Найти πj, наименьший элемент справа от πi и больший его]
j← n;
while πi>πj do j← j-1;
[Поменять местами πi и πj и затем перевернуть πi+1,…πn]
πi π;j r ← n;
s← i+1; while r>s do begin
πr πs; r ← r-1;
s ← s+1;
22
end;
end.
Алгоритм начинает работу с распечатки Π=(1,2,…,n) и заканчивает ее при i=0, что происходит в случае, когда π1>π2>…>πn, т.е. когда получена последняя в лексикографическом порядке перестановка.
Сочетания
Пусть основным множеством является множество натуральных чисел (1,2,…,n). Необходимо сгенерировать все сочетания мощности k. Рассмотрим генерацию в лексикографическом порядке. На-
пример, для C53 = 15 24 33 =10 сочетаний из пяти предметов по три
получается следующий лексикографический порядок 123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
Алгоритм лексикографической генерации сочетаний может быть следующим.
Начиная с сочетания (1,2,…,k), следующее сочетание находится просмотром текущего сочетания справа налево с тем, чтобы определить место самого правого элемента, который еще не достиг своего максимального значения. Этот элемент увеличивается на единицу, а всем элементам справа от него присваиваются новые наименьшие возможные значения. Например, если n=6 и мы получили сочетание (1236) , то следующим будет сочетание (1245).
Следующий алгоритм реализует эту процедуру:
Листинг 6.2 Алгоритм генерации сочетаний.
C0 ← -1;
for i=1 to k do Ci← I; j ←1;
while j≠0 do begin
вывести (C1,C2,…,Ck); j← k;
while Cj=n-k+j do j ← j-1;
Cj← Cj+1;
for i=j+1 to k do Ci=Ci-1+1;
end.
23
Разбиения чисел
Рассмотрим задачу генерации разбиений натурального числа n в последовательность неотрицательных целых чисел (p1,…,pk), так что p1+…+pk=n и порядок чисел pi не важен. Т.о. не делается раз-
личий между 1+1+2, 1+2+1, 2+1+1.
Разбиения числа n на l компонентов можно генерировать в возрастающем лексикографическом порядке, начиная с p1=p2=… =pl-1=1, и продолжая процесс следующим образом. Для получения следующего разбиения из текущего просматриваем элементы справа налево, останавливаясь на самом правом pi, таком, что pl-pi≥2. Заменяем затем pj на pi+1 для j=i,i+1,…,l-1 и после этого
l−1
заменяем pl на n −∑p j .
j=1
Например, если n=12 и l=5, а разбиение имеет вид (11334), то 4 на 2 больше самой правой 1, и следующее разбиение будет иметь вид (12225).
Когда ни один из элементов разбиения не отличается от последнего больше, чем на единицу, то процедура заканчивается.
Следующий алгоритм реализует эту процедуру:
Листинг 6.3 Алгоритм генерации разбиения чисел. l←1;
p1←n; p0←-1; while l≤n do begin
вывести (p1,…,pl); i← l-1;
while pl-pi<2 do i←i-1;
if i≠0 then for j=l-1 to i by –1 do pj←pi+1; else for j=1 to l do pj←1;
l←l+1;
l−1
pl←n- ∑p j ;
j=1
end.
24