cp's OEIS Frontend

A188792 Table with T(n,k) the number of word structures of length n which can be decomposed into k palindromes but not fewer.

%I A188792 #18 Apr 30 2025 21:04:09
%S A188792 1,1,1,2,2,1,2,8,3,2,5,16,18,8,5,5,45,57,56,25,15,15,84,220,213,203,
%T A188792 90,52,15,235,583,1005,909,826,364,203,52,402,1965,3358,4914,4247,
%U A188792 3708,1624,877,52,1190,4737,13250,19340,25735,21511,18127,7893,4140,203,2020
%N A188792 Table with T(n,k) the number of word structures of length n which can be decomposed into k palindromes but not fewer.
%C A188792 Every singleton string is a palindrome, so decomposition into n strings is always possible.
%C A188792 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).
%H A188792 Franklin T. Adams-Watters, <a href="/A188792/b188792.txt">Rows n = 1..14, flattened</a>
%e A188792 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.
%e A188792 The table starts:
%e A188792   1
%e A188792   1  1
%e A188792   2  2  1
%e A188792   2  8  3  2
%e A188792   5 16 18  8  5
%o A188792 (PARI) numpal(v)={local(w,n);w=vector((n=#v)+1,i,i-1);
%o A188792 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)));
%o A188792 w[n+1]}
%o A188792 nextsetpart(v)={local(w,n);w=vector(n=#v);w[1]=1;for(k=2,n,w[k]=max(w[k-1],v[k]));
%o A188792 while(n>1,if(v[n]<=w[n-1],v[n]++;return(v));v[n]=1;n--);vector(#v+1,i,1)}
%o A188792 al(n)=local(v,r);v=vector(n,i,1);r=vector(n);while(#v==n,r[numpal(v)]++;v=nextsetpart(v));r
%Y A188792 Cf. row sums etc. A000110, 1st column A188164, sum 1st 2 columns A165137.
%K A188792 nonn,tabl,nice
%O A188792 1,4
%A A188792 _Franklin T. Adams-Watters_, Apr 10 2011