in Combinatory edited by
6,345 views
27 votes
27 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
in Combinatory edited by
by
2261 2454 2576
6.3k views

5 Comments

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'.
0
0
edited by
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
0
0
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
0
0
Distinct doesn't mean that the zeroes can’t be adjacent to each other. We just need that no two ones are together.
0
0

Subscribe to GO Classes for GATE CSE 2022

5 Answers

58 votes
58 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$

edited by
by
40 66 126

5 Comments

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.
0
0

just_bhavana,

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

0
0
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
0
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
0
8 votes
8 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}$

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

edited by
by
32 159 260
0 votes
0 votes

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

The correct answer is (D) None of the above

by
25 70 138

3 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)
0
0
answer should D)
0
0
@ 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.
0
0
0 votes
0 votes

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
0 votes
0 votes

 

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

edited by
Answer:

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