The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 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 (69k points)
retagged by | 1.1k 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

2 Answers

+20 votes
Best answer

answer - 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+1Ck

answered by Boss (9.3k points)
selected 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.


all 0s and 1s 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?
0 votes

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

The correct answer is (D) None of the above

answered by Veteran (16.3k points)

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

33,593 questions
40,128 answers
38,389 users