GATE CSE 1999 | Question: 1.3

Question

The number of binary strings of $n$ zeros and $k$ ones in which no two ones are adjacent is

• A. $^{n-1}C_k$
• B. $^nC_k$
• C. $^nC_{k+1}$
• D. None of the above

Comments

but that's the actual gate question mentioned with the condition so I asked him to edit and if the mention that condition the possibility we have to consider all the possibilities for n=k-1,k,k+1..... and that's what i wrote above anyways  for both we get none of the above ...they didn't mention n as a fixed value in the question if u don't care about what they gave in the book u can see from the original gate paper of 1999.....but i dont think its available anywhere but if they donot mention that condition we dont need to do  OR for all the possible cases.. i

---

Please can anyone explain why only case of n distinct zeroes being considered? we could also have a case like, 10010001. In that case C(n+1, k) wont be true. Please comment

---

Distinct doesn't mean that the zeroes can’t be adjacent to each other. We just need that no two ones are together.

Answer 1

Answer is (D)

First place $n$ zeroes side by side _ 0 _ 0 _ 0 ... 0 _

$k \ 1's$ can be placed in any of the $(n+1)$ available gaps.

Hence, number of ways  $=^{n+1}C_k$

Comments

@ just_bhavana,

We can do that also...first fix k-1 0's between 1's now we are left with n-(k-1) 0's which can be placed in k+1 places. So it will become C(k+1, n-(k+1))

---

k is no. of 1's

n is no. of 0's

if  k>n is okay, is there a string with no consecutive 1's where k=5 and n=3? or any combination where k>n+1?

---

getting confused one query, when we have n zeroes and K ones => we have (n+k) positions and after we filled n zeroes first in alternating positions we would be left with K ones and K positions right ? then how would we get C(n+1,K)

Answer 2

$\text{i think n$\geq$k-1}$

$\text{then we will have $^{n+1}C_k$}$

$\text{suppose we have 3 zeroes and 2 1's now n+1 gives 4 places after placing}$

$\text{zeroes in this way(_0_0_0_) 0's can be placed in one way now}$

$\text{,from the 4 places we can select 2}$

$\text{places and can put the two 1's it can look this ->10100 or 01010 $\cdot$$\cdot$}$

$\text{note->no need to arrange the zeroes and 1's as they are identical if}$

$\text{you will arrange then it will be like this}$

$\text{$^{3+1}C_2$$\frac{3!}{3!}\frac{2!}{2!}$}$

$\mathbf{alternate approach }$

$\text{by option elimination,take n=2 (0's),k=2(1's) then it gives 1001,0101,1010}$

$\text{a) $^{1}C_2$ (wrong)  b)$^{2}C_2=1$ (wrong)  ,c)$^{2}C_3$ (wrong)   d)correct}$

Answer 3

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

The correct answer is (D) None of the above

Comments

getting confused one query, when we have n zeroes and K ones => we have (n+k) positions and after we filled n zeroes first in alternating positions we would be left with K ones and K positions right ? then how would we get C(n+1,K)

---

answer should D)

---

@ Salazar, suppose when we have $3(n)$  zeroes  and  $2(k)$  one’s  and the zeroes are positioned in a way given below:

_ $0$ _ $0$ _ $0$ _

We have  $4$  i.e.  $(n+1)$  gaps available to fill for  $2$  i.e. $(k)$  ones.

So, we get in total  $\binom{n+1}{k}$  ways to arrange  $k$  ones.

Answer 4

Option D, None of these

As every 0 is identical we can place n 0's in 1 way only. Placing of n 0's will create n+1 slots where we can place 1's as to satisfy the given condition & moreover as every 1 is also identical they'll also be arranged in 1 way only.

So, Total number of binary strings possible is

1*(n+1)Ck *1  = (n+1)Ck