Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers

up vote 1 down vote accepted

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)$.

share|improve this answer
add comment

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?

share|improve this answer
    
@ 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
add comment

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.