# Number of solutions to $a_1 + a_2 + a_3 + \cdots + a_n = N;\; 1\leq a_i \leq K$

How can I find the number of solution to this - $$a_1 + a_2 + a_3 + \cdots + a_n = N;\; 1\leq a_i \leq K$$
I know stars and bard theorem. I can solve if it was said that $a_i \geq K$. Then we can set $a_i' = a_i - K$ and convert that to $$a_1' + a_2' + a_3' + \cdots a_n' = N + Kn;\; a_i \geq 0$$
Then the number of solutions will be $$\binom{N+Kn + n - 1}{n-1}$$ But how can I handle this when $a_i \leq K$

## 2 Answers

It is the coefficient of $X^N$ in the expression $\prod_{i=1}^N(1+X+X^2+\dots +X^K)$

• How can I find that! :( – 0123456789101112 May 11 '17 at 7:18
• Using the multinomial theorem :P – user379195 May 11 '17 at 7:19
• I don't know that :( Can you please explain a little bit more? – 0123456789101112 May 11 '17 at 7:20
• I don't think there's a closed form expression. – user379195 May 11 '17 at 7:23
• Is the equation equivalent to ${(1+x+x^2 + \cdots x^k)}^n$ – 0123456789101112 May 11 '17 at 7:27

Consider the 3 problems below:

Problem A: $$x_1+\cdots+x_n=N\\s.t.~x_i\geq0~\forall i, ~\text{and}~x_1\geq k+1$$ Problem B: $$x_1+\cdots+x_n=N\\s.t.~x_i\geq0~\forall i, ~\text{and}~x_j\geq k+1~\text{for some}~j$$ Problem C: $$x_1+\cdots+x_n=N\\s.t.~x_i\geq0~\forall i$$ Problem D: $$x_1+\cdots+x_n=N\\s.t.~0\leq x_i\leq k~\forall i$$ Problem E: $$x_1+\cdots+x_n=N-k-1\\s.t.~x_i\geq0~\forall i$$ Let $N_a.N_b,N_c,N_d$ be the number of solutions to Problem A,B,C,D respectively. Then $$N_d=N_c-N_b$$$$N_b=n!\times N_a$$$$N_a=N_e$$