The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 votes

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
asked in Combinatory by Veteran (52.1k points)
edited by | 2k views
the above question is incomplete there were some conditions i saw in book please edit @Arjun sir

the condition is n>=k-1
hence the answer will be when n=k-1 then we get k-2+2  =k  places and we have k once kCk  ways

when n=k we have k+1 places to place k ones hence k+1Ck so on

ans is kCk+ k+1Ck + k+2Ck +..................... none of these
Hello venkat sai

As i'm able to see , there is no need to add any relation b/w n and k. Question is complete.

Here we just have to apply our common sense. He is asking to arrange such that no two one are adjacent , and if there are many 1's compare to 0's then it can't possible to keep the 1's away from each other hence 0 ways. $\binom{n+1}{k}$ is a general answer which will take care about all cases.

When we say $\binom{n}{r}$ , it's common condition that $r\leq n$. You can't se;ect 4 things out of 3 things.
hello rupendra choudary  i  didnt change the question and apply the condition it was mentioned in ace academy book as gate 1999 ....if we have k 1's then we get k-1 gaps and we should atleast have k-1 0's or more to satisfy the condition that no 2 1's will together and thats common sense ...try to check in either madeeasy or ace academy book the condition is given

PS: n>=k-1

n+1>=k according to n+1Ck u r arranging k numbers in n+1 gaps generated and hence the condition should be satisfied for sure else if n+1<k 2 1's might come together
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'.
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

3 Answers

+36 votes
Best answer

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$

answered by Loyal (8.7k points)
edited by

Shouldn't the complete answer be n+1Ck  multiplied by k! multiplied by (k-1)!.taking into consideration the arrangements of 0 s

Arrangement of n zeroes can be in  Ways as


Keeping n+1 places for ones so that no two ones can be placed together and ther are k ones to be placed.

= n+1Ck

all $0's$ and $1's$ are identical so no need to permutate them
why is it not C(n, k+1) ?

we  place k one's initially


and then place n zero's in the k+1 blanks
@Bhavna it's because if any gap is not filled by 0 as we are giving choices to fill 0's, then two 1's will be consecutive.
@manu I get it, but they should've specified that k > n right ?
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)
+5 votes

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


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

answered by Loyal (5.4k points)
edited by
0 votes

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

The correct answer is (D) None of the above

answered by Loyal (7.5k points) 1 flag:
✌ Edit necessary (Satbir “please provide detailed explanation or ove your answer to 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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,814 questions
54,518 answers
75,287 users