Первая страница / Теория / Комбинаторика /

Комбинаторика (часть 2)

Голосование: 25, 13

Введение

В данной статье продолжается рассмотрение различных аспектов комбинаторики, т. е. она является логическим продолжением этой статьи. Далее мы разберем такие разделы, как разбиения множеств и чисел, производящие функции, принцип включения и исключения и др.

Разбиения множества

Разбиение n-элементного множества X на k блоков — это семейство Q = {B1, …, Bk}, в котором B1 ∪ … ∪ Bk = X, Bi ∩ Bj = Ø, Bi ≠ Ø, для 1 ≤ i < j ≤ k. Обозначим множество всех разбиений множества X на k блоков через Πk(X), а через Π(X) — множество всех разбиений.

Довольно интересным является вопрос генерирования разбиений множества. Рассмотрим идею алгоритма, отвечающего на этот вопрос, описав ее в рекуррентной форме. Сначала сделаем ряд полезных замечаний. Можно показать, что разбиение Q множества {1, …, n} однозначно определяет разбиение Qn−1 множества {1, …, n−1}, которое получается из Q после удаления элемента n (или пустого блока) из соответствующего блока. Также, если имеется разбиение W = {B1, …, Bk} множества {1, …, n−1}, то можно отыскать все разбиения Q множества {1, …, n}, для которых Qn−1 = W, т. е. такие разбиения:

B1 ∪ {n}, …, Bk,

B1, …, Bk ∪ {n},
B1, …, Bk, {n}.

Обозначим такую последовательность через E. Тогда сформулируем несложный метод генерирования разбиений: если у нас есть список Ln−1 всех разбиений множества {1, …, n−1}, то список Ln разбиений множества {1, …, n} будем создавать, заменяя каждое разбиение Q в списке Ln−1 на соответствующую ему последовательность E. Проиллюстрируем построение списка Ln для n = 1, 2, 3.

Списки

Существует нерекуррентная реализация данного алгоритма (см. визуализатор [2]).

Числа Стирлинга второго и первого рода

Число Стирлинга второго рода S(nk) — это число разбиений n-элементного множества на k блоков, т. е.

S(nk) = |Πk(X)|,

где множество X состоит из n элементов. Например, S(4, 2) = 7.

Любопытны некоторые тождества, связанные с числами Стирлинга второго рода:

  • S(nn) = 1, для n ≥ 0,
  • S(n0) = 0, для n > 0,
  • S(nk) = S(n−1, k−1) + kS(n−1, k), для 0 < k < n
  • xn = ∑k=0:n S(nk)[x]k, для n ≥ 0, где [x]k = x(x−1)…(xk+1).

Первые две формулы очевидны. Доказательство последних формул предлагается читателю в качестве несложного упражнения.

Число Белла Bn — это число всех разбиений n-элементного множества:

Bn = |Π(X)|, где |X| = n.

Рассмотрим несложное рекуррентное соотношение:

Bn+1 = ∑i=0:n Ci,nBi

Для доказательства достаточно заметить, что множество всех разбиений множества X = {1, …, n+1} можно разделить на различные классы в зависимости от блока B, который содержит элемент n+1, или в зависимости от множества X \ B. Далее для каждого множества X \ B из {1, …, n} имеется |Π(X \ B)| = B|X\B| разбиений множества X, которое содержит B в качестве блока. Группируя классы в зависимости от мощности множества X \ B, приходим к требуемому.

Числа Стирлинга первого рода s(nk) — это коэффициенты при последовательных степенях переменной x в многочлене [x]k:

[x]n = ∑k=0:n s(nk)xk.

Для них определяются аналогичные рекуррентные соотношения, что и для чисел второго рода:

  • s(nn) = 1, для n ≥ 0,
  • s(n, 0) = 0, для n > 0,
  • s(nk) = s(n−1, k−1) + (n−1)s(n−1, k), для 0 < k < n.

Разбиения чисел

Разбиение числа (натурального) n на k слагаемых — это последовательность a1, …, ak, такая что

n = a1 + … + ak, a1 ≥ … ≥ ak > 0.

Существует довольно простой способ представления разбиения числа — диаграмма Феррерса. Для разбиения a1, …, ak она состоит из k строк, которые соответствуют слагаемым разбиения, где i-я строка состоит из ai точек. Сопряженное разбиение — это разбиение, получающееся при перемене ролями строк и столбцов в диаграмме Феррерса.

Феррерс

Заметим, что с помощью диаграммы Феррерса можно доказать много интересных свойств числа всех разбиений рассматриваемого числа. Подробнее об этом можно почитать в [1].

