Сколько существует симметричных рефлексивных бинарных отношений на множестве из пяти элементов ?

задан 18 Июн '16 15:33

@pavel1076: Вы нашли число упорядоченных пар. Это не есть число бинарных отношений с указанными свойствами.

(18 Июн '16 15:57) falcao

@falcao сейчас прочитаю, что Вы написали

(18 Июн '16 15:58) pavel1076

@Ladence тут по 4 коментария можно оставлять под каждым постом, поэтому пишу здесь. Последний Ваш коментарий я не понимаю

(18 Июн '16 16:36) pavel1076

@Ladence: на всякий случай добавлю одно замечание. У нас для каждой клетки есть количество способов её заполнения. Эти числа перемножаются. Если ограничений нет, то везде получается 2. Если клетка заполняется однозначно, то способ один, и мы можем либо домножать на 1, действуя по шаблону, или просто игнорировать этот момент, заполняя клетку однозначно, и не учитывая это в ходе процесса перемножений.

(18 Июн '16 16:49) falcao
10|600 символов нужно символов осталось
1

Рассмотрим таблицу 5x5, строки и столбцы которой соответствуют элементам множества. Можно считать, что они просто пронумерованы, а множество состоит из элементов $%\{1,2,3,4,5\}$%.

Каждому бинарному отношению однозначно соответствует заполнение таблицы, скажем, плюсами и минусами. Если элемент $%a$% находится с $%b$% в данном отношении, то в клетку $%(a,b)$% ставим плюс. В противном случае -- минус.

Отсюда ясно, что общее число бинарных отношений будет равно $%2^{25}$%: на каждом из 25 последовательных этапов (по числу клеток) мы двумя способами можем заполнить данную клетку. По правилу произведения, эти количества способов перемножаются.

Пусть мы знаем, что отношение рефлексивно. Тогда на главной диагонали стоят все плюсы. Поставим их, и далее заполним таблицу произвольно. У нас осталось 20 "степеней свободы" вместо 25, поэтому рефлексивных отношений будет $%2^{20}$%.

Теперь пусть отношение рефлексивно и симметрично. Снова ставим плюсы по главной диагонали. Из 20 клеток, половина расположена выше главной диагонали. Заполняем эту часть таблицы как хотим. Для этого имеется $%2^{10}$% способов. Нижняя часть таблицы теперь заполняется однозначно: значок таблицы в клетке $%(a,b)$% в силу симметричности должен быть тот же, что и в клетке $%(b,a)$%. Поэтому информация из верхней части просто копируется в нижнюю, посредством отражения относительно главной диагонали.

В общем случае, если элементов множества $%n$%, получится в точности $%2^{n(n-1)/2}$% рефлексивных симметричных отношений.

ссылка

отвечен 18 Июн '16 15:56

А, всё, понял, отношение же это множество и вопрос был в том, сколько таких множеств можно получить.

(18 Июн '16 16:05) pavel1076
1

@pavel1076: да, конечно. Отношение -- это "база данных", которая содержит информацию о том, что с чем находится в этом отношении. То есть это некоторое множество упорядоченных пар.

(18 Июн '16 16:14) falcao

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

(18 Июн '16 16:18) pavel1076

@Ladence это стандартная вещь в комбинаторике, что у множества из n элементов 2^n подмножеств

(18 Июн '16 16:22) pavel1076

@pavel1076 , да , это действительно очевидно , понял только после того как написал комментарий . @falcao теперь меня ввело в заблуждение как вы посчитали посчитали отражение относительно главной диагонали , т.е. все было понятно до того момента как мы начали считать симметричные отношения

(18 Июн '16 16:28) Ladence

@Ladence если a,b состоят в симметричном отношении, нет смысла говорить, что b,a там тоже состоят, потому что мы 2 раза будем считать эту (неупорядоченную) пару.

Этого не нужно делать, потому что p(a,b)<=>p(b,a).

(18 Июн '16 16:30) pavel1076

@pavel1076 так верхнюю часть матрицы смежности мы заполнили произвольно , как теперь отобразить это в нижней части (с точки зрения комбинаторики)

(18 Июн '16 16:34) Ladence

@pavel1076 @falcao кажется я разобрался , огромное спасибо за помощь !

(18 Июн '16 16:35) Ladence
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,326
×1,258
×474
×155

задан
18 Июн '16 15:33

показан
2337 раз

обновлен
18 Июн '16 16:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru