Комбинаторика битовых строк

[mustang]

Просьба помочь решить следующий блок задач:

имеется полный набор битовых строк (последовательность нулей и единиц) длиной $n$ за исключением нулевой (последовательность одних нулей).

Вопрос: сколькими способами $m_i$ можно выбрать подмножество из $i$ строк так, чтобы для любого бита нашлась хотя бы одна строка в этом подмножестве, у которой этот бит равен 1. Иными словами, сумма "ИЛИ" всех подстрок даёт максимальную строку, состоящую из одних 1.

Ну и чему равна сумма по $m_i$, т.е. общее число наборов строк длины $n$, удовлетворяющих условию выше.

Дополнительное условие: два подмножества строк являются эквивалентными, если существует такая взаимооднозначная перестановка битов строки, что все строки одного подмножества взаимооднозначно переходят в строки другого подмножества. Сколько $m^*_i$ таких групп эквивалентности?

Пример:

$n=2: \{(0,1);(1,0);(1,1)\}$

$m_1 = 1 : \{(1,1)\} \rightarrow 1.$

$m_2 = 2 : \{(0,1);(1,0)\}, \{(0,1);(1,1)\}, \{(1,0);(1,1)\} \rightarrow 3 $

$m_3 = 3 : \{(0,1);(1,0);(1,1)\} \rightarrow 1$

$\sum\limits_{i=1}^n m_i = 5.$

С условием эквивалентности

$m^*_1 = 1 : \{(1,1)\} \rightarrow 1.$

$m^*_2 = 2 : \{(0,1);(1,0)\}, \{(0,1);(1,1)\} \sim \{(1,0);(1,1)\} \rightarrow 2$

$m^*_3 = 3 : \{(0,1);(1,0);(1,1)\} \rightarrow 1$

Спасибо.

PS Если кто опознает задачу-аналог или более общую формулировку, то было бы здорово!

[mustang]

нашел альтернативную формулировку первой задачи: найти количество всех множеств подмножеств данного множества, объединение которых даёт исходное множество. Иными словами, задача покрытия множества подмножествами.

A003465

Развернутая формула: A055154. Т.е. сколько множеств подмножеств заданной мощности накрывает данное множество.

Единственно, просьба - объясните, пожалуйста, как работает формула для этой последовательности - при $n = j$ второй биноминальный коэффициент не вычисляется. Как он должен выглсдеть, чтобы сумма по k давала первую формулу?

Более сложная задача с условием эквивалентности накрывающих множеств подмножеств остаётся открытой.

[Sonic86]

(уточнение)

mustang в сообщении #808061 писал(а):

нашел альтернативную формулировку первой задачи: найти количество всех множеств подмножеств данного множества, объединение которых даёт исходное множество.

Забыли написать, что покрывающие множества непусты и различны.

[mustang]

Sonic86 в сообщении #808117 писал(а):

(уточнение)

mustang в сообщении #808061 писал(а):

нашел альтернативную формулировку первой задачи: найти количество всех множеств подмножеств данного множества, объединение которых даёт исходное множество.

Забыли написать, что покрывающие множества непусты и различны.

Формально, да, такое уточнение нужно, спасибо. Но я инженер, мне тривиальные решения мало интересны. Очевидно, что пустые и повторяющиеся множества делают ответ в стиле "сколько хочешь - столько и нарисуем" :) Ну, понятное дело, бОльшее, чем нетривиальный ответ.