Back to Search
Start Over
Counting scattered palindromes in a finite word
- Publication Year :
- 2021
-
Abstract
- We investigate the scattered palindromic subwords in a finite word. We start by characterizing the words with the least number of scattered palindromic subwords. Then, we give an upper bound for the total number of palindromic subwords in a word of length $n$ in terms of Fibonacci number $F_n$ by proving that at most $F_n$ new scattered palindromic subwords can be created on the concatenation of a letter to a word of length $n-1$. We propose a conjecture on the maximum number of scattered palindromic subwords in a word of length $n$ with $q$ distinct letters. We support the conjecture by showing its validity for words where $q\geq \frac{n}{2}$.
- Subjects :
- Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2108.02729
- Document Type :
- Working Paper