Реферат: Комбинаторные задачи
begin for j:=1 to n do write(a[p[j]],' '); writeln end
else
begin
for j:=i+1 to n do
begin
Perm(i+1);
k:=p[i]; p[i]:=p[j]; p[j]:=k
end;
Perm(i+1);
{циклический сдвиг элементов i .. n влево}
k:=p[i];
for j:=i to n-1 do p[j]:=p[j+1];
p[n]:=k
end
end;{Perm}
begin {Permutations}
Perm(1)
end;
begin {Main}
readln(n);
for i:=1 to n do p[i]:=i;
a := p ; {массив a может быть заполнен произвольно}
Permutations(n)
end.
Заметим, что в данной программе массив p можно было и не использовать, а переставлять непосредственно элементы массива a.
Разбиения множества
Число разбиений n -элементного множества на k блоков произвольного размера, но таких, что каждый элемент множества оказывается “приписан” к одному из блоков, выражается числом Стирлинга второго рода S (n ,k ) [6,7]. Очевидно, что S (n ,k ) = 0 для k > n . Если согласиться, что существует только один способ разбиения пустого множества на нулевое число непустых частей, то S (0,0) = 1 (именно такая договоренность, как и в случае с факториалом, приводит в дальнейшем к универсальным формулам). Так как при разбиении непустого множества нужна, по крайней мере, одна часть, S (n ,0) = 0 при n > 0. Отдельно интересно также рассмотреть случай k = 2. Если непустое множество разделили на две непустые части, то в первой части может оказаться любое подмножество исходного множества, за исключением подмножеств, включающих в себя последний элемент множества, а оставшиеся элементы автоматически попадают во вторую часть. Такие подмножества можно выбрать 2n -1 – 1 способами, что и соответствует S (n ,2) при n > 0.
Для произвольного k можно рассуждать так. Последний элемент либо будет представлять из себя отдельный блок в разбиении и тогда оставшиеся элементы можно разбить уже на k – 1 частей S (n – 1,k – 1) способами, либо помещаем его в непустой блок. В последнем случае имеется kS (n – 1,k ) возможных вариантов, поскольку последний элемент мы можем добавлять в каждый блок разбиения первых n - 1элементов на k частей. Таким образом
S (n ,k ) = S (n – 1, k – 1) + kS (n – 1, k ), n > 0. (5)
Полезными могут оказаться также формулы, связывающие числа Стирлинга с биномиальными коэффициентами, определяющими число сочетаний:
 |