1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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]$. $\endgroup$ – Ángel Valencia Nov 30 '15 at 7:38
  • $\begingroup$ Thanks. I will try again till I open my PC next time. Is this a familiar question by chance? $\endgroup$ – kazuki Nov 30 '15 at 7:55
  • $\begingroup$ You’ll want the result of this question; the answers offer a couple of proofs. $\endgroup$ – Brian M. Scott Nov 30 '15 at 8:02
  • $\begingroup$ @ÁngelValencia: what bijection should I get? $\endgroup$ – kazuki Dec 1 '15 at 7:28
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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