Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers 2

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.