A320910 - OEIS

%I #9 Oct 25 2018 02:44:24

%S 2,6,20,50,128,302,708,1612,3624,8048,17704,38604,83660,180118,386096,

%T 823540,1750564

%N a(n)/2^n is the expected length of the longest palindromic subsequence of a length-n binary string.

%C By subsequence we mean "not necessarily contiguous subsequence".

%e For n = 3, the binary strings are 000, 001, 010, 011, and their bitwise complements, with longest palindromic subsequence of length 3,2,3,2 respectively, so a(3) = 2*(3+2+3+2) = 20.

%K nonn,more

%O 1,1

%A _Jeffrey Shallit_, Oct 23 2018