Математика - Теория на графите
Колко симетрични рефлексивни двоични отношения има върху набор от пет елемента?
дадено от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^$% рефлексивни симетрични отношения.