A188164 -id:A188164 - cp's OEIS frontend

A164904 a(n) is the number of palindromic structures using a maximum of ten different symbols.

1, 1, 1, 2, 2, 5, 5, 15, 15, 52, 52, 203, 203, 877, 877, 4140, 4140, 21147, 21147, 115975, 115975, 678569, 678569, 4213530, 4213530, 27641927, 27641927, 190829797, 190829797, 1381367941, 1381367941, 10448276360, 10448276360, 82285618467

Offset: 0

Tanya Khovanova, Aug 30 2009

a(n) is the number of palindromic word structures of length n using 10-ary alphabet.

a(n) is the same as taking every element twice from A164864.

			Four-digit palindromes have two different digits structures: aaaa and abba. Hence a(4)=2.

Index entries for linear recurrences with constant coefficients, signature (1, 45, -45, -861, 861, 9135, -9135, -58674, 58674, 233100, -233100, -557864, 557864, 732960, -732960, -403200, 403200).

Cf. A056470, A056471, A164864, A188164.

G.f.: (148329*x^17 -403200*x^16 -210253*x^15 +732960*x^14 +122692*x^13 -557864*x^12 -38365*x^11 +233100*x^10 +6965*x^9 -58674*x^8 -736*x^7 +9135*x^6 +42*x^5 -861*x^4 -x^3 +45*x^2 -1) / ((x -1)*(2*x -1)*(2*x +1)*(2*x^2 -1)*(3*x^2 -1)*(5*x^2 -1)*(6*x^2 -1)*(7*x^2 -1)*(8*x^2 -1)*(10*x^2 -1)). [Colin Barker, Dec 05 2012]

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

Original entry on oeis.org

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

Offset: 1

Franklin T. Adams-Watters, Apr 10 2011

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).

			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

Franklin T. Adams-Watters, Rows n = 1..14, flattened

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

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

A327612 Number of length n reversible string structures that are not palindromic using any number of colors.

Original entry on oeis.org

0, 1, 2, 9, 27, 112, 453, 2137, 10691, 58435, 340187, 2110016, 13829358, 95474679, 691538954, 5240280999, 41432965441, 341040295916, 2916376121375, 25862097370783, 237434958512487, 2253358056604465, 22076003464423853, 222979436686398848, 2319295172150784296

Offset: 1

Andrew Howroyd, Sep 18 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row sums of A309748(n > 1).

Cf. A103293, A188164, A304972.

\\ Ach is A304972 as square matrix.
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
seq(n)={my(A=Ach(n)); vector(n, i, sum(k=1, n, (A[i,k] + stirling(i, k, 2))/2 - stirling((i+1)\2, k, 2)))}

a(n) = A103293(n + 1) - A188164(n).

cp's OEIS Frontend

A164904 a(n) is the number of palindromic structures using a maximum of ten different symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A327612 Number of length n reversible string structures that are not palindromic using any number of colors.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula