2014 dxdy logo

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

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




 
 Количество транзитивных бинарных отношений множ-ва объема n
Сообщение18.02.2007, 13:45 
Помогите, пожалуйста, решить такую задачу (или поскажите источники, где рассматривается что-то хоть чуть-чуть похожее):

Пусть задано некое конечное множество A из n элементов. Кол-во различных бинарных отношений над ним, очевидно, $2^{n^2}$. А каково кол-во тех из них, которые обладают свойством транзитивности?

 
 
 
 
Сообщение20.02.2007, 00:29 
Аватара пользователя
:evil:
См. A006905. Там же ссылки.

Для известных членов $\frac{\log\log N}{\log n}$ растет, но $\frac{\log\log N}{\log n \log\log n}$ убывает. По внешнему виду, вторая оценка смотрится лучше (что может быть и не правда, слишком мало членов известно…).

 
 
 
 
Сообщение20.02.2007, 18:51 
Большое спасибо

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


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