комбинаторика - Число разбиений

Простую формулу вывести пока не смог, за то могу предложить рекурсивную.
Пусть $%K_m^n$% - число разбиений множества из n элементов на m подмножеств, а $%Q_n$% - число разбиений множества из n элементов на любое количество подмножеств (т.е. то, что нужно по условию). При увеличении n на 1 мы можем разместить "новый" элемент двумя способами: или сформировать из него отдельное подмножество, или добавить его к одному из подмножеств с "предыдущего шага". То есть, $%K_m^{n+1}=K_{m-1}^n+mK_m^n$%. Добавив начальные условия, получим рекурсивную формулу: $$\begin{cases} K_0^n=0\\ K_{n+1}^n=0\\ K_1^1=1\\ K_m^{n+1}=K_{m-1}^n+mK_m^n\\ Q_n=\sum_{m=1}^n{K_m^n} \end{cases}$$ Что же касается асимптотики, то начиная с n=61 число разбиений превышает $%10^n$%.
Первые 15 чисел данной последовательности: 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545.
График $%\log_{10}Q_n$%:

Насчёт получения оценки снизу можно применить следующее соображение. Рассмотрим числа Белла с чётным номером $%2n$%. Ясно, что множество всех разбиений включает в себя множество разбиений на $%n$% пар. Для последней задачи ответ хорошо известен, и получается неравенство $$B_{2n}\ge(2n-1)(2n-3)\cdot\,\cdots\,\cdot3\cdot1.$$ Отсюда становится понятно, что числа Белла растут весьма быстро -- порядка корня из факториала, как минимум.

N(n1,n2,n3,...,nk)=n!/(n1!n2!n3!...nk!)