Informal version
What is the maximum number of distinct $n$-runs that a $\{0,1\}$-sequence of length $2^n$ can have?
Formal version
If $A, B$ are sets, we denote by $B^A$ the set of all functions $f:A \to B$. For any positive integer $n\in\mathbb{N}$ we let $[n]:=\{0,\ldots,n-1\}$.
"Map of runs": Let $s:[2^n] \to \{0,1\}$ be any binary sequence. To $s$ we associate a map $r_{n,s}: [2^n – n] \to \{0,1\}^{[n]}$ defined by $k \mapsto s_k$ where $s_k: [n] \to \{0,1\}$ is defined by $j \mapsto s(k+j)$.
Question. In terms of $n$, what is the value of $$\max\{|\text{im}(r_{n,s})| : s\in \{0,1\}^{|2^n|}\}$$
?
Best Answer
I understand that $n$-run here refers just to a substring of length $n$ (sometimes called $n$-mer).
The answer to this question is given by any de Bruijn sequence $B(2,n)$, where all $2^n-n+1$ (or $2^n$ if the sequence is viewed as cyclic) $n$-mers are distinct.