# Counting Binary Sequences

From Richard Stanley's Enumerative Combinatorics,

2(j) How many sequences $(a_1, a_2, \ldots, a_{12})$ are there consisting of four 0's and eight 1's, if no two consecutive terms are both 0's?

I can brute force this, but Stanley provides the (mysterious) reasoning ${8 + 1 \choose 4} = 126$.

Any elegant argument is appreciated.

-

From the answer here: Consecutive birthdays probability

We need to select $\displaystyle d$ numbers from $\displaystyle 1,2, \dots, k$ such that no two are consecutive.

Now if $\displaystyle b_1 \lt b_2 \lt \dots \lt b_d$ were such numbers, then notice that

$\displaystyle 1 \le b_1 \lt b_2 - 1 \lt b_3 - 2 \dots \lt b_d - (d-1) \le k-(d-1)$ gives us a way to select numbers from $\displaystyle 1, 2, \dots, k-(d-1)$ without having to bother about the consecutive issue.

This can be done in $\displaystyle {k-d+1 \choose d}$ ways.

In your case, $k=12, \ d=4$.

-
Beat me to it, and you did it better too! :-) – Asaf Karagila Mar 15 '11 at 22:04
@Asaf: Actually this was already done, so it was just a cut&paste :-) Thanks! – Aryabhata Mar 15 '11 at 22:05
Very nice answer, thank you. – Hans Parshall Mar 15 '11 at 22:10

Let me attempt a "proof without words":

_ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _

(There are nine slots here. Pick four of them to put zeroes in.)

-