Number of solutions for $x_1+ x_2+ x_3 + \cdots + x_k=n$, where $0\leq x_i\leq p$ for all $i$

Question

I know that for $1\leq x_i\leq p$ the answer will be the coefficient of $x^n$ in $(x + x^2 + x^3 + ... + x^p)^k$. But what will be the answer for the constraint $0 \leq x_i \leq p?$

Also, how can I generate a definite formula or recurrence relation to program it? It will be difficult to calculate the answer by summing up the GP series and then calculating the coefficients using series expansion.

Thank you!

Answer 1

You can use your generating function approach just putting an $x^0=1$ term in and getting $(1+x + x^2 + x^3 + ... + x^p)^k$

Answer 2

For any fixed $p,k$ you look at the generating function $((1-x^{p+1})/(1-x))^k$ and the coefficient of $x^n$ is the answer $a(n)$. The generating function factors as $(1-x^{p+1})^k (1-x)^{-k}$ and each of these involves binomial coefficients. Thus the product coefficients is given by a sum involving products of binomial coefficients. $$a(n) = \sum_{i=0}^{\left\lfloor(n+1)/(p+1)\right\rfloor} (-1)^i {k \choose i} {n-(p+1)i+k-1 \choose k-1}.$$

Answer 3

You can use inclusion-exclusion in the complement form.

The total set $S$ is the set of all non-negative integer solutions to $x_1 + \ldots x_k = n$. The to-be-avoided conditions are $S_i$ are all such solutions such that $x_i > p$.

Then all good solutions (so where all $x_i \le p$) is (see wikipedia entry on inclusion-exclusion):

$$|S| - \sum_{i=1}^k |S_i| + \sum_{\{i,j\}} |S_i \cap S_j| + \ldots \sum_{S' \subset \{1,\ldots, k\} |S'| = t}(-1)^t \left(\cap_{j \in S'} S_j)\right| + +\ldots (-1)^n\left|\cap_{i=1}^n S_i\right|$$

The number of solutions in $S_i$ ,for some fixed $i$, is all solutions that have $x_i >p$, so we subtract $p+1$ from $x_i$ and see that its suffices to count all solutions in non-negative integers o$x_1 + \ldots x_k = n-p$ which equals $\binom{n-p + (k-1)}{k-1}$, and we have $k$ times that condition, so the first term in the sum bemes $-k\binom{n+k - (p+1)}{k-1}$. For two conditions we consider $n-2(p+1)$ for $k$ variables and there are $\binom{k}{2}$ subsets $\{i,j\}$ to consider for $S_i \cap S_j$, which all have the same size, etc. This can go on so long as $tp \le n$ of course, and any terms with larger than $t$-subsets of conditions become $0$ in this sum.

So you get a nice alternating sum representation (a closed formula, linked to in one of the comments).