in Combinatory
883 views
4 votes
4 votes

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.

 

in Combinatory
by
883 views

1 Answer

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

Related questions