2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Число элементов в множестве
Сообщение13.10.2015, 12:05 
Аватара пользователя
Может, кто-нибудь сталкивался с подобными задачами.
Найти число элементов в указанном множестве в зависимости от натурального числа $n$

$\[|([1,n] \times [1,n] \to [1,n])/R(n)|\]$
где эквивалентность $\[R(n)\]$ определяется следующим образом
$\[aR(n)b \[ \buildrel \Delta \over = \] (\exists h \in ([1,n] \leftrightarrow [1,n]))(\forall i,j \in [1,n])h(a(i,j)) = b(h(i),h(j))\]$

Другими словами, на множестве всех функций от двух переменных определена эквивалентность $ R(n)$. Нужно найти число классов эквивалентности.
$\[[1,n]\]$ обозначает множество натуральных чисел от $1$ до $n$.

Вычисляется ли вообще это число?
Хотелось бы узнать литературу, где рассматриваются подобные задачи.

 
 
 
 Re: Число элементов в множестве
Сообщение13.10.2015, 12:29 
Я б сначала задумался над $R$. Как-то мне не очевидно, что это эквивалентность.

 
 
 
 Re: Число элементов в множестве
Сообщение13.10.2015, 13:13 
Аватара пользователя
iifat в сообщении #1061963 писал(а):
Как-то мне не очевидно, что это эквивалентность.

1) $\[\because \quad \operatorname{id} ([1,n]):[1,n] \leftrightarrow [1,n] \wedge \operatorname{id} ([1,n])(a(i,j)) = a(\operatorname{id} ([1,n])(i),\operatorname{id} ([1,n])(j))\]$

2) $\[h:[1,n] \leftrightarrow [1,n];\;(\forall i,j \in [1,n])h(a(i,j)) = b(h(i),h(j))\quad \because \quad {h^{ - 1}}:[1,n] \leftrightarrow [1,n];\;(\forall i,j \in [1,n]){h^{ - 1}}(b(i,j)) = a({h^{ - 1}}(i),{h^{ - 1}}(j))\]$

3) $\[{h_1}:[1,n] \leftrightarrow [1,n];\;(\forall i,j \in [1,n]){h_1}(a(i,j)) = b({h_1}(i),{h_1}(j));\;{h_2}:[1,n] \leftrightarrow [1,n];\;(\forall i,j \in [1,n]){h_2}(b(i,j)) = c({h_2}(i),{h_2}(j))\quad \because \quad {h_2} \circ {h_1}:[1,n] \leftrightarrow [1,n];\;(\forall i,j \in [1,n]){h_2}({h_1}(a(i,j))) = c({h_2}({h_1}(i)),{h_2}({h_1}(j)))\]$

А так не очевиднее?

 
 
 
 Re: Число элементов в множестве
Сообщение13.10.2015, 14:51 
Meson в сообщении #1061976 писал(а):
А так не очевиднее?
Как говаривал Фрэнк Дребин, «Это действительно очевидно. Теперь»

 
 
 
 Re: Число элементов в множестве
Сообщение13.10.2015, 23:57 
Проще говоря, надо найти число неизоморфных магм (алгебр с одной бинарной операцией) данного порядка.

(Оффтоп)

Вёрстка не очень удачная, всё слипается. :? И, как видно, натуральные числа тут совсем бессмысленно добавлять, достаточно было указать мощность носителя операции и всё. И обозначать операцию как операцию.

-- Ср окт 14, 2015 02:00:53 --

Кажется, один раз я нашёл (и вполне элементарно) число неизоморфных алгебр с произвольным числом операций произвольных арностей. Или что-то другое, потому что не помню, почему вышло так просто и откуда там были(?) биномиальные коэффициенты. Надо перевывести, но писать что-то лень, а в уме никак.

-- Ср окт 14, 2015 02:02:25 --

А, отбой, то было, скорее всего, другое число.

 
 
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 00:19 
Аватара пользователя
arseniiv в сообщении #1062329 писал(а):
Проще говоря, надо найти число неизоморфных магм (алгебр с одной бинарной операцией) данного порядка

Да, по-разному можно определять это число. Например, число неэквивалентных матриц Кэли или число неизоморфных группоидов конечного порядка. Но поскольку доказательство будет по индукции (других способов я не вижу), поэтому я и перевел проблему на натуральные числа.

 
 
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 00:55 
Кстати, A001329.

(Группоидами зовут несколько вещей — здесь это те самые, см. описание последовательности.)

 
 
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 01:26 
Аватара пользователя
arseniiv в сообщении #1062353 писал(а):
Кстати, A001329
.

Цитата:
1, 1, 10, 3330, 178981952, 2483527537094825, 14325590003318891522275680

Я с помощью Mathematica смог найти число 3330. Так что это то самое. Mathematica считала около часа. Для следующего числа у Mathematica не хватило памяти. А что насчет аналитического выражения? Оно существует? Раз они считают численным методом, то получается, что аналитического выражения для произвольного $n$ нет.

arseniiv в сообщении #1062353 писал(а):
Группоидами зовут несколько вещей

Не знаю других вещей.
Группоид - универсальная алгебра с одной бинарной операцией. (Математическая энциклопедия)

 
 
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 01:44 
В принципе, не важно, что ещё им зовут, ведь я сам ввёл это слово в контекст (и магму тоже) и мог бы даже не упоминать, что оно многозначное. Посмотрите в англовики, например.

Meson в сообщении #1062364 писал(а):
А что насчет аналитического выражения? Оно существует? Раз они считают численным методом, то получается, что аналитического выражения для произвольного $n$ нет.
А ссылки смотрели? В том числе, если текстовое представление одной из формул не совсем понятно, она переписана в этом комментарии на Math.StackExchange. Формула страшная, но под «аналитическое выражение» сходить вполне должна.

 
 
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 01:58 
Аватара пользователя
arseniiv в сообщении #1062373 писал(а):
А ссылки смотрели?

Спасибо за информацию. Изучу. Приятно было узнать, что мой вопрос в каком-то смысле (пока непонятно в каком) решен.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group