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

Question

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.

Answer 1

The problem with recurrence is that you can't go infinitely long or very short, the length in which the string satisfy your condition is bounded in a narrow range so using the length as the parameter is not an option, and if you would choose to use four parameters then is not generally solvable..

To solve the problem you would first refer to this Discrete Math Bit String proof

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