**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|}\}$$
?



Maximum number of distinct $n$-runs that binary sequence of length $2^n$ can have
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](https://en.wikipedia.org/wiki/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.


