MathDB

Let

a_1,a_2,\ldots,a_n

be a finite sequence of non negative integers, its subsequences are the sequences of the form

a_i,a_{i+1},\ldots,a_j

with

1\le i\le j \le n

. Two subsequences are said to be equal if they have the same length and have the same terms, that is, two subsequences

a_i,a_{i+1},\ldots,a_j

and

a_u,a_{u+1},\ldots a_v

are equal iff

j-i=u-v

and

a_{i+k}=a_{u+k}

forall integers

k

such that

0\le k\le j-1

. Finally, we say that a subsequence

a_i,a_{i+1},\ldots,a_j

is palindromic if

a_{i+k}=a_{j-k}

forall integers

k

such that

0\le k \le j-i

What is the greatest number of different palindromic subsequences that can a palindromic sequence of length

n

contain?

Problem Statement