Количество различных подмножеств множества подмножеств

[mustang]

Всем доброго дня.

Заголовок темы может показаться странным, поэтому сразу привожу формулировку задачи.

Пусть имеется множество $A$ подмножеств множества $X$ мощности $n$: $\{A_1, A_2,…,A_n\}$, $A_i \in X, i=[1,n]$

Построим множество подмножеств $B_I, где B_I = \bigcap_{k \in I} A_k \setminus \bigcup_{j \notin I} A_j$, где $I \in B({1,…,n})$ — множество всех подмножеств индексов от 1 до $n$.

Видно, что мощность множества $B = \{B_I\}$ равна $2^{2^{n}-1}$

Пусть $S \subset B$, при этом выполняются условие восстановимости: $\forall A_n \exists S^{\thicksim} \subseteq S: \bigcup_{p \in S^{\thicksim}}p = A_n $

Комментарий: иными словами, мы имеем множество $S$, которое определяет структуру множества $A$, т.е. теоретико-множественные отношения между его элементами — подмножествами $A_n$.

Подсчёт количества множеств $S$, удовлетворяющих условию восстановимости, приводит к последовательности A059201

Однако, поскольку $A$ — множество подмножеств, то на множестве множеств $S$ возникают классы эквивалентностей: такие $S$, что восстанавливаемые множества $A$ отличаются только нумерацией своих элементов.

И мощность разнообразия структур множества $A$ определяется именно количеством классов эквивалентностей $S$.

В смысле формулировки задачи, дающей упомянутую последовательность A059201, вопрос в том, каково количество классов изоморфизма соответствующих гиперграфов — t0-покрытий?

Для $n=1$ ответ тривиален — 1.

Для $n=2$ ответ будет 3 ($i \ne j$):

1. $A_i \cap A_j = \emptyset$,

2. $A_i \subset A_j$,

3. $A_i \cap A_j \ne \emptyset$ и $A_i \setminus A_j \ne \emptyset$

Попытка запрограммировать полный перебор всего множества множеств $S$ осуществлялась через представление в виде бинарных матриц, однако нет уверенности в правильности результатов: для $n=3$ ответ — 29, для $n=4$ ответ — 1885.

P.S. Если имеются замечания к формулировкам — буду рад поправиться.
P.S.S Если имеет смысл обсуждать реализацию прямого численного эксперимента — готов обсудить.

[Someone]

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

Пусть имеется множество $A$ подмножеств множества $X$ мощности $n$: $\{A_1, A_2,…,A_n\}$, $A_i \in X, i=[1,n]$

Давайте сразу уточним: подмножеств или элементов? Потому что словами Вы написали "подмножеств", а формулой — "элементов" ($\in$).

[mustang]

Someone в сообщении #1333921 писал(а):

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

Пусть имеется множество $A$ подмножеств множества $X$ мощности $n$: $\{A_1, A_2,…,A_n\}$, $A_i \in X, i=[1,n]$

Давайте сразу уточним: подмножеств или элементов? Потому что словами Вы написали "подмножеств", а формулой — "элементов" ($\in$).

Потому что подмножество некоторого множества является элементом множества подмножеств.

Как будет корректно записать операцию порождения множества всех подмножеств данного множества? Если я запишу эту операцию как $B(X)$, то

$A \subseteq B(X)$, $A_i \in A$, $i = [1,…n]$

[Geen]

А зачем Вам вообще $X$ - он же нигде больше не фигурирует?

-- 22.08.2018, 18:43 --

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

Видно, что мощность множества $B = \{B_I\}$ равна $2^{2^{n}-1}$

А не не более $2^n-1$ разве?
Например, взяли два непересекающихся множества - тогда $B$ состоит только из пустого множества и каждого из этих заданных множеств. А если два совпадающих, то только пустое множество...

[Sender]

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

Как будет корректно записать операцию порождения множества всех подмножеств данного множества? Если я запишу эту операцию как $B(X)$

По-моему, нередко используется обозначение $2^X$.

[Someone]

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

Потому что подмножество некоторого множества является элементом множества подмножеств.

А у Вас $X$ — не множество подмножеств. У Вас $A_i$ — подмножества $X$:

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

Пусть имеется множество $A$ подмножеств множества $X$ мощности $n$: $\{A_1, A_2,…,A_n\}$, $A_i \in X, i=[1,n]$

Кстати, и запись $i=[1,n]$ какая-то странная. Боюсь, она означает совсем не то, что Вы имеете в виду.

[mustang]

Geen в сообщении #1333930 писал(а):

А зачем Вам вообще $X$ - он же нигде больше не фигурирует?

Привычка . Чтобы показать, что над $A_i$ можно выполнять все теоретико-множественные операции. $X$ здесь как бы множество-универсум. В принципе, для этой задачи нюансами аксиоматики теорий множеств можно не заморачиваться.

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

Видно, что мощность множества $B = \{B_I\}$ равна $2^{2^{n}-1}$

А не не более $2^n-1$ разве?
Например, взяли два непересекающихся множества - тогда $B$ состоит только из пустого множества и каждого из этих заданных множеств. А если два совпадающих, то только пустое множество...[/quote]

$A_i$ не могут совпадать. Поскольку они - элементы множества. А у множества все его элементы различны.

Если у нас есть множество подмножеств, то количество всех $B_I$ есть $N=2^n-1$ (пустое множество нас не интересует).

Соответственно количество всех подмножеств множества $B$ есть $M = 2^N$, т.е. $2^{2^n-1}$

-- 23.08.2018, 11:56 --

Someone в сообщении #1333986 писал(а):

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

Потому что подмножество некоторого множества является элементом множества подмножеств.

А у Вас $X$ — не множество подмножеств. У Вас $A_i$ — подмножества $X$

Правильно. Множество подмножеств здесь - $A$:

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

Пусть имеется множество $A$ подмножеств множества $X$

Цитата:

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

Пусть имеется множество $A$ подмножеств множества $X$ мощности $n$: $\{A_1, A_2,…,A_n\}$, $A_i \in X, i=[1,n]$

Кстати, и запись $i=[1,n]$ какая-то странная. Боюсь, она означает совсем не то, что Вы имеете в виду.

Имеется ввиду, что для всех $i$ от $1$ до $n$ включительно. Да, вы правы, вместо "$=$" надо было написать "$\in$". Я так понимаю, опечатки в исходном сообщении поправить не получится?

Если кратко, то задача для множества $A$ перенумерованных множеств $A_i$, решена. Задача-аналог — t0-покрытия. Также решена задача для кортежа ($n$-ки подмножеств $A_i$).

А вот подсчитать количество классов эквивалентности, порождаемых перестановкой индексов — проблема. Я не встречал решений по изморфизмам гиперграфов, если опираться на упомянутую задачу-аналог.

Если можно построить алгоритм, порождающий множество представителей каждого класса — вообще отлично.

[Geen]

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

Привычка . Чтобы показать, что над $A_i$ можно выполнять все теоретико-множественные операции.

Странная привычка...

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

пустое множество нас не интересует

Почему? И что ещё нас не интересует?

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

количество всех подмножеств множества $B$

А где до этого шла речь об этом количестве?

-- 23.08.2018, 12:24 --

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

$A_i$ не могут совпадать.

$n=2$, $A_1=\varnothing$, $B=\{\varnothing,A_2\}$

[Sender]

Кажется, я улавливаю, о чём речь. Предлагаю следующую формулировку.
Пусть имеется конечное множество $U$, содержащее $n$ элементов: $U:|U|=n$. Тогда

$$\mathfrak{A}=\{A:\big(A\subseteq{2^U}\big)\wedge\big(\varnothing \not\in A\big) \wedge\big( \cup_{a\in A}a=U \big) \wedge \big(\forall u \in U \exists B,C \subseteq A:(\cap_{b \in B}b) \cap (\cap_{c \in C}(U\setminus c))=\{u\} \big)\}$$

Далее мы считаем $A_1,A_2\in \mathfrak{A}$ эквивалентными, если существует перестановка элементов $U$, переводящая $A_1$ в $A_2$. Требуется подсчитать число классов эквивалентности(обозначим их множество S) для каждого $n\in \mathbb{N}$.
Например, для $n=2$ $U=\{1,2\}$, S=

{{{1},{2}},
 {{1},{1,2}},
 {{1},{2},{1,2}}}.

Для $n=3$ $U=\{1,2,3\}$,S=

{{{1, 2}, {1, 3}},
 {{1}, {2}, {3}},
 {{1}, {2}, {1, 3}},
 {{1}, {2}, {1, 2, 3}},
 {{1}, {1, 2}, {1, 3}},
 {{1}, {1, 2}, {2, 3}},
 {{1}, {1, 2}, {1, 2, 3}},
 {{1, 2}, {1, 3}, {2, 3}},
 {{1, 2}, {1, 3}, {1, 2, 3}},
 {{1}, {2}, {3}, {1, 2}},
 {{1}, {2}, {3}, {1, 2, 3}},
 {{1}, {2}, {1, 2}, {1, 3}},
 {{1}, {2}, {1, 2}, {1, 2, 3}},
 {{1}, {2}, {1, 3}, {2, 3}},
 {{1}, {2}, {1, 3}, {1, 2, 3}},
 {{1}, {1, 2}, {1, 3}, {2, 3}},
 {{1}, {1, 2}, {1, 3}, {1, 2, 3}},
 {{1}, {1, 2}, {2, 3}, {1, 2, 3}},
 {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}},
 {{1}, {2}, {3}, {1, 2}, {1, 3}},
 {{1}, {2}, {3}, {1, 2}, {1, 2, 3}},
 {{1}, {2}, {1, 2}, {1, 3}, {2, 3}},
 {{1}, {2}, {1, 2}, {1, 3}, {1, 2, 3}},
 {{1}, {2}, {1, 3}, {2, 3}, {1, 2, 3}},
 {{1}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}},
 {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}},
 {{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}},
 {{1}, {2}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}},
 {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}}.

Для вычислений использовался такой код mathematica:

n = 3; s = Range[n]; Select[
 Union[Select[Subsets[Subsets[s]], ! MemberQ[#, {}] &], 
 SameTest -> (MemberQ[(p = #1;
 Map[
 Sort, ((p /. # & /@ (Inner[#1 -> #2 &, s, #, List] & /@ 
  Permutations[s]))), 2]), #2] &)], (s1 = #;
 s2 = Complement[s, #] & /@ s1;
 And @@ (MemberQ[(a = #; If[a != {}, Intersection @@ a, {}]) & /@ 
  Subsets[Union[s1, s2]], {#}] & /@ s)) && (Union @@ # == 
 s) &]

Таким образом, при $n=3$ получается $|S|=29.$ При $n=4$ $|S|=1885,$ что согласуется с результатами mustang.

[mustang]

Geen в сообщении #1334078 писал(а):

mustang в сообщении #1334077

писал(а):
пустое множество нас не интересует
Почему? И что ещё нас не интересует?

Ну такое условие задачи.

Если грубо, то пустое множество, будучи аргументом, не изменяет результат теоретико-множественной операции относительно другого аргумента. Ну или потому, что пустое множество не имеет теоретико-модельной интерпретации. Пустое множество апельсинов и пустое множество стульев равны друг другу (неотличимы друг от друга).

Могу сказать что интересует — формула, определяющая количество классов эквивалентности. Ну или классов изморфизма t0-покрытий n-элементного множества.

Ещё больше интересует прямой алгоритм построения множества представителей этих классов.

-- 23.08.2018, 19:11 --

Sender в сообщении #1334145 писал(а):

Кажется, я улавливаю, о чём речь. Предлагаю следующую формулировку.
Пусть имеется конечное множество $U$, содержащее $n$ элементов: $U:|U|=n$. Тогда

$$\mathfrak{A}=\{A:\big(A\in{2^U}\big)\wedge\big(\varnothing \not\in A\big) \wedge\big( \cup_{a\in A}a=U \big) \wedge \big(\forall u \in U \exists B,C \subseteq A:(\cap_{b \in B}b) \cap (\cap_{c \in C}(U\setminus c))=\{u\} \big)\}$$

Далее мы считаем $A_1,A_2\in \mathfrak{A}$ эквивалентными, если существует перестановка элементов $U$, переводящая $A_1$ в $A_2$. Требуется подсчитать число классов эквивалентности(обозначим их множество S) для каждого $n\in \mathbb{N}$.

Спасибо, Sender.

Я так понимаю, рассчитанный вами S - множество представителей классов эквивалентностей и $S \subseteq \mathfrak{A}$.

Структура (типизация) $S$ - множество множеств подмножеств $U$. И $\mathfrak{A}$ тогда имеет такую же типизацию.

$A$ - подмножество $U$, следовательно $\mathfrak{A}$ - множество $A$ или множество подмножеств $U$.

Типизация не бьётся, или я не правильно читаю условие для $\mathfrak{A}$ .

Мне нужно в идею последнего условия вникнуть, так я записывать не пробовал .

[Sender]

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

$A$ - подмножество $U$, следовательно $\mathfrak{A}$ - множество $A$ или множество подмножеств $U$.

Да, $A$, конечно же, должно быть подмножеством $2^U$. Поправил в исходном сообщении.

[mustang]

В общем, благодаря Sender первые несколько членов искомой последовательности стали известны: 1, 3, 29, 1885…

В OEIS такой последовательности нет. http://oeis.org/search?q=1%2C3%2C29%2C1885&sort=&language=&go=Search

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

Вопрос формирования искомого множества путём построения, а не отбрасывания вариантов ($2^{2^n}$ уже при $n = 6$ для вычислений бесперспективно) - также актуален.

Есть какие-то идеи, как подступиться к задаче? Оценка асимптотики?

Видно, что по сравнению с A059201$: 1, 4, 96, 31692, 2147001636,…$ растёт медленнее

Sender, по вашей формуле $|\mathfrak{A}(n)|$ есть A059201? Я mathematica не владею.



У меня есть соображения как сократить количество перебираемых вариантов, в том числе, разбивая задачу на части. Не уверен, правда, что получается задача по динамическому программированию.

Вопрос к модератору: уместно ли обсуждать на этом тематическом форуме алгоритмические моменты? Хотя они могут натолкнуть на решение, задача то, как мне видится, комбинаторная.

[Geen]

Sender в сообщении #1334145 писал(а):

Далее мы считаем $A_1,A_2\in \mathfrak{A}$ эквивалентными, если существует перестановка элементов $U$, переводящая $A_1$ в $A_2$.

Прошу прощения, не понял - для любых двух равномощных множеств такая перестановка существует.

-- 24.08.2018, 00:10 --

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

Ну такое условие задачи.

Так а можно таки увидеть это "условие задачи" и задачу целиком?

[mustang]

Geen в сообщении #1334215 писал(а):

Sender в сообщении #1334145 писал(а):

Далее мы считаем $A_1,A_2\in \mathfrak{A}$ эквивалентными, если существует перестановка элементов $U$, переводящая $A_1$ в $A_2$.

Прошу прощения, не понял - для любых двух равномощных множеств такая перестановка существует.

Это не так. $A_i$ - множества подмножеств. Посмотрите на решения, которые привёл Sender.

-- 24.08.2018, 00:10 --

Цитата:

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

Ну такое условие задачи.

Так а можно таки увидеть это "условие задачи" и задачу целиком?

Прочитайте первый пост и последующие, в которых исправлены некоторые оговорки.

Могу повторить (с учётом обсуждения):
Вариант 1: определить число классов эквивалентности подмножеств множества подмножеств множества $U$, $|U|=n$, удовлетворяющих условиям:
а) все подмножества множества $U$ не пусты,
б) для всех подмножеств множества подмножеств множества $U$ объединение их элементов — подмножеств множества $U$ — есть множество $U$,
в) для любого подмножества множества подмножеств множества $U$ и для любых двух различных элементов множества $U$, объединения всех элементов данного подмножества множества подмножеств множества $U$, содержащих один и другой элемент множества $U$ соответственно, различны.

Вариант 2: определить число изоморфизмов для t0-покрытий labeled множества мощности $n$

Задача целиком - это овладение структурой множества подмножеств. Там много чего.
Хотя бы простое решить - с каким количеством структур мы имеем дело и каковы свойства этого количества.

Поэтому очень интересно найти явную формулу $|\mathfrak{A}(n)|$.

[Geen]

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

для всех подмножеств множества подмножеств множества $U$ объединение их элементов — подмножеств множества $U$ — есть множество $U$,

Простите? Пустое подмножество множества подмножеств множества никак не может быть равно (по объединению) самому множеству если оно не пусто.

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

определить число изоморфизмов для t0-покрытий labeled множества мощности $n$

Пардон, не знаю что такое $t0$...

-- 24.08.2018, 01:05 --

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

Посмотрите на решения, которые привёл Sender.

Для начала, всё же, хочется понять что решаем...

Пока это выглядит, на мой взгляд, как попытка придумать задачу под известное(?) решение...