The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 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 (59.4k points)
edited ago by | 1.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

2 Answers

+22 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+1}C_k$

answered by Loyal (9.2k points)
edited ago 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?
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)
0 votes

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

The correct answer is (D) None of the above

answered by Loyal (6.2k points)
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)

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

35,487 questions
42,746 answers
42,138 users