12 Bit String 4 non adjacent 1s I've been asked to find the number possibilities with a 12 bit string, where there are exactly four 1s, where none are adjacent to each other. 
I'm pretty sure that if the adjacent property wasn't necessary, then it would be 12!/(4!*8!), but I'm puzzled on how to solve this.
 A: Think of it in this way: we denote our four 1's by bars and our eight 0's by hash keys #.
We represent a string of 12 bits in this way: if the string is, say, ($0,1,1,0,0,0,1,0,0,1,0,0$), then we write #||###|##|##. So we "count how many zeroes there are between 1's/before the first 1/after the last 1".
Now we are required that between any two bars (our four 1's), there is at least a hash key (a $0$). So we put three hash keys between each two bars: |#|#|#|.
Now we have 5 remaining hash keys, and we can put them wherever we want. In how many way can we put the remaining 5 hash keys into the 5 slots (one slot before the first bar, the three slots where we have already put a hash key, and one final slot after the last bar). The answer is ${5+5-1 \choose 5}=126$. 
See:
http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) for an explanation of the last formula.
A: Write down the eight  $0$'s,  with some space between them, like this:
$$0\qquad 0\qquad0\qquad0\qquad0\qquad0\qquad0\qquad0\qquad$$
There are $9$ "gaps" determined by these $0$'s ($7$ real gaps, plus just before the first $0$, and just after the last one).
We need to choose $4$ of these gaps to put a $1$ into. By definition, there are $\binom{9}{4}$ ways to do this.
Remark: The number $\binom{9}{4}$ denotes a binomial coefficient. You may be accustomed to calling it ${}^9C_4$, or $C^9_4$, or $C(9,4)$, or by some related name. It is equal to $\frac{9!}{4!5!}$, which simplifies to $\frac{(9)(8)(7)(6)}{4!}$, and then to $126$. 
A: Here's another way to find the answer.
Count separately how many valid strings begin with 0 and how many begin with 1. The number that begin with 0 is the number of ways of arranging four "01"s and four "0"s, which is ${8\choose4}=70$. The valid strings beginning with a 1 can be generated by prepending "1" to the valid 11-bit strings that begin with 0 and contain three non-adjacent 1s. These are the arrangements of three "01"s and five "0"s, and there are ${8\choose3}=56$ of them. In all, that's $70+56=126$ strings.
