OFFSET
1,4
COMMENTS
Every singleton string is a palindrome, so decomposition into n strings is always possible.
T(n,n) = B(n-2), where B = A000110 is the Bell numbers. A string has no nontrivial decomposition into palindromes iff each symbol is different from the two preceding symbols. Processing from right to left, decrease each symbol by the number of smaller symbols of the two preceding it, and dropping the first two symbols; this yields an arbitrary string of length n-2. E.g., [1,2,3,1,4] => [1,1,2], [1,2,3,4,2] => [1,2,2]. Similarly, T(n,n-1) counts strings contributing to T(n-1,n-1) with one symbol repeated, so T(n,n-1) = B(n-3)*(n-1).
LINKS
Franklin T. Adams-Watters, Rows n = 1..14, flattened
EXAMPLE
T(4,3) = 3; the 3 strings are 1,1,2,3; 1,2,2,3; and 1,2,3,3. Greedy parsing of 1,1,2,1 gives 1,1|2|1 into 3 parts, but 1|1,2,1 is better.
The table starts:
1
1 1
2 2 1
2 8 3 2
5 16 18 8 5
PROG
(PARI) numpal(v)={local(w, n); w=vector((n=#v)+1, i, i-1);
for(t=2, 2*n, forstep(i=t\2, max(1, t-n), -1, if(v[i]!=v[j=t-i], break); w[j+1]=min(w[j+1], w[i]+1)));
w[n+1]}
nextsetpart(v)={local(w, n); w=vector(n=#v); w[1]=1; for(k=2, n, w[k]=max(w[k-1], v[k]));
while(n>1, if(v[n]<=w[n-1], v[n]++; return(v)); v[n]=1; n--); vector(#v+1, i, 1)}
al(n)=local(v, r); v=vector(n, i, 1); r=vector(n); while(#v==n, r[numpal(v)]++; v=nextsetpart
(v)); r
CROSSREFS
KEYWORD
AUTHOR
Franklin T. Adams-Watters, Apr 10 2011
STATUS
approved