2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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\;. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.