n−1

Пример 5.2. Найти ∑(n −k)(n − k)Cn−−k .

n 1

k +2

n−2

Решение: Запишем исходную сумму в виде ∑k 2Ck− .

n 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