計算兩個值的排列數，並對運行進行限制

Question

我在想如何解決this other question about counting the number of values whose digits sum to a target，並決定嘗試範圍是[0，n^base]形式的情況。所以基本上你得到N個獨立的數字來處理，這是一個更簡單的問題。

N個自然數可以與目標T求和的方法數很容易計算。如果你認爲它是將N-1個分隔條放在T條中，你應該看到答案是（T + N-1）！/（T！（N-1）！）。

但是，我們的N個自然數僅限於[0，基數），因此可能性會更少。我也想爲這種情況找到一個簡單的公式。

我考慮的第一件事是扣除棍棒'基部'被'大棒'取代的可能性數量。不幸的是，有些可能性被重複計算，因爲它們有多個地方可以插入「大棒」。

任何想法？

Answer 1

您可以使用生成函數。

假設順序的問題，那麼你在

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

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

尋找的x^T係數使用二項式定理（作品甚至-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.