Enumeration of two dimensional palindromes (Q2672656)

A palindrome is a word \(w_1\cdots w_n\in \Sigma^n\) that coincides with its reversal \(w_nw_{n-1}\cdots w_1\). This definition has been extended to (rectangular) bidimensional words. A word \(w_{1,1}\cdots w_{1,n}\cdots w_{m,1}\cdots w_{m,n}\in \Sigma^{m\times n}\) is a palindrome if it coincides with its reversal \(w_{m,n}\cdots w_{m,1}\cdots w_{1,n}\cdots w_{1,1}\). The authors find upper bounds on the number of palindromic (rectangular) subwords of a bidimensional word. Their main results concern two-row words, that is, words in \(\Sigma^{2\times n}\). In particular, they show that a two-row word in \(\{a,b\}^{2\times n}\) has at most \(2n+\lfloor n/2 \rfloor -1\) non-empty distinct palindromic sub-words.