13
$\begingroup$

I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length $>1$ that appears more than once in the string. For example, with $n=2$ and alphabet $\{0,1\}$, the string $10011$ would be counted, but $1010$ would not because substring $10$ appears twice, and similarly $000$ would not be counted because substring $00$ appears twice (note that occuring substrings can overlap). The empty string counts as a valid string too. I computed $A(n)$ for $n=1,2,3,4,5$ and got $3,25,1885,3636297,327094648711$. However, when I entered this into OEIS, I got no match (and similarly when I subtracted $1$ and entered $A(n)-1$ for $n=2,3,4$). So I added the sequence A246536 to the OEIS database.

Anyway, I was wondering if anyone can help either come up with a combinatorial formula (either closed form or in terms of somewhat tractable summation etc.), or similarly come up with an asymptotic formula $G(n)$ such that $\lim_{n\to\infty} A(n)/G(n)=1$. The only progress I've been able to make is noting that a circular De Bruijn sequence where every substring of length 2 occurs exactly once can be cut in any of the $n^2$ possible cut points, and then the full string obtained or the string with the last character removed can be counted, and this gives a somewhat good lower bound of $A(n)>G(n)=2n^2B(n,2)$ where $B(n,2)$ is the De Bruijn number for alphabet of size $n$ and substrings of length $2$ (which has an exact known formula). However this does not give an asymptotic lower bound $G(n)$ that satisfies $\lim_{n\to\infty}A(n)/G(n)=1$, because the number of left out shorter strings not counted by $G(n)$ that are counted by $A(n)$ is non-trivial. Any help or pointers to the literature are greatly appreciated.

$\endgroup$
7
  • $\begingroup$ why are you saying "The empty string counts as a valid string too", especially as you have (of course) excluded length 1? Maybe it is easier to "break it up" by looking at A(n,k) for strings with no multiple substrings of length k. $\endgroup$
    – Wolfgang
    Sep 18, 2014 at 18:33
  • $\begingroup$ @Wolfgang Both the empty string and strings of length 1 trivially satisfy the property, since they have no substrings of length $> 1$, so we could exclude the empty string or exclude all those strings of length $\leq 1$. I just chose to include the empty string in the count because it is often considered to be a string, just like the empty set is often considered to be a set. Note I tried removing it when I searched OEIS and I still found no match. $\endgroup$ Sep 18, 2014 at 19:03
  • $\begingroup$ As a comment; there is a dual/related? question, about the length of the shortest string in an alphabet in $n$ letters that contain all permutations as consecutive substrings of the string. Computing these numbers is also quite hard, I remember a recent article on arxiv on this. $\endgroup$ Sep 18, 2014 at 19:17
  • 2
    $\begingroup$ FWIW, I believe $A(n)$ is equal to the number of trails in the complete graph on $n$ vertices. $\endgroup$ Sep 19, 2014 at 7:10
  • 2
    $\begingroup$ @Kevin: I believe you mean a directed complete graph with a loop on each vertex. This seems like the best way to look at it. The number of maximum-length trails is a determinant. I'm not sure about shorter trails. $\endgroup$ Sep 19, 2014 at 13:12

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.