Mathematics is a vast and endless field with several areas of
specialization such as algebra, geometry, calculus, and many others. There is
one area of mathematics called **combinatorics**
that has been producing exciting and impactful results since time immemorial. Combinatorics
generally deals with **counting**.
Although this may sound simple, it has many, diverse applications in physics,
biology, and computer science.

Combinatorics is used in pattern recognition and image processing techniques in computer science. In biology, it is used to study nucleotide sequencing in DNA computing. In physics, it is used in crystallography.

In Formal Languages, a word is a sequence of letters or symbols. Words can be finite or infinite. A tandem is a repetitive **subword **that occurs in a word. In computer science engineering, tandem-repeats are used in compression algorithms. In molecular biology and genealogical DNA tests, tandem-repeats are very useful to determine inherited traits of an individual.

In this study conducted by Mr. M. Sivasankar and Dr. R. Rama from the
Department of Mathematics, Indian Institute of Technology Madras, Chennai,
India, **tandem-repeats have been studied
in two-dimensional Fibonacci arrays**.

In computer science, an **array**
is a data structure that consists of a collection of values or variables. For
example, a name, or a sequence of numbers could constitute a one dimensional array.

**Fibonacci words/arrays** are formed by repeated concatenation in the same way
that Fibonacci numbers are formed by repeated addition. Recall that **Fibonacci numbers** are a sequence of numbers
where each number is the sum of the two preceding ones. The initial sequence is
as follows: 0, 1, 1, 2, 3, 5, 8, 13…

Fibonacci words are over any two-letter alphabet (usually over the
binary digits). Two-dimensional arrays are an extension of one-dimensional
arrays. In a one-dimensional array, a tandem-repeat for a non-empty string *x*, is *xx*. Finding a tandem-repeat in a two-dimensional array, which is of
size *m* x *n*, where *m* is the number
of rows, and *n* is the number of
columns, is more complex. A tandem in a two-dimensional array, is a
configuration consisting of a block W that touches with the same block W on the
other side or its corner as shown below.

Figure: Types of tandems that can occur in a two-dimensional array

In this study, both the finite and the infinite two-dimensional
Fibonacci arrays were studied. The exact number of tandems occurring in a
two-dimensional Fibonacci array was counted, both with and without repetition.
Factor complexity of finite two-dimensional Fibonacci arrays was also studied.
It was also proved that **infinite
two-dimensional Fibonacci word is a morphic word**. A **DFAO** (**Deterministic Finite
state Automaton with Output**) generating the two-dimensional Fibonacci words
was also constructed.

Some closely related properties to tandem-repeats are approximate tandem-repeats and approximate periodicity of two-dimensional Fibonacci words. These could be studied for future research.

Prof. Krishna Shankar Narayanan, from the Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai, India, gave her analysis of the work done by the authors with the following comments: “This article reports a very interesting result capturing the exact number of tandems in a given finite Fibonacci array of dimension *m x n*. Prior work in this direction is only known to provide an upper bound for the number of tandems of a certain type, but not the exact number. The authors obtain an expression capturing the exact number of tandems of both types in this paper by going through some non-trivial combinatorics, thereby finding the factor complexities of a given finite Fibonacci array. The generality of the proposed technique also allows one to use the same in computing the factor complexity of an infinite dimensional Fibonacci array as well.”

Article by Akshay Anantharaman

Click here for the original link to the paper