# Combinatorics-discrete mathematics

Count the solutions in nonnegative integers $x_1,\ldots,x_k$ to $x_1 + \cdots + x_k \leq n$.

Can someone please help with the solution?

-
Can you solve the problem with $\le$ replaced by $=$? If so, can you think of a clever way to turn your inequality to an equality? (Hint: add one extra variable.) –  mrf Jan 29 '13 at 13:51
Sarah: since you're fairly new, you might like to know that you can accept one answer per question: click on the "greyed out" check-mark to the left of the answer you want to accept. Once you earn >= 30 rep, you can upvote as many answers as you'd like! –  amWhy Feb 5 '13 at 15:37

## 3 Answers

Add an extra variable $x_{k+1}$ and count the solutions in non-negative integers to the equation

$$x_1+x_2+\ldots+x_k+x_{k+1}=n\;;\tag{1}$$

this is a standard stars-and-bars problem, and the answer is $$\binom{n+(k+1)-1}{(k+1)-1}=\binom{n+k}k\;.$$ (The reasoning behind this is reasonably well explained in the linked article.) Every solution to $(1)$ gives you a solution to your inequality by simply throwing away $x_{k+1}$. On the other hand, if

$$x_1+x_2+\ldots+x_k\le n\;,$$

then you can set $x_{k+1}=n-(x_1+x_2+\ldots+x_k)$ to get a solution to $(1)$. Thus, there are exactly as many solutions to your inequality as there are solutions to $(1)$.

-

It seems that you can write

$0$ in $1$ way, $0 + 0 + \dots + 0$

$1$ in $k$ ways, $1 + 0 + 0 + \dots$, $0 + 1 + 0 + \dots$

$2$ in $k + {k \choose 2}$ ways, $2 + 0 + \dots$, $\dots$ and $1 + 1 + 0 + \dots$, $\dots$

$3$ in $k + {k \choose 2} + {k \choose 3}$ ways

Can you generalize and use this information to compute what you asked?

-
@ mrf for x1 + x2 + ... + xk = n, now I think it would be (n+k-1) choose (k-1). –  Sarah Jan 29 '13 at 14:01

hint:if $x_1 + ... + x_r+ = n$ then define this function $$f(x)=\sum_{r=0}^\infty b_r\frac{x^r}{r!}$$ and answer is coefficient of $\frac{x^r}{r!}$ in f(x)( f(x) is generate function) or answer is n!$n \choose k+1$ for this question at first add $x_{k+1}$ then we have $$x_1 + ... + x_k+ x_{k+1} = n$$ and according to above answer is : n!$n \choose k+1$

-
Thank you for your response, but I haven't learnt the formula you used ... so is there possibly another way to solve it? –  Sarah Jan 29 '13 at 15:07
Could you clean up your Latex? I do not understand what your \quads are for, and you should put them in separate \$, otherwise it screws up the view. –  Calvin Lin Jan 29 '13 at 17:08
thanks calvin lin –  Maisam Hedyelloo Jan 29 '13 at 19:05