Skip to main content
MathOverflow

Return to Question

added 1 characters in body
Source Link
user6976
user6976

Let $W$ be a cyclic word of length $n$ in a 2-letter alphabet $\{0,1\}$. It is clear that it has at most $n^2$ different subwords because(because the number of subwords of length $i$ is at most $n$ for each $i$) and that the actual number of subwords is less than $n^2$ (because the number of subwords of length $1$ is not $n$, but $2$). What is the maximal possible number of subwords as a function of $n$ and what are words where this upper bound is achieved.

Let $W$ be a cyclic word of length $n$ in a 2-letter alphabet $\{0,1\}$. It is clear that it has at most $n^2$ different subwords because the number of subwords of length $i$ is at most $n$ for each $i$) and that the actual number of subwords is less than $n^2$ (because the number of subwords of length $1$ is not $n$, but $2$). What is the maximal possible number of subwords as a function of $n$ and what are words where this upper bound is achieved.

Let $W$ be a cyclic word of length $n$ in a 2-letter alphabet $\{0,1\}$. It is clear that it has at most $n^2$ different subwords (because the number of subwords of length $i$ is at most $n$ for each $i$) and that the actual number of subwords is less than $n^2$ (because the number of subwords of length $1$ is not $n$, but $2$). What is the maximal possible number of subwords as a function of $n$ and what are words where this upper bound is achieved.

Source Link
user6976
user6976

A word with maximal number of subwords

Let $W$ be a cyclic word of length $n$ in a 2-letter alphabet $\{0,1\}$. It is clear that it has at most $n^2$ different subwords because the number of subwords of length $i$ is at most $n$ for each $i$) and that the actual number of subwords is less than $n^2$ (because the number of subwords of length $1$ is not $n$, but $2$). What is the maximal possible number of subwords as a function of $n$ and what are words where this upper bound is achieved.