How many solutions does this inequality have in non negative integers $x_i$:

$n \leq x_1+x_2+x_3+ \dots +x_n \le 2n$ ? Im stumped

I know I should add another variable but...I don't know.

  • $\begingroup$ I'm not sure I understand what you're asking... $\endgroup$ – mojambo Nov 9 '13 at 14:29
  • $\begingroup$ How many different combinatios are there for x(1) x(2) etc that are non negative and integer, that satisfy this inequality $\endgroup$ – Oria Gruber Nov 9 '13 at 14:31
  • $\begingroup$ u mean $x_1 + x_2 + ... x_n$ ??? $\endgroup$ – PleaseHelp Nov 9 '13 at 14:35
  • $\begingroup$ yes! I just don't know how to write it in mathjax :P $\endgroup$ – Oria Gruber Nov 9 '13 at 14:36
  • $\begingroup$ You want the number different combinations of non-negative integers $x_1,\dots,x_n$ such that $n\leq x_1+\dots+x_n \leq 2n$? $\endgroup$ – mojambo Nov 9 '13 at 14:37

Suppose $s$ is positive integer. Now create a row of $n + s - 1$ blanks, and imagine you have $s-1$ $o$s and $n-1$ $x$s . There are ${n+s-1 \choose n-1}$ ways to position the $x$s in the blanks. There is one way to position the $o$s. Each of these permutations represents a solution to the equation $$\sum_{k=1}^n x_k = s, \qquad x_k \ge 0, 1\le k \le n.$$ This correspondence is achieved by letting $x_1$ be the number of $o$s as the beginning, $x_2$, be the number of $o$s between $x_1$ and $x_2$, etc. So this equation has ${n+s-1\choose n-1}$ solutions.

Now do some summation to get the solution to your problem.


Using generating functions,

The number of solutions of $x_1 + x_2 + x_3 + \dots + x_n = m$ is given by the coefficient of $x^m$ in $(1+x+x^2+...)^n = \dfrac1{(1-x)^n}$

So the number of solutions of $x_1 + x_2 + x_3 + \dots + x_n \le m$ is given by the coefficient of $x^m$ in $\dfrac1{(1-x)^{n+1}}$. Say this is $f(m)$. Then you need $f(2n)-f(n-1)$.

By the extended binomial theorem, $f(m) = \dfrac{(n+1)(n+2)(n+3)\dots(n+m)}{m!} = \binom{n+m}{m}$, so you can work out that $$f(2n)-f(n-1) = \binom{3n}{n}-\binom{2n-1}{n}$$ is what you seek.

  • $\begingroup$ +1 Though, this can be approached directly with stars and bars without generating functions. It's an overkill. $\endgroup$ – Calvin Lin Nov 9 '13 at 15:47

Hint: The number of (non-negative integer) solutions to

$$ x_1 + x_2 + \ldots + x_n \leq k, $$

is equal to the number of solutions to

$$x_1 + x_2 + \ldots + x_n + x_{n+1} = k, $$

which by stars and bars is ${ n+1 + k -1 \choose n}.$ $_\square$

Hence, conclude that the number of ways is ${3n \choose n } - { 2n-1 \choose n}$.

  • $\begingroup$ Yes, that's simpler. +1 $\endgroup$ – Macavity Nov 9 '13 at 15:51

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.