n bit strings are made by filling the digits 0 or 1.the number of strings in which there are exactly k zeroes with no two 0’s consecutive is

dear student, this s an ez ques. note that there would have to be m= n – k 1’s.

so, first of all arrange m 1’s in a row, and mark the spaces b/w the 1’s by crosses. also, mark the space next to the end 1’s by crosses too. so there are total (m – 1) + 2= m+1 crosses. now note that out of these m+1 crossed spaces, the k 0’s can be placed anywhere as they wouldnt be consecutive due to the presence of at least one 1.

hence the number of strings in which there are exactly k zeroes with no two 0’s consecutive= no of ways of placing 1’s * number of ways to select k places out of m+1 * number of ways of placing 0’s

= 1* ^m+1C_k * 1

= ^{n – k+1}C_k