2
$\begingroup$

I know stars and bars theorem. I can solve $a_1 + a_2 + a_3 + \cdots + a_n = N;\; 1\leq a_i \leq K$, if $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 $\dbinom{N+Kn + n - 1}{n-1}$.

But how can I handle this when $a_i \leq K$ ?

$\endgroup$
3

2 Answers 2

Reset to default
1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .