Number of non negative integer solutions with additional restriction Find the number of non negative integer solutions to
$$x_1+x_2+....x_k=n$$ with the additional constraints $$x_i < s,  \forall i \in [1,k], i\in Z$$

This is how I tried.

*

*The number of non negative integer solutions to
$x_1+x_2+....x_k=n$ without the constraints is: (Call it $A_0$)

$$ n+k-1 \choose k-1 $$
This can be found using standard ball & stick argument.


*We need to apply Inclusion Exclusion Principle Now:

Let $P_i$ be the property that the $i^{th}$ $x_i$ violates the constraints. Then let $A_i$ be the set of non negative integer solution of $x_1+x_2+....x_k=n$ with the additional constraint $x_i < s$ does not hold. i.e $x_i \geq s$
Then |$A_i$| is $n-s+k-1 \choose k-1$ (Is this correct?)


*The number of required solution is then:
$$|A_0| - |A_1 \cap .... \cap A_K|$$


*Then by Inclusion Exclusion Principle:
$|A_1 \cap .... \cap A_K|$ can be calculated
Now how to proceed from here? How do I get my final answer in terms of $n,k,s$
 A: To approach this problem, what we must understand first is how the formula for the number of non-negative integral solutions with no restrictions is derived. It all stems from the Binomial Theorem. Consider this- you have a polynomial $$(x^0 + x^1 + x^2 + x^3 + ...)^n$$ The coefficient of $x^r$ in this expression is actually the number of non-negative integral solutions of $$a_1 + a_2 + a_3 + ... + a_n = r $$ How is that? Well, consider how the term $x^r$ is to be obtained. We choose one particular term $x^a$ from each of the n factors and at the end, after multiplying all the chosen terms from each bracket the resultant power of x must be r. In other words, $a_1 + a_2 + a_3 + ... + a_n = r $. Note that here $a_1, a_2, ... a_n$ are all non-negative as we have no negative power in our factors. Suppose this choosing of terms can be done in $k$ different ways. Then each of those choices would contribute one $x^r$ to the final expression. Which implies that the coefficient of $x^r$ in this polynomial would be $k$, which is our required answer.
Putting this idea into action, we obtain $$\begin{aligned}k &= \text{coefficient of } x^r \text{ in } (x^0 + x^1 + x^2 + x^3 + ...)^n \\ &= \text{coefficient of } x^r \text{ in } \left(\frac{1}{1-x}\right)^n \text{ [Assuming x<1 WLOG as x plays no role in our derivation]} \\ &= \text{coefficient of } x^r \text{ in } (1-x)^{-n} \\ &=  ^{r+n-1}C_{n-1} \end{aligned}$$ The above result can be found in any high-school algebra textbook. Refer here for the proof.
Now, once we have understood the above derivation, this problem can be solved quite easily. What we need to do is find the coefficient of $x^r$ in $$ (x^0 + x^1 + x^2 + x^3 + ... + x^{s-1})^n $$ which simplifies to $$\begin{aligned} \text{coefficient of } x^r \text{ in } \left(\frac{1 \times (1-x^s)}{1-x}\right)^n  &= \text{coefficient of } x^r \text{ in } (1-x^s)^n (1-x)^{-n}\end{aligned}$$
Therefore, the answer you desire in terms of $n,k,s$ according to your definition is simply $$ \text{coefficient of } x^n \text{ in } (1-x^s)^k (1-x)^{-k} $$To proceed further, we would need specific values of $n,k,s$ and evaluate the coefficient according to the standard algebra textbook process.
