2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: разбиения на подмножества
Сообщение07.11.2013, 12:09 
ET в сообщении #785917 писал(а):
Имхо, проще решать по-другому. Введем функцию $P(x)$ - число отношений эквивалентности на множестве из $x$ элементов. Эта функция неплохо выражается рекуррентно, и посчитать $P(1)$ , $P(2)$ , $P(3)$ , $P(4)$ , $P(5)$ , $P(6)$ у меня вчера (как увидел эту задачку) получилось за вполне недлинное время
Решать можно по-разному.
Например, воспользоваться готовой формулой: $$\sum_{k=1}^n\frac1{k!}\sum_{i=0}^{k-1}(-1)^i {k \choose i}(k-i)^n$$ Но приведенное ранее решение хорошо уже тем, что понятно. А той формулы, что привел я, спросонья можно и испугаться.

 
 
 
 Re: разбиения на подмножества
Сообщение08.11.2013, 07:32 
VAL в сообщении #785993 писал(а):
Но приведенное ранее решение хорошо уже тем, что понятно. А той формулы, что привел я, спросонья можно и испугаться.

Ну это как сказать насчет понятности. Два часа разбирались, как бы лишние подсчеты учесть. А через рекуррентное отношение там все очевидно и просто. Фиксируем один элемент. Он может быть в классе эквивалентности из одного этого элемента, из двух, трех и так далее. Число классов эквивалентности - это биноминальные коэффициенты, а число разбиений на классы эквивалентности оставшегося множества - это вычисленные ранее как я писал $P(x)$ Тут ошибиться можно только в случае крайней небрежности.

 
 
 
 Re: разбиения на подмножества
Сообщение08.11.2013, 11:00 
ET в сообщении #786243 писал(а):
VAL в сообщении #785993 писал(а):
Но приведенное ранее решение хорошо уже тем, что понятно. А той формулы, что привел я, спросонья можно и испугаться.

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

А вот Ваш подход и подход ТС могу сравнить, глядя, так сказать, со стороны.
Так вот, с моей стороны, подход ТС прозрачнее.
То, что при этом у него возникли некоторые затруднения, не доказывает, что Ваш метод привел бы его к цели за 5 минут :-)

 
 
 [ Сообщений: 18 ]  На страницу Пред.  1, 2


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