Вычисление количества перестановок двух значений с ограничением на прогоны

Question

Я думал о способах решения этого другого вопроса о подсчете количества значений, чьи цифры суммируются с целью , и решил попробовать случай, когда диапазон имел форму [0, n ^ база). По сути, вы получаете N независимых цифр для работы, что является более простой проблемой.

Число способов суммирования N натуральных чисел с целью T легко вычислить. Если вы думаете об этом как о размещении делителей N-1 среди T палочек, вы должны увидеть ответ (T + N-1)! / (T! (N-1)!).

Однако наши N натуральных чисел ограничены [0, основание), и поэтому будет меньше возможностей. Я хочу найти простую формулу и для этого случая.

Первое, что я рассмотрел, было вычитание количества возможностей, когда «основание» палочек было заменено на «большую палку». К сожалению, некоторые возможности учитываются дважды, потому что в них есть несколько мест, в которые можно вставить «большую палку».

Есть идеи?

Answer 1

Вы можете использовать функции генерации.

Предполагая, что порядок имеет значение, вы ищете коэффициент x^T в

(1 + x + x^2 + ... + x^b)(1 + x + x^2 + .. + x^b) ... n times

 = (x^(b+1) - 1)^n/(x-1)^n

Используя биномиальную теорему (работает даже для -n), вы должны иметь возможность написать свой ответ в виде суммы произведений биномиальных коэффициентов.

Пусть b + 1 = B.

Используя биномиальную теорему, мы имеем

(x^(b+1) - 1)^n = Sum_{r=0}^{n} (-1)^(n-r)* (n choose r) x^(Br)

1/(x-1)^n = Sum (n+s-1 choose s) x^s

Таким образом, нам нужен ответ:

Sum (-1)^(n-r) * (n choose r)*(n+s-1 choose s)

для любых r и s при условии, что

Br + s = T.