login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A188792 Table with T(n,k) the number of word structures of length n which can be decomposed into k palindromes but not fewer. 2
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, 90, 52, 15, 235, 583, 1005, 909, 826, 364, 203, 52, 402, 1965, 3358, 4914, 4247, 3708, 1624, 877, 52, 1190, 4737, 13250, 19340, 25735, 21511, 18127, 7893, 4140, 203, 2020 (list; table; graph; refs; listen; history; text; internal format)
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

Cf. row sums etc. A000110, 1st column A188164, sum 1st 2 columns A165137.

Sequence in context: A307599 A162663 A005007 * A192395 A014243 A124839

Adjacent sequences:  A188789 A188790 A188791 * A188793 A188794 A188795

KEYWORD

nonn,tabl,nice

AUTHOR

Franklin T. Adams-Watters, Apr 10 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 19 04:06 EDT 2019. Contains 323377 sequences. (Running on oeis4.)