2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

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

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.