Number of binary numbers given constraints on consecutive elements I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but couldn't find anything much useful. Any help will be appreicatted in solving this.

A binary string consists of ones and zeros. Ram tells you number of occurences of 00, 01, 10, and 11 respectively in the string. Come up with an algorithm assuming those values to be variables to find the number of such possible strings. Note that if the number of occurences of 11,10,00, and 01 are 1, 1, 2, 1 respectively, you can come up with 5 such binary strings that satisfy it.

I did come up with a recursive formulation for this, that is f(p, q, r, s) where those are the variables respectively. From a theoretical CS perspective, it would take $O(2*p*q*r*s)$ time to compute. Our professor has specifically told it can be done better, just I dont know how better.

If we draw a directed multigraph with two nodes, 0 and 1, and draw $p$ edges from 1 to 1, $q$ edges from 1 to 0, etc.
                   q
          ___   ------>  ___
     --\ /   \ /        /   \/--
  p |   |  1  |        |  0  |  | r
     --> \___/ <------/ \___/<--
                  s

then the number of such strings is the number of different paths that visit every edge in the graph. (Actually, it's twice that number, since you can start at $0$ or at $1$).
I'm not sure if this can be converted into a more efficient algorithm than already given, however.
