# How many binary sequences are there which have given numbers of substrings 00, 01, 10, 11?

My teacher told me to write a program to solve this problem, but I thought it would be more fun to solve this without brute force of my PC. To explain this problem, for instance, 0000001001101111 has six 00s, three 01s, two 10s, four 11s.
I tried to solve this by using recurrences.Define the number of sequences which have a 00s, b 01s, c 10s, d 11s by $a_n( \left[ \begin{array}{rrr} a & b \\ c & d \\ \end{array} \right]$ ) …and I got stuck. I am looking forward to your answer.

• You don't need a computer program to solve it. Hint: try to get a bijection between the set of all such sequences and the interval $[0,1]$. – Ángel Valencia Nov 30 '15 at 7:38
• Thanks. I will try again till I open my PC next time. Is this a familiar question by chance? – kazuki Nov 30 '15 at 7:55
• You’ll want the result of this question; the answers offer a couple of proofs. – Brian M. Scott Nov 30 '15 at 8:02
• @ÁngelValencia: what bijection should I get? – kazuki Dec 1 '15 at 7:28

Hence if $|b-c|>1$ you would immediately answer $0$.
Now otherwise if $|b-c|\leq1$ you would first arrange $0101010...$ or $1010101...$ and then "insert" $0$ and $1$s into them.
For example, if you want "six 00s, three 01s, two 10s, four 11s" then first you generate $010101$ and then you insert $6$ zeros to the three spaces which has ${6+3-1\choose 3-1}$ choices then you insert $4$ ones into the three spaces which has ${4+3-1\choose 3-1}$ choices.
In the case of $b=c$ however, for example "six 00s, three 01s, three 10s, four 11s", then you would generate both $1010101$ and $0101010$ and then insert into both of them. It is easy to see that after the insertion there won't be any duplication between the two cases as the first case consists of four "bunches of ones" and the second case consists of three "bunches of ones".