Рассмотрим теперь несложный алгоритм генерирования всех разбиений числа. Обозначим через S[1], …, S[d] само разбиение числа, а через R[1], …, R[d] — информацию о том, сколько раз слагаемое S[i] появляется в разбиении.


 1  begin
 2      S[1] := n; R[1] := 1; d := 1;
 3      write();
 4      while S[1] > 1 do
 5          begin sum := 0;
 6              if S[d] = 1 then
 7                  begin sum := sum + R[d]; d := d − 1;
 8                  end;   
 9              sum := sum + S[d]; R[d] := R[d] − 1; l := S[d] − 1;
10              if R[d] > 0 then d := d + 1;
11              S[d] := l; R[d] := sum div l;
12              l := sum mod l;
13              if l ≠ 0 then
14                  begin d := d + 1; S[d] := l; R[d] := 1
15                  end;
16              write();
17          end
18  end

Производящие функции

Производящая функция — это функция, которая позволяет определить явный вид общего члена рассматриваемой числовой последовательности. Так, пусть имеется последовательность {an}, для главного члена a которой нужно найти общую формулу. Тогда введем функцию A(x) = ∑nanxn. Если, используя свойства рассматриваемой последовательности, удастся решить составленные для A(x) уравнения, то можно будет получить искомые элементы последовательности.

Один из примеров применения производящих функций относится к числам Фибоначчи. Они являются решением рекуррентного уравнения Fn+1 = Fn + Fn−1, где F0 = F1 = 1.

Рассмотрим производящую функцию F(x) = ∑nfnxn. Она удовлетворяет уравнению F(x) = 1 + x + ∑k=2:∞ (Fk−2 + Fk−1)xk = … = 1 + (x + x2)F(x). Отсюда получаем, что F(x) = (1 − x − x2)−1. Далее находим разложение 1 − x − x2 = (1 − ax)(1 − bx), где a = (1 + √5) ⁄ 2, b = (1 − √5) ⁄ 2. Далее, используя метод неопределенных коэффициентов, получаем F(x) = ∑k=0:∞(ak+1− bk+1)xk ⁄ (ab).

Интересно, что предел отношения fn+1 ⁄ fn равен a, т. е. «золотому сечению». Также существует связь между числами Фибоначчи и треугольником Паскаля: можно выбрать линии, пересекающие узлы треугольника, так, чтобы сумма всех чисел на одной линии соответствовала числу Фибоначчи.

Другим примером являются числа Каталана. Они появляются в контексте следующей задачи: нужно найти число различных последовательных действий, чтобы вычислить сумму S0, …, Sn, складывая любые два рядом стоящих числа и результат помещая на их место. Тогда если обозначить искомое число через сn, то производящая функция будет выглядеть, как С(x) = ∑n=0:∞cnxn. Следуя аналогичным рассуждениям, как и в случае с числами Фибоначчи, получим, что С(x) = ∑n=0:∞C2n,nxn ⁄ (n+1).

Принцип включения и исключения

Для общего представления приведем иллюстрацию для трех множеств A, B и C:

Принцип включения и исключения

Теорема

|∪i=1:n Ai| = ∑i=1:n |Ai| − ∑1≤i<jn |Ai ∩ Aj| + ∑1≤i<j<kn |Ai ∩ Aj ∩ Ak| − … + (−1)n−1|A1 ∩ … ∩ An|.

Доказательство. Будем доказывать теорему по индукции. База индукции очевидно верна. Тогда пусть для A1, …, An−1 выполняется |∪i=1:n−1 Ai| = ∑i=1:n−1 |Ai| − ∑1≤i<jn−1 |Ai ∪ Aj| + ∑1≤i<j<kn−1 |Ai ∩ Aj ∩ Ak| − … + (−1)n−2|A1 ∩ … ∩ An−1|. Если мы применим эту формулу к сумме (A1 ∪ … ∪ An−1) ∩ An = ∪i=1:n−1(Ai ∩ An), то получим |∪i=1:n−1 Ai ∩ An| = ∑i=1:n−1 |Ai ∩ An| − ∑1≤i<jn−1 |Ai ∩ Aj ∩ An| + ∑1≤i<j<kn−1 |Ai ∩ Aj ∩ Ak ∩ An| − … + (−1)n−2|A1 ∩ … ∩ An−1 ∩ An|. Отсюда уже получаем |∪i=1:n Ai| = |(∪i=1:n−1 Ai) ∪ An| = |∪i=1:n−1 Ai| + |An| − |∪i=1:n−1 Ai ∩ An| = ∑i=1:n |Ai| − ∑1≤i<jn |Ai ∩ Aj| + ∑1≤i<j<kn |Ai ∩ Aj ∩ Ak| − … + (−1)n−1|A1 ∩ … ∩ An|.

Литература

  1. Липский В. Комбинаторика для программистов. — М.: Мир, 1988.

Визуализаторы

  1. Белешко Д. Перебор разбиений (2003)

Белешко Дмитрий


kilo51 / 2012-07-16 11:20:53

спасибо очень пригодилось

Марина / 2013-01-07 15:46:08

Спасибо,помогло разобраться :)

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий