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

[Sender]

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

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

Назовём $A_1, A_2\in \mathfrak{A}$ эквивалентными, если $|A_1|=|A_2|$ и существует биекция $\pi:U \to U$, такая, что
$\forall a_1 \in A_1 \exists a_2\in A_2:\pi(a_1)=a_2.$

[Sender]

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

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

Не берусь утверждать наверняка, но во всяком случае первые несколько членов совпадают:$1,4,96,31692$.

[Geen]

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

Назовём $A_1, A_2\in \mathfrak{A}$

Да, спасибо - не вчитался в это условие, "по привычке" думал что это элементы покрытия, а не сами покрытия...

[mustang]

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

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

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

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

Что означает, что пустое множество не входит в данное множество подмножеств. По условию.

Цитата:

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

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

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

Могу только привести ссылку http://oeis.org/A059201/a059201.pdf по приведённой выше ссылке A059201. Первый абзац:

Цитата:

A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point

-- 24.08.2018, 01:05 --

Цитата:

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

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

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

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

Решаем задачу, формулировка которой, приведена выше. Известное решение ведь должно(?) содержаться в OEIS?

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

Собственно поэтому в этой задаче вопрос об явной формуле.

[Sender]

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

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

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

[Someone]

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

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

Почему бы просто не написать, что рассматриваются покрытия множества $U$ его подмножествами?

[mustang]

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

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

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

Не берусь утверждать наверняка, но во всяком случае первые несколько членов совпадают:$1,4,96,31692$.

Спасибо.

Явная формула, приведённая в A059201: $a(n) = \sum_{i=0}^{n+1}(s(n+1, i)*2^{2^{i-1}-1})$, где $s(n+1, i)$ — число Стирлинга 1 рода.

Компонента $2^{2^{i-1}-1}$ как бы намекает нам на мощность множества множеств подмножеств без пустых множеств, а какова может быть интерпретация второго компонента - числа Стирлинга 1 рода?

Меня смущает правильность приведённой формулы при $i=0$. В mathematica можно проверить?

Тогда, возвращаясь к исходной задаче, можно ли "подкрутить" вышеприведённую формулу под искомую задачу подсчёта классов эквивалентности? Как-то поделить на $n!$ :)

-- 24.08.2018, 12:46 --

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

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

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

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

Согласен, это моё ограничение: слепой десятипальцевый метод vs. посимвольный набор в LaTex со штудированием документации по LaTex.

Плюс отсутствие у меня кругозора общеуподребимых нотаций.

Придётся исправляться

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

Почему бы просто не написать, что рассматриваются покрытия множества $U$ его подмножествами?

Если та запись суть определение покрытия - то да, конечно, можно написать. Спасибо за замечание, так, действительно, короче.

Как это будет корректно и общепринято записать в символьной нотации?

[Someone]

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

записать в символьной нотации

Зачем? Термин "покрытие" достаточно широко распространён. Тем более, что Вы ссылаетесь на англоязычный текст, в котором явно употребляется термин "cover" — покрытие. И вообще, то, что можно написать словами, лучше и писать словами. Читатели будут только благодарны.

[Geen]

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

Не берусь утверждать наверняка, но во всяком случае первые несколько членов совпадают

Если я правильно понимаю определение $T_0$-покрытия, то оно эквивалентно Вашему.

Про эквивалентность с конструкцией из первого поста сказать ничего не могу.

[mustang]

С учётом проведённого обсуждения привожу новую формулировку задачи:

Найти количество классов эквивалентности множества $\mathfrak{A}$ t0-покрытий множества $U$ как функцию от $n=|U|$.

t0-покрытие означает, что для каждых двух различных элементов множества $U$ существует часть покрытия, содержащая один, но не другой элемент.

Эквивалентность двух покрытий $A_1, A_2\in \mathfrak{A}$ означает, что (формулировка Sender) существует биекция $\pi:U \to U$, такая, что $\forall a_1 \in A_1 \exists a_2\in A_2:\pi(a_1)=a_2$

Задача количества t0-покрытий решена A059201

Задача количества классов эквивалентности остаётся открытой. Прямой перебор (спасибо Sender) дал следующие значения:
$a(1) = 1$
$a(2) = 3$
$a(3) = 29$
$a(4) = 1885$

-- 24.08.2018, 15:05 --

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

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

Не берусь утверждать наверняка, но во всяком случае первые несколько членов совпадают

Если я правильно понимаю определение $T_0$-покрытия, то оно эквивалентно Вашему.

Про эквивалентность с конструкцией из первого поста сказать ничего не могу.

Совпадает. Просто от множеств из исходной формулировки перешли к индексам (номерам) этих множеств. Получили не множество множеств, а кортеж множеств (длина кортежа равна мощности множества).

Собственно вопрос о классах эквивалентности возникает именно в силу того, что нужно обратно перейти от кортежа к множеству - нам без разницы, как именно перенумерованы исходные множества.

[Sender]

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

