Комбинаторика на отрезке

а что мешает взять оставшееся место m-n*k и представить в виде единичных отрезков, а потом посчитать кол-во перестановок?

Во первых они одинаковые (т е перестановки тут не при чем), т.е. порядок не важен. Но важны интервалы между ними. Т.е
<---+++-+++-+++->
<--+++--+++--+++>
это разные расположения

они одинаковые

это видно из условия

т.е. порядок не важен

но очевидно считай тогда сочетания: https://ru.wikipedia.org/wiki/Сочетание#.D0.A1.D0.BE.D1.87.D0.B5.D1.82.D0.B0....

Это разные расположения
<---+++-+++-+++-> и <--+++--+++--+++>
Это
<---+++-+++-+++-> and <-+++-+++-+++--->
тоже разные. Сочетания этот кейс никак не обрабатывают. Единственное уточнение, что в каждом расположении должны участвовать все k отрезков.

Все правильно же. https://en.m.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Stars - твои отрезки по m. Bars - «свободные» m-nk элементы.

Вот такое решение пришло в голову:

Если зафиксировать последовательность k отрезков, сколькими способами можно их разместить на отрезке не меняя порядка?

Весь целевой отрезок можно представить как m1*k1*m2*k2*...*kn*m(n+1). Нужно найти сколько существует способов заполнения вектора <m1 ... m(n+1)> целыми положительными числами, при том что их сумма всегда должна быть равна недостаче в длине суммы k1..kn до длины m.

Если эту сумму обозначить как m', то каждый из n+1 промежутков получит от 0 до m' целых единиц. Значит, с другой стороны, каждую из m' единиц можно приписать к одному из n+1 отрезков, и число способов это сделать равно числу сочетаний с повторениями из n+1 по m'.

Теперь, значя число способов разместить k отрезков в зафиксированной последовательности, надо домножить его на количество таких последовательностей (т.е. k! в данном случае).