Задача 553
Булеан булеанов

Пусть P(n) будет множеством первых n натуральных чисел {1, 2, ..., n}.
Пусть Q(n) будет множеством всех непустых подмножеств P(n).
Пусть R(n) будет множеством всех непустых подмножеств Q(n).

Элемент XR(n) является непустым подмножеством Q(n), поэтому он сам по себе является множеством.
Из X мы можем построить граф следующим образом:

  • Каждый элемент YX соответствует вершине графа и обозначается Y;
  • Две вершины Y1 и Y2 соединены, если Y1Y2 ≠ ∅.

Например, из X = {{1}, {1,2,3}, {3}, {5,6}, {6,7}} получается следующий граф:

p553-power-sets.gif

Этот граф имеет две компоненты связности.

Пусть C(n,k) будет количеством элементов R(n), которые имеют ровно k компонент связности в своем графе.
Известно, что C(2,1) = 6, C(3,1) = 111, C(4,2) = 486, C(100,10) mod 1 000 000 007 = 728209718.

Найдите C(104,10) mod 1 000 000 007.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net