Эквивалентность двух покрытий $A_1, A_2\in \mathfrak{A}$ означает, что (формулировка Sender) существует биекция $\pi:U \to U$, такая, что $\forall a_1 \in A_1 \exists a_2\in A_2:\pi(a_1)=a_2$

Тут ещё необходимо добавить равенство мощностей $A_1$ и $A_2$, ну или наличие прообраза в $A_1$ у каждого $a_2$ из $A_2.$

[mustang]

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

Тут ещё необходимо добавить равенство мощностей $A_1$ и $A_2$, ну или наличие прообраза в $A_1$ у каждого $a_2$ из $A_2.$

Да, согласен. В таком виде условия у $A_2$ могут быть "лишние" элементы. Поскольку отношение эквивалентности симметрично, то наличие прообраза как-бы само собой подразумевалось.

Требование равенства мощностей $A_1$ и $A_2$ для меня выглядит, скорее, следствием.

Спасибо за поправку, как-то "оттуда ушёл, а туда не пришёл".

Т.е. так правильно?:

Существуют биекция $\pi$:U \to U$ и обратная ей $\pi^*$ ($\forall u \in U \pi^*{(\pi(u))}=u$), такие, что $(\forall a_1 \in A_1 \exists a_2\in A_2:\pi(a_1)=a_2) \wedge (\forall a_2 \in A_2 \exists a_1 \in A_1:\pi^*(a_2)=a_1)$

(Оффтоп)

Исправить предыдущее сообщение я уже не смогу? Никаких кнопок типа "изменить" или "редактировать" я не вижу

[Someone]

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

Существуют биекция $\pi:U \to U$ и обратная ей $\pi^*$ ($\forall u \in U \pi^*{(\pi(u))}=u$), такие, что $(\forall a_1 \in A_1 \exists a_2\in A_2:\pi(a_1)=a_2) \wedge (\forall a_2 \in A_2 \exists a_1 \in A_1:\pi^*(a_2)=a_1)$

Обратная биекция стандартно обозначается $\pi^{-1}$. Её существование отдельно требовать не нужно, так как отображение имеет обратное тогда и только тогда, когда является биекцией. Если, конечно, Вы не употребляете термин "биекция" в каком-нибудь расширенном смысле (возможно, в смысле "инъекция"). Но для конечного множества всякая инъекция в себя является биекцией на себя.

Я, видимо, так и не понял ваших обозначений.
Что такое $A_1$ и $A_2$? Это покрытия или что-то другое?
А что такое $a_1$ и $a_2$? Это подмножества множества $U$?

Биекция множества на себя очевидным способом порождает биекцию множества подмножеств на себя и биекцию множества $T_0$-покрытий на себя.

[Sender]

Поскольку я ввёл эти обозначения, то я и отвечу.

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

Что такое $A_1$ и $A_2$? Это покрытия или что-то другое?

Да, это покрытия множества $U$.

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

А что такое $a_1$ и $a_2$? Это подмножества множества $U$?

Именно так.

[maxal]

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

С учётом проведённого обсуждения привожу новую формулировку задачи:

Найти количество классов эквивалентности множества $\mathfrak{A}$ t0-покрытий множества $U$ как функцию от $n=|U|$.

t0-покрытие означает, что для каждых двух различных элементов множества $U$ существует часть покрытия, содержащая один, но не другой элемент.

Эквивалентность двух покрытий $A_1, A_2\in \mathfrak{A}$ означает, что (формулировка Sender) существует биекция $\pi:U \to U$, такая, что $\forall a_1 \in A_1 \exists a_2\in A_2:\pi(a_1)=a_2$

Задача количества t0-покрытий решена A059201

Задача количества классов эквивалентности остаётся открытой. Прямой перебор (спасибо Sender) дал следующие значения:
$a(1) = 1$
$a(2) = 3$
$a(3) = 29$
$a(4) = 1885$

Пусть $B_{n,m}$ - число бинарных матриц размера $n\times m$ с попарно различными ненулевыми строками и попарно различными ненулевыми столбцами, с точностью до перестановок строк и перестановок столбцов. Другими словами, $B_{n,m}$ - это число различных непомеченных двудольных графов с попарно неизоморфными вершинами, без изолированных вершин, и с фиксированными долями размеров $n$ и $m$.
Тогда по аналогии с A059201 и A059202 имеем

$$a(n) = \sum_{m=0}^{2^n-1} B_{n,m}.$$

Насколько я знаю, эффективно вычислять $B_{n,m}$ не умеют. Умеют отдельно вычислять количество бинарных матриц с точностью до перестановок строк и перестановок столбцов (A028657) и количество бинарных матриц с попарно различными ненулевыми строками и попарно различными ненулевыми столбцами (A318537), но вот вместе скомпоновать эти два условия проблематично. Точнее, второе с точностью до перестановки столбцов легко получить делением на $m!$ (A059202), но вот добавить сюда ещё и перестановку строк непросто.