Distinct combinations of binary strings with ascending indices

Question

The problem is to derive a formula to count the number of distinct combinations of length $l$ for any given binary string $x \in 2^n (\text{i.e., the length of the string is } n)$, such that the $l$ indices are selected in ascending order, i.e., for an $n$ bit string $x$, indexed by $i_1 i_2 \dots i_n$, the $l$ bits selected for $l$-out-of-$n$ combinations ($l$-combinations hereafter) are selected from $x$ in an ascending order of the indices of $x$. So, if the $k^{th}$ bit of an $l$-combination $y$ is the bit at index $i_m$ in $x$, then the $k+1^{th}$ bit of $y$ must come from some $i_e$ index of $x$, where $e > m$.

Now, we know that for $n$ distinct elements, the solution is simply $\dbinom{n}{l}$, but for the given problem, this formula overcounts the number of distinct permutations. For eg., for the string $101101$ with $l=3$, all of the following $l$ combinations are equivalent $(= 101)$:

• $i_1i_2i_3$

• $i_4i_5i_6$

• $i_1i_2i_4$

• $i_1i_2i_6$

• $i_3i_5i_6$

and so on...

I think that the hamming weight $||x||_1$ of the given binary string $x$ might be useful here but I haven't been able to prove anything useful about the possible solution.

Thanks for your help!

Answer 1

You can generate all strings that have the same pattern of transitions between $0$ and $1$ as your given string does, or any subpattern; equivalently, all strings that have the same pattern of stretches of $0$s and $1$s as your string does, or any subpattern.

If you have at least $l$ transitions, you can generate all $2^l$ strings.

If you have $k\lt l$ transitions, the number of admissible strings can be counted by two sums, one in which you use $j$ transitions starting with the first one and one in which you use $j$ transitions starting with the second one. In each case, the choices where to put the transitions are counted by a binomial coefficient. Thus, the number of admissible strings is

$$ \sum_{j=1}^k\binom{l-1}j+\sum_{j=1}^{k-1}\binom{l-1}{j}=\binom{l-1}k+2\sum_{j=1}^{k-1}\binom{l-1}j\;. $$