The subword complexity of a finite \(\omega\) of length \(N\) is a function which associates to each \(n\leq N\) the number of all distinct subwords of \(\omega\) having the length \(n\). We define the maximal complexity \(C\left(\omega \right)\) as the maximum of the subword complexity for \(n\in\{1,2,\ldots,N\}\), and the global maximal complexity \(K\left( N\right)\) as the maximum of \(C\left( \omega \right)\) for all words \(\omega\) of a fixed length \(N\) over a finite alphabet. By \(R\left( N\right)\) we will denote the set of the values \(i\) for which there exists a word of length \(N\) having \(K\left( N\right)\) subwords of length \(i\). \(M\left( N\right)\) represents the number of words of length \(N\) whose maximal complexity is equal to the global maximal complexity.
The values of \(K\left( N\right)\) and \(R)N\) are obtained; methods to compute \(M\left( N\right)\) using the de Bruijn graphs and trees are given. An open problem is to find a formula for \(M\left( N\right)\).
Authors
Mira-Cristiana Anisiu Tiberiu Popoviciu Institute of Numerical Analysis Cluj-Napoca, Romanian Academy
Zoltan Blazsik Bolyai Institute of Mathematics, University of Szeged
Zoltan Kasa Faculty of Mathematics and Informatics, Babes-Bolyai University of Cluj-Napoca
Keywords
complexity of words; de Bruijn graphs and trees.
Paper coordinates
M.-C. Anisiu, Z. Blázsik, Z. Kása, Maximal complexity of finite words, Pure Math. Appl. 13 (1-2) (2002), 39-48
[1] T. van Aardenne-Ehrenfest, N.G. de Bruijn, Circuits and trees in oriented linear graphs, Simon Stevin 28 (1951), 203-217.
[2] J. Bond, A. Ivanyi, Modelling of interconnection networks using de Bruijn graphs, Third Conference of Program Designer, Ed. A. Ivanyi, Budapest, 1987, 75-87.
[3] N.G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch. Proc. 49(1946), 758-764.
[4] M. Heinz, Zur Teilwortkomplexitat Fur Worter und Folgen uber einem endlichen Alphabet, EIK 13 (1977), 27-38.
[5] M.Lothaire Combinatorics on words, Addison-Welsely, Reading, MA, 1983.
[6] A. de Luca, On the combinatorics of finite words, Theor. Comput. Sc. 218 (1999), 13-30.
[7] M.H. Martin, A problem in arrangements, Bull. A.M.S. 40 (1934), 859-864.
2002-Anisiu-MaxFinit
Maximal complexity of finite words
Mira-Cristiana Anisiu* Zoltán Blázsik ^(†)quad{ }^{\dagger} \quad Zoltán Kása ^(‡){ }^{\ddagger}
Abstract
The subword complexity of a finite word ww of length NN is a function which associates to each n <= Nn \leq N the number of all distinct subwords of ww having the length nn. We define the maximal complexity C(w)C(w) as the maximum of the subword complexity for n in{1,2,dots,N}n \in\{1,2, \ldots, N\}, and the global maximal complexity K(N)K(N) as the maximum of C(w)C(w) for all words ww of a fixed length NN over a finite alphabet. By R(N)R(N) we will denote the set of the values ii for which there exits a word of length NN having K(N)K(N) subwords of length i.M(N)i . M(N) represents the number of words of length NN whose maximal complexity is equal to the global maximal complexity.
The values of K(N)K(N) and R(N)R(N) are obtained; methods to compute M(N)M(N) using the de Bruijn graphs and trees are given. An open problem is to find a formula for M(N)M(N).
Keywords: complexity of words, de Bruijn graphs and trees
AMS Classification: 68R15
1 Introduction
A finite word is a finite sequence of letters over a finite alphabet A\mathcal{A}, and can be represented as a concatenation of its letters:
w=w_(1)w_(2)dotsw_(N)quad" with "w_(i)inA" for "1 <= i <= N.w=w_{1} w_{2} \ldots w_{N} \quad \text { with } w_{i} \in \mathcal{A} \text { for } 1 \leq i \leq N .
The number NN is the length of ww and is denoted by |w||w|. A word with no letters (i.e. of length 0 ) is the empty word, denoted by epsi\varepsilon. We denote by A^(+)\mathcal{A}^{+} the set of nonempty words over A\mathcal{A}, by A^(**)=A^(+)uu{epsi}\mathcal{A}^{*}=\mathcal{A}^{+} \cup\{\varepsilon\} the set of words over A\mathcal{A} and by A^(n)\mathcal{A}^{n} the set of words of length nn over A\mathcal{A}.
A word uu is a factor (or subword) of ww if there exist words x,y inA^(**)x, y \in \mathcal{A}^{*} such that w=xuyw=x u y. If x!=epsix \neq \varepsilon and y!=epsiy \neq \varepsilon then uu is a proper factor (proper subword) of ww. If x=epsi(y=epsi)x=\varepsilon(y=\varepsilon) then uu is a prefix (suffix) of ww. Let us denote by F(w)F(w) the set of all nonempty factors of ww, and by F_(n)(w)F_{n}(w) the set of all factors of ww of length nn (hence F_(n)(w)=F(w)nnA^(n)F_{n}(w)=F(w) \cap \mathcal{A}^{n} ).
The subword complexity of ww counts the number of all distinct factors of a given length occurring in ww and is defined as
f_(w)(n)=Card(F_(n)(w))quad" for "1 <= n <= |w|.f_{w}(n)=\operatorname{Card}\left(F_{n}(w)\right) \quad \text { for } 1 \leq n \leq|w| .
Clearly f_(w)(1) <= Card(A)f_{w}(1) \leq \operatorname{Card}(\mathcal{A}) and we can consider f_(w)(n)=0f_{w}(n)=0 for n > |w|n>|w|. The subword complexity has been extensively studied in [4], [5] and [6].
The maximal value of the subword complexity f_(w)(n)f_{w}(n) for 1 <= n <= |w|1 \leq n \leq|w| is called the maximal complexity of ww and is denoted by C(w)C(w) :
C(w)=max{f_(w)(n)∣n >= 1}C(w)=\max \left\{f_{w}(n) \mid n \geq 1\right\}
The global maximal complexity in A^(N)\mathcal{A}^{N} is equal to
K(N)=max{C(w)∣w inA^(N)}K(N)=\max \left\{C(w) \mid w \in \mathcal{A}^{N}\right\}
We shall denote by R(N)R(N) the set of values ii for which there exists a word w inA^(N)w \in \mathcal{A}^{N} such that f_(w)(i)=K(N)f_{w}(i)=K(N) :
R(N)={i in{1,2,dots,N}∣EE w inA^(N):f_(w)(i)=K(N)}R(N)=\left\{i \in\{1,2, \ldots, N\} \mid \exists w \in \mathcal{A}^{N}: f_{w}(i)=K(N)\right\}
The number of words in A^(N)\mathcal{A}^{N} with the maximal complexity equal to the global maximal complexity will be denoted by M(N)M(N) :
Remark 1. If Card(A)=q\operatorname{Card}(\mathcal{A})=q, for q=1q=1 the only word of length NN is w_(0)=ubrace(0dots0ubrace)_(N)w_{0}= \underbrace{0 \ldots 0}_{N} for which f_(w_(0))(i)=1,i in{1,2,dots,N}f_{w_{0}}(i)=1, i \in\{1,2, \ldots, N\}, hence C(w)=1=K(N)C(w)=1=K(N), R(N)={1,2,dots,N}R(N)=\{1,2, \ldots, N\} and M(N)=1M(N)=1. For q >= 2q \geq 2, but N <= qN \leq q, for each word w_(1)w_{1} which contains NN distinct elements of A\mathcal{A} we have C(w_(1))=f_(w_(1))(1)=N=K(N)C\left(w_{1}\right)=f_{w_{1}}(1)=N=K(N), R(N)={1}R(N)=\{1\} and M(N)=P_(q)^(N)M(N)=P_{q}^{N} (permutations of NN elements taken from qq ).
Some values for K(N),R(N)K(N), R(N) and M(N)M(N) in the case of an alphabet of 2 letters are given in Table 1. In the case N=3N=3 the following six words have maximal complexity: 001,010,011,100,101,110001,010,011,100,101,110. For each of them f_(w)(1)=2,f_(w)(2)=2,f_(w)(3)=1f_{w}(1)=2, f_{w}(2)=2, f_{w}(3)=1, so K(3)=2,R(3)={1,2}K(3)=2, R(3)=\{1,2\} and M(3)=6M(3)=6.
2 Global maximal subword complexity of finite words
In this section we shall compute the values of the global maximal complexity K(N)K(N), as well as those of R(N)R(N), proving that they are in agreement with the values in Table 1. Some special cases being solved in Remark 1, in what follows we shall consider alphabets with Card(A)=q >= 2\operatorname{Card}(\mathcal{A})=q \geq 2 and words of length N > qN>q.
We shall use the following result.
Lemma 1. [7] For each k inN^(**)k \in N^{*}, the shortest word containing all the q^(k)q^{k} words of length kk has q^(k)+k-1q^{k}+k-1 letters (hence in this word each of the q^(k)q^{k} words of length kk appears only once).
An algorithm for obtaining such a word for A={e_(1),e_(2),dots,e_(q)}\mathcal{A}=\left\{e_{1}, e_{2}, \ldots, e_{q}\right\} is the following [7]: ii. Each of the first k-1k-1 symbols is equal to e_(1)e_{1}. iii i. If the sequence a_(1)a_(2)dotsa_(k)dotsa_(m-k+1)dotsa_(m-1)a_{1} a_{2} \ldots a_{k} \ldots a_{m-k+1} \ldots a_{m-1} (with a_(1)=dots=a_(k-1)=e_(1),m >= ka_{1}=\ldots=a_{k-1}= e_{1}, m \geq k and the aa 's representing the ee 's in a certain order) has been obtained, the symbol a_(m)a_{m} to be added is the e_(i)e_{i} with the greatest subscript possible such that a_(m-k+1)dotsa_(m-1)a_(m)a_{m-k+1} \ldots a_{m-1} a_{m} does not duplicate a previously occurring section of kk symbols in the above sequence. iiii i i. Rule iii i is first applied for m=km=k (in which case a_(m)=a_(k)=e_(q)a_{m}=a_{k}=e_{q} ) and then applied repeatedly until a further application is impossible.
Proposition 1. If Card(A)=q\operatorname{Card}(\mathcal{A})=q and q^(k)+k <= N <= q^(k+1)+kq^{k}+k \leq N \leq q^{k+1}+k then K(N)=N-kK(N)=N-k.
Proof. Let us consider at first the case N=q^(k+1)+k,k >= 1N=q^{k+1}+k, k \geq 1.
From Lemma 1 we obtain the existence of a word WW of length q^(k+1)+kq^{k+1}+k which contains all the q^(k+1)q^{k+1} words of length k+1k+1, hence f_(W)(k+1)=q^(k+1)f_{W}(k+1)=q^{k+1}. It is obvious that f_(W)(l)=q^(l) < f_(W)(k+1)f_{W}(l)=q^{l}<f_{W}(k+1) for l in{1,2,dots,k}l \in\{1,2, \ldots, k\} and f_(W)(k+1+j)=q^(k+1)-j < f_(W)(k+1)f_{W}(k+1+j)=q^{k+1}-j< f_{W}(k+1) for j in{1,2,dotsq^(k+1)-1}j \in\left\{1,2, \ldots q^{k+1}-1\right\}. Any other word of length q^(k+1)+kq^{k+1}+k will have the maximal complexity less than or equal to C(W)=f_(W)(k+1)C(W)=f_{W}(k+1), hence we have K(N)=q^(k+1)=N-kK(N)=q^{k+1}=N-k.
For k >= 1k \geq 1 we consider now the values of NN of the form N=q^(k+1)+k-rN=q^{k+1}+k-r with r in{1,2,dots,q^(k+1)-q^(k)}r \in\left\{1,2, \ldots, q^{k+1}-q^{k}\right\}, hence q^(k)+k <= N < q^(k+1)+kq^{k}+k \leq N<q^{k+1}+k. If from the word WW of length q^(k+1)+kq^{k+1}+k considered above we delete the last rr letters, we obtain a word W_(N)W_{N} of length N=q^(k+1)+k-rN=q^{k+1}+k-r with r in{1,2,dots,q^(k+1)-q^(k)}r \in\left\{1,2, \ldots, q^{k+1}-q^{k}\right\}. This word will have f_(W_(N))(k+1)=q^(k+1)-rf_{W_{N}}(k+1)=q^{k+1}-r and this value will be its maximal complexity. Indeed, it is obvious that f_(W_(N))(k+1+j)=f_(W_(N))(k+1)-j < f_(W_(N))(k+1)f_{W_{N}}(k+1+j)=f_{W_{N}}(k+1)-j<f_{W_{N}}(k+1) for j in{1,2,dots,N-k-1}j \in\{1,2, \ldots, N-k-1\}; for l in{1,2,dots,k}l \in\{1,2, \ldots, k\} it follows that f_(W_(N))(l) <= q^(l) <= q^(k) <= q^(k+1)-r=f_(W_(N))(k+1)f_{W_{N}}(l) \leq q^{l} \leq q^{k} \leq q^{k+1}-r=f_{W_{N}}(k+1), hence C(W_(N))=f_(W_(N))(k+1)=q^(k+1)-rC\left(W_{N}\right)=f_{W_{N}}(k+1)=q^{k+1}-r. Because it is not possible for a word of length N=q^(k+1)+k-rN=q^{k+1}+k-r, with r in{1,2,dots,q^(k+1)-q^(k)}r \in\left\{1,2, \ldots, q^{k+1}-q^{k}\right\} to have the maximal complexity greater than q^(k+1)-rq^{k+1}-r, it follows that K(N)=q^(k+1)-r=N-kK(N)= q^{k+1}-r=N-k.
Proposition 2. If Card(A)=q\operatorname{Card}(\mathcal{A})=q and q^(k)+k < N < q^(k+1)+k+1q^{k}+k<N<q^{k+1}+k+1 then R(N)={k+1}R(N)= \{k+1\}; if N=q^(k)+kN=q^{k}+k then R(N)={k,k+1}R(N)=\{k, k+1\}.
Proof. In the first part of the proof of Proposition 1, we proved for N=q^(k+1)+k,k >= 1N= q^{k+1}+k, k \geq 1, the existence of a word WW of length NN for which K(N)=f_(W)(k+1)=N-kK(N)= f_{W}(k+1)=N-k. This means that k+1in R(N)k+1 \in R(N). For the word WW, as well as for any other word ww of length NN, we have f_(w)(l) < f_(W)(k+1),l!=k+1f_{w}(l)<f_{W}(k+1), l \neq k+1, because of the special construction of WW, which contains all the words of length k+1k+1 in the most compact way. It follows that R(N)={k+1}R(N)=\{k+1\}.
As in the second part of the proof of Proposition 1, we consider N=q^(k+1)+k-rN= q^{k+1}+k-r with r in{1,2,dotsq^(k+1)-q^(k)}r \in\left\{1,2, \ldots q^{k+1}-q^{k}\right\} and the word W_(N)W_{N} for which K(N)=f_(W_(N))(k+1)=q^(k+1)-rK(N)= f_{W_{N}}(k+1)=q^{k+1}-r. We have again k+1in R(N)k+1 \in R(N). For l > k+1l>k+1, it is obvious that the complexity function of W_(N)W_{N}, or of any other word of length NN, is strictly less than f_(W_(N))(k+1)f_{W_{N}}(k+1). We examine now the possibility of finding a word WW with f_(W)(k+1)=N-kf_{W}(k+1)=N-k for which f_(W)(l)=N-kf_{W}(l)=N-k for l <= kl \leq k. We have f_(W)(l) <= q^(l) <= q^(k) <= q^(k+1)-rf_{W}(l) \leq q^{l} \leq q^{k} \leq q^{k+1}-r, hence the equality f_(W)(l)=N-k=q^(k+1)-rf_{W}(l)=N-k=q^{k+1}-r holds only for l=kl=k and r=q^(k+1)-q^(k)r=q^{k+1}-q^{k}, that is for N=q^(k)+kN=q^{k}+k. We show that for N=q^(k)+kN=q^{k}+k we have indeed R(N)={k,k+1}R(N)=\{k, k+1\}. If we start with Martin's word of length q^(k)+k-1q^{k}+k-1 (or with another de Bruijn word) and add to this any letter from A\mathcal{A}, we obtain obviously a word VV of length N=q^(k)+kN=q^{k}+k, which contains all the q^(k)q^{k} words of length kk and q^(k)=N-kq^{k}=N-k words of length k+1k+1, hence f_(V)(k)=f_(V)(k+1)=K(N)f_{V}(k)=f_{V}(k+1)=K(N).
Remark 2. Having in mind the algorithm given by Martin [7] (or other more efficient algorithms), words ww with maximal complexity C(w)=K(N)C(w)=K(N) can be easily constructed for each NN and for both situations in Proposition 2.
3 De Bruijn graphs and trees
In the previous section the global maximal complexity K(N)K(N) for words of length NN was obtained, as well as the set of points R(N)R(N) where K(N)K(N) is equal to the maximal value of the subword complexity of certain words of length NN. To this aim we used a special word constructed by Martin [7], which is one of the de Bruijn words. A de Bruijn word for given qq and kk is a word over an alphabet with qq letters, containing all kk-length words exactly once. The length of such a word is q^(k)+k-1q^{k}+k-1.
In order to tackle the problem of finding the number of the words for which the global maximal complexity is attained, we shall use the de Bruijn graphs and trees.
For a qq-letter alphabet A\mathcal{A} the de Bruijn graph is defined as:
B(q,k)=(V(q,k),E(q,k))B(q, k)=(V(q, k), E(q, k))
with V(q,k)=A^(k)V(q, k)=\mathcal{A}^{k} as the set of vertices, and E(q,k)=A^(k+1)E(q, k)=\mathcal{A}^{k+1} as the set of directed arcs. There is an arc from x_(1)x_(2)dotsx_(k)x_{1} x_{2} \ldots x_{k} to y_(1)y_(2)dotsy_(k)y_{1} y_{2} \ldots y_{k} if x_(2)x_(3)dotsx_(k)=y_(1)y_(2)dotsy_(k-1)x_{2} x_{3} \ldots x_{k}= y_{1} y_{2} \ldots y_{k-1}, and this arc is denoted by x_(1)x_(2)dotsx_(k)y_(k)x_{1} x_{2} \ldots x_{k} y_{k}. See Fig. 1 and 2 for B(2,2)B(2,2) and B(2,3)B(2,3). The de Bruijn graphs B(q,k)B(q, k) are nonplanar for k >= 4k \geq 4, q >= 2q \geq 2.
In the de Bruijn graph B(q,k)B(q, k) a path (i. e. a walk with distinct vertices)
corresponds to an rr-length word a_(1)a_(2)dotsa_(k)a_(k+1)dotsa_(r)a_{1} a_{2} \ldots a_{k} a_{k+1} \ldots a_{r}, which is obtained by adding, in turn, to the vertex a_(1)a_(2)dotsa_(k)a_{1} a_{2} \ldots a_{k} the last letter of the following vertices in the path. For example in B(2,3)B(2,3) the path 001,010,101001,010,101 corresponds to the word 00101. Every maximal length path in the graph B(q,k)B(q, k) (which is a Hamiltonian one) corresponds to a de Bruijn word.
Fig. 1: The de Bruijn graph B(2,2)B(2,2).
In the directed graph B(q,k)B(q, k) there always exists an Eulerian circuit because it is connected and all its vertices have the same indegree and outdegree qq. An Eulerian circuit in B(q,k)B(q, k) is a Hamiltonian path in B(q,k+1)B(q, k+1) (which always can be continued in a Hamiltonian cycle). For example in B(2,2)B(2,2) the following walk: 000,001,010,101,011,111,110,100000,001,010,101,011,111,110,100 represents an Eulerian circuit, which in B(2,3)B(2,3) is a Hamiltonian path.
In order to study the number of words in A^(k)\mathcal{A}^{k} which have the maximal complexity equal to the global maximal complexity K(N)K(N) we shall introduce the so-called de Bruijn trees. A de Bruijn tree T(q,w)T(q, w) with the root w inA^(k)w \in \mathcal{A}^{k} is a qq-ary tree defined recursively as follows: ii. The kk-length word ww over the alphabet A={e_(1),e_(2),dots.e_(q)}\mathcal{A}=\left\{e_{1}, e_{2}, \ldots . e_{q}\right\} is the root of T(q,w)T(q, w).
Fig. 2: The de Bruijn graph B(2,3)B(2,3).
iii i. If at any step of the recursive construction of the tree, x_(1)x_(2)dotsx_(k)x_{1} x_{2} \ldots x_{k} is a (temporary) leaf (a vertex with outdegree equal to 0 ), then each word among x_(2)x_(3)dotsx_(k)e_(1),x_(2)x_(3)dotsx_(k)e_(2),dots,x_(2)x_(3)dotsx_(k)e_(q)x_{2} x_{3} \ldots x_{k} e_{1}, x_{2} x_{3} \ldots x_{k} e_{2}, \ldots, x_{2} x_{3} \ldots x_{k} e_{q} which is not in the path from the root to x_(1)x_(2)dotsx_(k)x_{1} x_{2} \ldots x_{k} will be a descendant of x_(1)x_(2)dotsx_(k)x_{1} x_{2} \ldots x_{k}. iiii i i. The rule iii i is applied as many times as it is possible.
A path is maximal if we cannot add an arc to its beginning or to its end without destroying the path property. If a maximal path is of maximal length then it is a Hamiltonian one. In any de Bruijn tree each branch is a maximal path in the de Bruijn graph B(q,k)B(q, k) which begins with the root, and all maximal paths beginning with the root occur. For the de Bruijn trees T(2,000)T(2,000), T(2,001),T(2,010)T(2,001), T(2,010) and T(2,100)T(2,100) see Fig. 3-6. The word obtained by Martin's algorithm corresponds to the branch of maximal length in the right side of the de Bruijn tree T(2,001)T(2,001).
4 Methods to compute M(N)M(N)
The number M(N)M(N) of the words of length NN for which the maximal complexity is equal to the global maximal complexity K(N)K(N) can be expressed both in terms of certain paths in a de Bruijn graph and of some vertices in the de Bruijn trees.
Proposition 3. If Card(A)=q\operatorname{Card}(\mathcal{A})=q and q^(k)+k <= N <= q^(k+1)+kq^{k}+k \leq N \leq q^{k+1}+k then M(N)M(N) is equal to the number of different paths of length N-k-1N-k-1 in the de Bruijn graph B(q,k+1)B(q, k+1).
Proof. From Propositions 1 and 2 it follows that the number M(N)M(N) of the words of length NN with global maximal complexity is given by the number of words w inA^(N)w \in \mathcal{A}^{N} with f_(w)(k+1)=N-kf_{w}(k+1)=N-k. It means that these words contain N-kN-k subwords of length k+1k+1, all of them distinct. To enumerate all of them we start successively with each word of k+1k+1 letters (hence with each vertex in B(q,k+1)B(q, k+1) ) and we add at each step, in turn, one of the symbols from A\mathcal{A} which does not duplicate a word of length k+1k+1 which has already appeared.
Fig. 3: De Bruijn tree T(2,000)T(2,000).
Fig. 4: De Bruijn tree T(2,001)T(2,001).
Fig. 5: De Bruijn tree T(2,100)T(2,100).
Fig. 6: De Bruijn tree T(2,010)T(2,010).
Of course, not all of the trials will finish in a word of length NN, but those which do this, are precisely paths in B(q,k+1)B(q, k+1) starting with each vertex in turn and having the length N-k-1N-k-1. Hence to each word of length NN with f_(w)(k+1)=N-kf_{w}(k+1)=N-k we can associate a path and only one of length N-k-1N-k-1 starting from the vertex given by the first k+1k+1 letters of the initial word; conversely, any path of length N-k-1N-k-1 will provide a word ww of length NN which contains N-kN-k distinct subwords of length k+1k+1.
Remark 3. The number of words of length NN having global maximal complexity can be also expressed by means of certain vertices in the de Bruijn trees. M(N)M(N) is equal to the number of vertices at the level N-k-1N-k-1 in the set {T(q,w)∣w inA^(k+1)}\left\{T(q, w) \mid w \in \mathcal{A}^{k+1}\right\} of the de Bruijn trees. (The level of the root is considered to be 0 , its descendants are on level 1 etc.)
The other four trees corresponding to the de Bruijn graph B(2,3)B(2,3) are mirror images of those in Fig. 3-6; we obtain, for example, M(6)M(6) by doubling the number of vertices at level 3 in Fig. 3-6, i. e. M(6)=2*18=36M(6)=2 \cdot 18=36. Similarly M(7)=2*21=42M(7)=2 \cdot 21=42 is obtained by doubling the number of vertices at level 4, and so on up to M(10)=2*8=16M(10)=2 \cdot 8=16 (using the vertices at level 7). These results are in accordance with those given in Table 1 obtained by counting all possible words with maximal complexity.
A formula for the number M(N)M(N) of the words whose maximal complexity is equal to the global maximal complexity K(N)K(N) can be given for the special case of de Bruijn words.
Proposition 4. If N=2^(k)+k-1N=2^{k}+k-1 then M(N)=2^(2^(k-1))M(N)=2^{2^{k-1}}.
Proof. The number of distinct Hamiltonian cycles in the de Bruijn graph B(2,k)B(2, k) is equal to 2^(2^(k-1)-k)2^{2^{k-1}-k} [2]. With each vertex of a Hamiltonian cycle a de Bruijn word (containing all the factors of length kk ) begins, which has maximal complexity, so M(N)=2^(k)*2^(2^(k-1)-k)M(N)=2^{k} \cdot 2^{2^{k-1}-k}, which proves the proposition. (In [3] the number of circular de Bruijn words is found, which corresponds to the number of Hamiltonian cycles in de Bruijn graphs).
A generalization for q >= 2q \geq 2 can be proved in a similar way using the results in [1].
Proposition 5. If N=q^(k)+k-1N=q^{k}+k-1 then M(N)=(q!)^(q^(k-1))M(N)=(q!)^{q^{k-1}}.
In Proposition 1, respectively Proposition 2, we have determined for each natural number NN the value of the global maximal complexity K(N)K(N), respectively the set of values ii for which there exists a word of length NN with K(N)K(N) subwords of length ii. To obtain a general formula for M(N)M(N) for each natural number NN is still an open problem.
References
[1] T. van Aardenne-Ehrenfest, N. G. de Bruijn, Circuits and trees in oriented linear graphs, Simon Stevin 28 (1951), 203-217.
[2] J. Bond, A. Iványi, Modelling of interconnection networks using de Bruijn graphs, Third Conference of Program Designer, Ed. A. Iványi, Budapest, 1987, 75-87.
[3] N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch. Proc. 49 (1946), 758-764.
[4] M. Heinz, Zur Teilwortkomplexität für Wörter und Folgen über einem endlichen Alphabet, EIK 13 (1977), 27-38.
[5] M. Lothaire, Combinatorics on words, Addison-Wesley, Reading, MA, 1983.
[6] A. de Luca, On the combinatorics of finite words, Theor. Comput. Sci. 218 (1999), 13-39.
[7] M. H. Martin, A problem in arrangements, Bull. A. M. S. 40 (1934), 859864.
*Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, Cluj-Napoca, E-mail: mira@math.ubbcluj.ro Partially supported by grant CNCSIS 125/64-2001/2002 ^(†){ }^{\dagger} Bolyai Institute of Mathematics, University of Szeged, E-mail: blazsik@sol.cc.u-szeged.hu ^(‡){ }^{\ddagger} Faculty of Mathematics and Informatics, Babes-Bolyai University of Cluj-Napoca, Email: kasa@cs.ubbcluj.roPartially supported by grant CNCSIS 125/64-2001/2002
