Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
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.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.