# Homework - combinatorics

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.

• I'm not sure I understand what you're asking... – mojambo Nov 9 '13 at 14:29
• How many different combinatios are there for x(1) x(2) etc that are non negative and integer, that satisfy this inequality – Oria Gruber Nov 9 '13 at 14:31
• u mean $x_1 + x_2 + ... x_n$ ??? – PleaseHelp Nov 9 '13 at 14:35
• yes! I just don't know how to write it in mathjax :P – Oria Gruber Nov 9 '13 at 14:36
• 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$? – mojambo Nov 9 '13 at 14:37

## 3 Answers

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.

• +1 Though, this can be approached directly with stars and bars without generating functions. It's an overkill. – 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}$.

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