Binary string ($\{0,1{\}}^{<\omega }$)

A binary string is a finite word over the alphabet $\{0,1\}$. There are $2^n$ strings of length $n$. Finite binary strings have an effective bijection with natural numbers, so computable enumerability and immunity apply to sets of strings.

A binary string with $n$ zeroes and $j$ ones is determined by its $j$ one-positions, giving $\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)$ possibilities. Sum for $0\le j\le m$ and apply the hockey-stick identity. Equivalently, distribute at most $m$ ones among the $n+1$ gaps around the zeroes and add a slack count; stars and bars counts $n+2$ nonnegative counts summing to $m$.

A self-delimiting code permits a decoder to identify the end of a code without an external length marker. Encoding a binary word of length $\ell$ by $\ell$ ones, a zero and the word uses $2\ell +1$ bits. This yields an $O(\log n)$ description of a natural number in an incompressibility proof.