2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Число элементов в множестве
Сообщение13.10.2015, 12:05 
Аватара пользователя


13/10/15
5
Может, кто-нибудь сталкивался с подобными задачами.
Найти число элементов в указанном множестве в зависимости от натурального числа $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 
Заслуженный участник


16/02/13
4105
Владивосток
Я б сначала задумался над $R$. Как-то мне не очевидно, что это эквивалентность.

 Профиль  
                  
 
 Re: Число элементов в множестве
Сообщение13.10.2015, 13:13 
Аватара пользователя


13/10/15
5
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 
Заслуженный участник


16/02/13
4105
Владивосток
Meson в сообщении #1061976 писал(а):
А так не очевиднее?
Как говаривал Фрэнк Дребин, «Это действительно очевидно. Теперь»

 Профиль  
                  
 
 Re: Число элементов в множестве
Сообщение13.10.2015, 23:57 
Заслуженный участник


27/04/09
28128
Проще говоря, надо найти число неизоморфных магм (алгебр с одной бинарной операцией) данного порядка.

(Оффтоп)

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

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

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

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

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

 Профиль  
                  
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 00:19 
Аватара пользователя


13/10/15
5
arseniiv в сообщении #1062329 писал(а):
Проще говоря, надо найти число неизоморфных магм (алгебр с одной бинарной операцией) данного порядка

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

 Профиль  
                  
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 00:55 
Заслуженный участник


27/04/09
28128
Кстати, A001329.

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

 Профиль  
                  
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 01:26 
Аватара пользователя


13/10/15
5
arseniiv в сообщении #1062353 писал(а):
Кстати, A001329
.

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

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

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

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

 Профиль  
                  
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 01:44 
Заслуженный участник


27/04/09
28128
В принципе, не важно, что ещё им зовут, ведь я сам ввёл это слово в контекст (и магму тоже) и мог бы даже не упоминать, что оно многозначное. Посмотрите в англовики, например.

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

 Профиль  
                  
 
 Re: Число элементов в множестве
Сообщение14.10.2015, 01:58 
Аватара пользователя


13/10/15
5
arseniiv в сообщении #1062373 писал(а):
А ссылки смотрели?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group