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

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

Offset

1,1

Comments

By subsequence we mean "not necessarily contiguous subsequence".

Links

Table of n, a(n) for n=1..17.

Example

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.

Crossrefs

Sequence in context: A056820 A204422 A027558 * A066397 A060344 A363600

Adjacent sequences: A320907 A320908 A320909 * A320911 A320912 A320913

Keyword

nonn,more

Author

Jeffrey Shallit, Oct 23 2018

Status

approved