разбиения на подмножества

[VAL]

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$$

Но приведенное ранее решение хорошо уже тем, что понятно. А той формулы, что привел я, спросонья можно и испугаться.

[ET]

VAL в сообщении #785993 писал(а):

Но приведенное ранее решение хорошо уже тем, что понятно. А той формулы, что привел я, спросонья можно и испугаться.

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

[VAL]

ET в сообщении #786243 писал(а):

VAL в сообщении #785993 писал(а):

Но приведенное ранее решение хорошо уже тем, что понятно. А той формулы, что привел я, спросонья можно и испугаться.

Ну это как сказать насчет понятности. Два часа разбирались, как бы лишние подсчеты учесть. А через рекуррентное отношение там все очевидно и просто.

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

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