Equation for inductive relationship determining counts of binary sequences

Question

Given a binary string, the following properties can be determined:

n: the total length of the sequence
p: the total number of `1`s in the sequence
k: a vector of transition counts [{0->0}, {0->1}, {1->0}, {1->1}]
     reading the sequence from left to right

For example, the string 0110, can be determined to have:

n: 4, p: 2, k: [0 1 1 1]

The string can grow by appending either a 0 or a 1 at the end, which will change it's properties:

0110:   01100  ->   n: 5, p: 2, k: [1 1 1 1]
        01101  ->   n: 5, p: 3, k: [0 2 1 1]

So conversely, an inductive relationship determining the counts (F) of all possible sequences of length n can be found, where all the values are whole numbers:

F(p, [k00, k01, k10, k11])
=   F(p,     [k00 - 1, k01, k10, k11]) 
  + F(p - 1, [k00, k01 - 1, k10, k11]) 
  + F(p,     [k00, k01, k10 - 1, k11]) 
  + F(p - 1, [k00, k01, k10, k11 - 1])

The starting conditions are:

F(0, [0, 0, 0, 0]) = 1
F(1, [0, 0, 0, 0]) = 1

And k01 and k02 can only have a maximum difference of 1

F(p, [k00, k, k - 2, k11]) = 0
F(p, [k00, k - 2, k, k11]) = 0

Is there a way to determine an equation that lets the values be plugged in without doing it inductively?

Answer 1

You can think of the string in terms of "runs of ones" and "runs of zeros".

Suppose that there are $p$ ones. If they form a single run, then $k_{11}=p-1$.

$$\underbrace{1111\ldots1111}_p$$

Each time you insert a zero into this string in such a way as to break one run into two runs, $k_{11}$ decreases by $1$. Thus the number of runs of ones, $r_1$, equals $p-k_{11}$. Similarly, $r_0=n-p-k_{00}$.

But it's also true that $$r_1=k_{10}+[\text{string ends with 1}]=k_{01}+[\text{string starts with 1}]$$ (where the brackets mean $``\text{1 if true, else 0"}$) so you can use the other elements of the vector to deduce the first and last bits in the string.

Suppose for example you are given $n=14, p=8, k=(3,3,2,5)$. Then you know that the string of length $14$ starts with $0$, ends with $1$, and contains three runs of ones and three runs of zeros. So the number of possible binary strings with these properties can be found using stars-and-bars: $$\binom{p-1}{r_1-1}\binom{n-p-1}{r_0-1}=\binom{8-1}{3-1}\binom{6-1}{3-1}=\binom72\binom52=210$$ This formula will hold in general; $\tbinom00=\tbinom{-1}{-1}=1$.