6,345 views

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

1. $^{n-1}C_k$
2. $^nC_k$
3. $^nC_{k+1}$
4. None of the above

Hello venkat

i didn't get about what you're agreed upon. I don't care what madeeasy/ace are doing with their books but what i want to say is , there is no need to apply any condition.When we use any function , it's common sense that we talk only in the area where it's defined. like when you use $logn$ you don't say 'where n is some positive real number'.
edited
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.

### Subscribe to GO Classes for GATE CSE 2022

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$

by
40 66 126

The condition specified should be k <= n+1.

If  no of 1's is 3 and no. of 0's is 1. There is no way you can arrange them in that format.

I guess it's assumed as they anyway cannot form that combination.

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)

# $\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}$

by
32 159 260

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

## The correct answer is (D) None of the above

by
25 70 138

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

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

by
1 5 10

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

1
8,811 views