Computing number of permutations of two values, with a restriction on runs

Question

I was thinking about ways to solve this other question about counting the number of values whose digits sum to a target, and decided to try the case where the range was of the form [0, n^base). So essentially you get N independent digits to work with, which is a simpler problem.

The number of ways N natural numbers can sum to a target T is easy to compute. If you think of it as placing N-1 dividers among T sticks, you should see the answer is (T+N-1)!/(T!(N-1)!).

However, our N natural numbers are restricted to [0, base) and so there will be fewer possibilities. I want to find a simple formula for this case as well.

The first thing I considered was deducting the number of possibilities where 'base' of the sticks had been replaced with a 'big stick'. Unfortunately, some possibilities are double counted because they have multiple places a 'big stick' could be inserted.

Any ideas?

Answer 1

You can use generating functions.

Assuming that the order matters, then you are looking for the coefficient of x^T in

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

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

Using binomial theorem (works even for -n), you should be able to write you answer as a sum of products of binomial coefficients.

Let b+1 = B.

Using binomial theorem we have

(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

So the answer we need is:

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

for any r and s subject to the condition that

Br + s = T.