GATE CSE 2002 | Question: 13

Question

1. In how many ways can a given positive integer $n \geq 2$ be expressed as the sum of $2$ positive integers (which are not necessarily distinct). For example, for $n=3$, the number of ways is $2$, i.e., $1+2, 2+1$. Give only the answer without any explanation.
2. In how many ways can a given positive integer $n \geq 3$ be expressed as the sum of $3$ positive integers (which are not necessarily distinct). For example, for $n=4$, the number of ways is $3$, i.e., $1+2+1, 2+1+1$ and $1+1+2$. Give only the answer without explanation.
3. In how many ways can a given positive integer $n \geq k$ be expressed as the sum of $k$ positive integers (which are not necessarily distinct). Give only the answer without explanation.

Answer 1

1. $n= 2 \left(1+1\right),\;n=3\left(1+2, 2+1\right),\\n=4\left(1+3,3+1,2+2\right),\;n=5\left(1+4,4+1,2+3,3+2\right)$
   so $x_1+x_2=n\;\text{and}\;x_1,x_2>{0}$ (no.of integral sol)
   This is same as number of ways of putting $\left(n-2\right)$  (as we can't have $0$ for either $x_1$ or $x_2$) identical balls into two distinct bins, which is obtained by putting a divider across $\left(n-2\right)$ balls and taking all possible permutations with $\left(n-2\right)$ being identical. i.e., $\frac{(n-2 + 1)!}{(n-2)!} = (n-1).$
   We can also use the following formula ,
   $^{(n-2+2-1)}C_{(2-1)}=^{n-1}C_1.$
    
2. $n=3\left(1+1+1\right),\;n=4\left(1+1+2,1+2+1,2+1+1\right),\\ n=5\left(1+1+3,1+3+1,3+1+1,2+2+1,2+1+2,1+2+2\right) $
   so $x_1+x_2+x_3=n\;\text{and}\;x_1,x_2,x_3>0$ (no.of integral sol) 
   Here, we can permute $\left(n-3\right)$ items with $2$ dividers which will give $\frac{(n-3 + 2)!}{(n-3)!2!}$
   $\begin{align}&=\frac{\left(n-1\right)!}{\left(n-1-2\right)!2!}\\\\&=\;^{n-1}C_2\end{align}$
    
3. $^{(n-k+k-1)}C_{k-1}=^{n-1}C_{k-1}.$

Comments

All a,b, and c is solved using star-bar problem by taking 1 bar in case of a, 2 in case of b and k-1 in case of c

---

nice question gate 2002 thank you

---

nice explaination

Answer 2

We know that the no. of +ve integral solution to the equation $x_{1} + x_{2} + x_{3}+ ... + x_{k} = n$ is given by $\binom{n-1}{k-1}$.

(a) Let, $x_{1}$ and $x_{2}$ be the two positive integers (not necessarily distinct) such that their sum is equal to $n\ (n≥2)$.

Therefore, $x_{1} + x_{2} = n$. 

Now, we have to find all such values of $x_{1}$ and $x_{2}$ that satisfy the above equation. In other words, the problem basically reduces to  finding the no. of +ve integral solution to the above equation.

Therefore, the req. no. of ways is $\binom{n-1}{2-1} = \binom{n-1}{1}$. 

(b) Let, $x_{1}$, $x_{2}$ and $x_{3}$ be the three positive integers (not necessarily distinct) such that their sum is equal to $n\ (n≥3)$.

Therefore, $x_{1} + x_{2} + x_{3} = n$. 

Now, we have to find all such values of $x_{1}$, $x_{2}$ and $x_{3}$ that satisfy the above equation. In other words, the problem basically reduces to  finding the no. of +ve integral solution to the above equation.

Therefore, the req. no. of ways is $\binom{n-1}{3-1} = \binom{n-1}{2}$.

(c) Let, $x_{1}$, $x_{2}$, $x_{3}$,...,$x_{k}$ be the $k$ positive integers (not necessarily distinct) such that their sum is equal to $n\ (n≥k)$.

Therefore, $x_{1} + x_{2} + x_{3}+ ... + x_{k} = n$. 

Now, we have to find all such values of $x_{1}$, $x_{2}$, $x_{3}$,...,$x_{k}$ that satisfy the above equation. In other words, the problem basically reduces to  finding the no. of +ve integral solution to the above equation.

Therefore, the req. no. of ways is $\binom{n-1}{k-1}$.

      

Answer 3

The above three questions are based on a single logic which is Indistinguishable Objects and Distinguishable Boxes (IODB) why??

Here positive integers don’t matter the same as objects but in which box you are putting that matters for example here there are two boxes in question (a) so both are distinguishable as 1 + 2 and 2 + 1 are different things.

To solve IODB problems think of it as a star-bar problem means objects are stars and the divider between two objects is a bar like in 1 + 2 → 1 and 2 are objects while + is considered as a bar.

Formula used in this IODB template is  $\binom{total number of stars  + total number of bars}{total number of stars}$ = $\binom{total number of stars  + total number of bars}{total number of bars}$

Question a). There are n objects such that value of n >= 2 so at the beginning we will give 2 objects so now we will have n -2 objects or n -2 starts; since we want it as the sum of two positive integers so number of bar = 1.

total number of ways here will be $\binom{n-2 +1}{1}$ { It is simple to use as it is one of the templates in Combinatorics}  

which is equal to  $\binom{n-1}{1}$.

Question b). here there are n –3 stars and two bars so the answer will be  $\binom{n-3 +2}{2}$ =  $\binom{n-1}{2}$.

Question c). here we are already providing k objects so there are left with n – k objects so there are n – k stars and k-1 bars

$\binom{n-k+k -1}{k -1}$ = $\binom{n – 1}{k – 1}$

 { PS:  TO understand IODB template watch Goclasses combinatorics lecture I am not advertising that but that is really awesome. }

Comments

Nice answer, Just a Typo in option C, must be:  n – k stars and k-1 bars. 

---

Very clear explanation!

Answer 4

SIMPLY APPLY THE LOGIC:

x1+x2+x3+x4+...........xn=r   where x1,x2.....xn>=0    apply c(n+r-1,r)  

make similarly all the 3 cases in order that it satisfies the equation

a-  x1+x2=n where x1,x2>=1 so make it x1+x2=n-2 now x1,x2>=0 so c(n-2+2-1,1)=n-1

b-x1+x2+x3=n where x1,x2,x3>=1 so x1+x2+x3=n-3 so c(n-3+3-1,2)=c(n-1,2)

c-x1+x2+.....xk=n where x1,x2,x3....xk>=n so x1+x2+x3+....xk=n-k=c(n-k+k-1,k-1)=c(n-1,k-1)

Answer 5

(a) Total no of ways = C(n-1 ,1) = n-1

(b)Total no of ways = C(n-1 ,n-3) = C(n-1 ,2) = (n-1)⨉(n-2) /2

(c)Total no of ways = C(n-k+k-1 ,n-k) = C(n-1 , n-k) = C(n-1 , k-1)

Answer 6

For Distinct  k positive integers : (n+k-1)C(k-1)

For Non-Distinct  k positive integers : (n-1)C(k-1)