Log In
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$.

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


in Combinatory 261 views

1 Answer

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

Related questions

14 votes
2 answers
Use the patterns given to prove that $\sum\limits_{i=0}^{n-1} (2i+1) = n^2$ (You are not permitted to employ induction) Use the result obtained in (a) to prove that $\sum\limits_{i=1}^{n} i = \frac{n(n+1)}{2}$
asked Oct 6, 2014 in Combinatory Kathleen 687 views
6 votes
2 answers
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ I have to check that it is Turing Recognizable or not (i.e R.E) My Approach/Doubt Question taken from ... $100$ $T_{yes}\subset T_{no}$. Hence it is not RE.But in the solution it is R.E.
asked Sep 9, 2017 in Theory of Computation sourav. 1.7k views
3 votes
2 answers
Prove the identity: $\begin{align*} &\sum_{i=0}^{n}\sum_{j=0}^{i} a_ia_j = \frac{1}{2}\left ( \left ( \sum_{i=0}^{n}a_i \right )^2 + \left ( \sum_{i=0}^{n}a_i^2 \right )\right ) \end{align*}$
asked Feb 25, 2017 in Combinatory dd 306 views
1 vote
4 answers
This is a question from Operating System concepts by Silberschatz, Gagne and Galvin. On very first go I could make that in such a situation deadlock can never occur. But doing guess work is a really bad habit and risky to. So I did some paper work using ... such question and proper explanation of the answer. I'm curious to know how you guys would have solved this question. Thanks in advance.
asked Jun 27, 2015 in Operating System Prateek Dwivedi 7.4k views