# of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one

53 Views Asked by At

case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one

Answer: 3

case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, zero must be followed by one

Answer: 6

Question: What is the number of bit strings of length n, with n/2-1 zeros and n/2+1 ones, zero must be followed by one (where n is even and n>2)

Answer: ???

Observation from the problem are: they all end with one, and no 2 consecutive zeros can occur

W/e you have in mind either recursion, closed form, permutation/combination or else anything helps.

1

There are 1 best solutions below

4
On BEST ANSWER

Let $k=n/2$. We will have $k-1$ blocks of $01$, and two extra $1$'s, in all $k+1$ "objects".

We choose where the extra $1$'s will go. This can be done in $\binom{k+1}{2}$ ways. We are essentially counting the strings of length $k+1$ made up of $k-1$ B's (block) and two E (extra $1$).