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$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ math.stackexchange.com/questions/1570989/… Relative question. $\endgroup$ – Rezwan Arefin May 11 '17 at 7:18
-
$\begingroup$ @RezwanArefin That question was also mine! $\endgroup$ – 0123456789101112 May 11 '17 at 7:18
Add a comment
|
$\begingroup$
$\endgroup$
6
It is the coefficient of $X^N$ in the expression $\prod_{i=1}^N(1+X+X^2+\dots +X^K)$
-
-
$\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
$\begingroup$
$\endgroup$
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$$
