Сколько существует комбинаций, чтобы поместить n глав в k (<n) томов?

Question

Кроме того, как можно алгоритмически генерировать их в пределах полинома от n? Псевдокод в порядке.

Answer 1

Эта проблема сводится к выбору k-1 границы, которые делят n элементы в k частей. В качестве таких, k-1 позиции должны быть выбраны из n+k-1 позиции, в результате чего

возможности. В качестве примера, скажем, нам нужно разделить четыре сладости на трех детей. В этом случае первой возможностью будет поставить две границы на первые две позиции, оставив четыре конфеты в позициях 3-6:

Таким образом, первые двое детей не получают конфет, а третий ребенок получает всех четверых. Другой возможностью было бы поместить первую границу в позицию 2, а вторую границу в позицию 4:

Теперь первые двое детей получают по одной конфете каждый (позиции 1 и 3), а третий ребенок получает двоих (позиции 5-6). Итерирование по всем позициям дает в общей сложности 15 возможностей.

Обратите внимание, что ответ будет разным, если во всех томах должна быть хотя бы одна глава. В этом случае, k предметы уже даны в один том каждый, оставляя n-k главы. Таким образом, есть

возможности. Обратите внимание, что условие k<n важно в этом случае.