1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I guess problem becomes easy if you look at it as "# of ways put X objects into Y piles w/o order", idk why I didn't think of that, thanks $\endgroup$ Commented Jun 19, 2016 at 3:44
  • $\begingroup$ @SakhJack: You are welcome. There are other ways, such as recurrence. But this one seems reasonably simple, and perhaps natural. $\endgroup$ Commented Jun 19, 2016 at 3:53
  • $\begingroup$ Would you be so kind to give a recurrence approach as another answer, if you have time? just curious $\endgroup$ Commented Jun 19, 2016 at 3:56
  • $\begingroup$ @SakhJack: Maybe. It is less pretty, so I will only do it if I find something neater than what I now have in mind. The recurrence is $f(k+1)=f(k)+k+1$, $f(1)=1$. $\endgroup$ Commented Jun 19, 2016 at 4:06

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.