Let's say we are given integer number $k$ and exactly $4$ other numbers $x_{00}, x_{01}, x_{10}, x_{11}$. We want to count binary numbers of length $k$, such that they start with $0$ and they have exactly $x_{00}$ substring of the form $00$, then $x_{01}$ substrings of the form $01$...
Substring is contiguous part of the whole number. For example $001$ is substring of $1001$.
I was thinking about solution with dynamic programming but I think that it will be very slow, so I started thinking about math formula, but I cannot come up with anything useful.
Hint: think of your string as a block of zeros, followed by a block of ones, followed by a block of zeros, etc. A block can be as few as one bit. Based on the $x$'s you are given how many transitions are there? How many blocks of zeros? How many blocks of ones? Can you find a restriction on the $x$'s based on this?
How many total two bit substrings are there? Can you find a restriction on the input data based on this?
If either of your restrictions are not met, you can answer zero without further effort. Otherwise, what is the order of the $01$ substrings and the $10$ substrings? Where can you scatter the remaining $0$s? How many are there? Similarly for the remaining $1$s.