Counting number of pairs whose sum is less than k

Question

How many pairs $(x,y)$ such that $x+y <= k$, where x y and k are integers and $x,y>=0, k > 0$.

1. Solve by summation rules.
2. Solve by combinatorial argument.

 

Answer 1

It is similar to saying that we have to put n identical balls in two different boxes(the two boxes being x and y). This can be done in (k+1)!/(k!*1!) ways if x>=0 and y>=0.(How? see at end of  answer). In ques, we have to put i balls( such that 1<=i<=k) in two boxes. This can be done in  $\sum_{i=1}^{k}$ $\left \{ (i+1)!/(i!*1!)\right \}$

----------------------------------------------------------------------------------------------

Number of ways of putting n identical balls in p boxes such that boxes can be empty(obviously not all boxes can be empty):

Put the n balls linearly. Draw p-1  lines to divide this linear arrangement of balls in p partitions. Now we have to arrange n+(p-1) things such that n are of same kind and p-1 are of same kind. This can be done in (n+p-1)!/(n!*(p-1)!).