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

@sk26 nope, It will be true and for a string like 10010001 with 3 ones and 5 zeroes C(5+1,3) = C(6,3) = 20 such strings, here are the 20 strings: 

10101000
10100100
10100010
10100001
10010100
10010010
10010001
10001010
10001001
10000101
01010100
01010010
01010001
01001010
01001001
01000101
00101010
00101001
00100101
00010101

---

no option match

---

https://youtu.be/C1CjtxYEbeM?t=109

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

but k can be more than n+1 broo we cannot conclude anything in this question answer shoule be D anyone plz explain @GO Classes 

---

k has to be less than equal to n+1 otherwise it is not possible to have a permutation in which no two ones are adjaceent. Consider thinking with a small value of n, for example 3, _0_0_0_, here n=3 and if k>4, then there doesnt any permutation in which no two ones are adjacent.

---

exactly

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

.

Answer 4

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 5

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 

Answer 6

 

Since there are n zeroes, so
XOXOXOXOXOXOX
n+1 gaps can be possible, where 1's can be placed so that no two one's are adjacent. So, no. of ways in which k 1's can be placed in n+1 gaps are,
$^{n+1}$$C_k$

Hence Option “D” None of these is the answer