математика - Теорія графів
Скільки існує симетричних рефлексивних бінарних відносин на безлічі з п'яти елементів?
заданий18 Чер '16 15:33
@pavel1076: Ви виявили кількість впорядкованих пар. Це не число бінарних відносин із зазначеними властивостями.
@falcao зараз прочитаю, що Ви написали
@Ladence тут по 4 коментарі можна залишати під кожним постом, тому пишу тут. Останній Ваш коментар я не розумію
@Ladence: про всяк випадок додам одне зауваження. У нас кожної клітини є кількість способів її заповнення. Ці числа перемножуються. Якщо обмежень немає, скрізь виходить 2. Якщо клітина заповнюється однозначно, то спосіб один, і ми можемо або примножувати на 1, діючи за шаблоном, або просто ігнорувати цей момент, заповнюючи клітину однозначно, і не враховуючи це в процесі перемножень.
Розглянемо таблицю 5x5, рядки та стовпці якої відповідають елементам множини. Можна вважати, що вони просто пронумеровані, а багато складається з елементів $%\$%.
Кожному бінарному відношенню однозначно відповідає заповнення таблиці, скажімо, плюсами та мінусами. Якщо елемент $%a$% знаходиться з $%b$% у цьому відношенні, то в клітину $%(a,b)$% ставимо плюс. Інакше - мінус.
Звідси ясно, що загальна кількість бінарних відносин дорівнюватиме $%2^$%: на кожному з 25 послідовних етапів (за кількістю клітин) ми двома способами можемо заповнити цю клітину. За правилом твору ці кількості способів перемножуються.
Нехай ми знаємо, що ставлення є рефлексивним. Тоді на головній діагоналі стоять усі плюси. Поставимо їх і далі заповнимо таблицю довільно. У нас залишилося 20 "ступенів свободи" замість 25, тому рефлексивних відносин буде $%2^$%.
Тепер нехай ставлення рефлексивне та симетричне.Знову ставимо плюси по головній діагоналі. З 20 клітин половина розташована вище головної діагоналі. Заповнюємо цю частину таблиці, як хочемо. Для цього є $%2^$% способів. Нижня частина таблиці тепер заповнюється однозначно: значок таблиці в клітині $%(a,b)$% через симетричність має бути той самий, що й у клітині $%(b,a)$%. Тому інформація з верхньої частини просто копіюється в нижню за допомогою відображення щодо головної діагоналі.
У випадку, якщо елементів безлічі $%n$%, вийде точно $%2^$% рефлексивних симетричних відносин.