Total pairs of binary strings permuted from $n-m$ $1$s and $m$ $0$s so that all initial substrings of $(1)$ have more $0$s than that of $(2)$

70 Views Asked by At

The length of the two original binary strings is $n$ with $m$ zeros and $n-m$ ones.

Let the two initial sub-strings (ie. beginning from index $0$ of the string and ending at any index except the final) be $S(1)$ and $S(2)$.

$S(1)$ must always have more zeros than $S(2)$, whatever the length of the sub-string.

Take for example -

$(1) - 00010111$

$(2) - 10110100$

Initial Substrings

length = $1$

"0" > "1"

length = $2$

"00" > "10"

length = $3$

"000" > "101" ...and so on.

$(1)$ and $(2)$ satisfy this requirement (each $S(1)$ has more zeros than $S(2)$), so $(1),(2)$ is one of the pairs in the count.

Find the total pairs of strings each permuted from n-m ones and m zeros such that the restriction placed is satisfied.

I really don't know how I should proceed. Hints please.