Задача такая: сколькими способами можно разбить множество из n элементов на подмножества, каждое из которых может быть размером от 1 до k? Так и не придумал, каким образом вывести формулу.

Можно свести к такой задаче:
Сколькими способами можно решить уравнение 1 * a1 + 2 * a2 + ... k * ak = n чтобы все а были целые и положительные. Правда не знаю, упрощает ли это задачу.

Спасибо. 

нет. неэквивалентны ни разу.


Классическая задача подбора суммы.

Поясняю: 
Возьмем за количество множеств размера 1 число а1. После отбора элементов в эти множества остается n - a1 элементов. Множества размеров 2 - а2 шт забирают из всех оставшихся 2 * а2 шт, имеем n - a1 - 2 * a2 элементов. Ну и в конце n - a1 - 2 * a2 - ... - k * ak = 0. 
Может быть, это имеет посредственное отношение к вопросу, но хотелось бы узнать, если мои рассуждения неправильные, то в чем именно.



Можно подробнее? Для меня этот ответ пустой. Хотя бы ссылку на классическое решение классической задачи привели бы. Спасибо. 

З.ы. попробовал погуглить "Классическая задача подбора суммы", что-то ничего похожего не нашлось.