3 votes

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

- Solve by summation rules.
- Solve by combinatorial argument.

1 vote

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

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

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