A298477 a(n) is the number of length n strings over a two-letter alphabet that have a minimum palindromic partition size of A090701(n).

2, 2, 4, 12, 24, 12, 28, 4, 16, 60, 4, 24, 140, 2, 32, 230, 1112, 36, 332, 4, 56, 542, 3572, 50, 712, 2, 64, 958, 8696, 50

Offset

1,1

Comments

A "minimum palindromic partition size" of a string is the fewest number of palindromes that the string can be partitioned into.

All terms are even because the letters of the alphabet can be swapped (e.g., "101100" can become "010011".)

Links

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

Example

The a(6) = 12 six-character strings that require A090701(6) = 3 partitions are:
  100101 via (1001)(0)(1),
  100110 via (1001)(1)(0),
  101001 via (1)(0)(1001),
  101100 via (101)(1)(00),
  110010 via (1)(1001)(0),
  110100 via (11)(010)(0),
along with the six strings made from swapping the 0's and 1's.

Prog

(Python)
from functools import cache
from itertools import product
def A090701(n): return n//6 + (n+4)//6 + 1 if n != 11 else 5
@cache
def f(w):
    if len(w) < 2: return len(w)
    return min(1+f(w[i:]) for i in range(1, len(w)+1) if (t:=w[:i]) == t[::-1])
def a(n):
    t = A090701(n) # target value
    return 2*sum(1 for w in product("01", repeat=n-1) if f("0"+"".join(w)) == t)
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Jan 24 2026

Crossrefs

Cf. A090701.

Sequence in context: A019225 A002840 A355566 * A253677 A182894 A286410

Adjacent sequences: A298474 A298475 A298476 * A298478 A298479 A298480

Keyword

nonn,more

Author

Peter Kagey, Jan 19 2018

Extensions

a(21)-a(30) from Michael S. Branicky, Jan 25 2026

Status

approved