2022/04/29 by M, Sivasankar, R, Rama
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2204.13977
If x is a non-empty string then the repetition xx is called a tandem repeat. Similarly, a tandem in a two dimensional array X is a configuration consisting of a same primitive block W that touch each other with one side or corner. In \citeApostolico:2000, Apostolico and Brimkov have proved various bounds for the number of tandems in a two dimensional word of size m × n. Of the two types of tandems considered therein, they also proved that, for one type, the number of occurrences in an m × n Fibonacci array attained the general upper bound, O(m2n \hspace0.1cm log \hspace0.1cm n). In this paper, we derive an expression for the exact number of tandems in a given finite Fibonacci array fm,n. As a required result, we derive the factor complexities of fm,n, m,n ≥ 0 and that of the infinite Fibonacci word f∞, ∞. Generations of f∞, ∞ and fm,n, for any given m,n ≥ 1 using a two-dimensional homomorphism is also achieved.