On minimal words with given subword complexity (Q1392298)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On minimal words with given subword complexity |
scientific article |
Statements
On minimal words with given subword complexity (English)
0 references
27 July 1998
0 references
Summary: We prove that the minimal length of a word \(S_n\) having the property that it contains exactly \(F_{m+2}\) distinct subwords of length \(m\) for \(1\leq m\leq n\) is \(F_n+ F_{n+ 2}\). Here \(F_n\) is the \(n\)th Fibonacci number defined by \(F_1=F_2=1\) and \(F_n=F_{n-1}+ F_{n-2}\) for \(n>2\). We also give an algorithm that generates a minimal word \(S_n\) for each \(n \geq 1\).
0 references
minimal length of a word
0 references