

A165137


a(n) is the number of patterns for ncharacter papaya words in an infinite alphabet.


8



1, 1, 2, 4, 10, 21, 50, 99, 250, 454, 1242, 2223, 6394, 11389, 35002, 62034, 202010, 359483, 1233518, 2203507, 7944110, 14249736, 53811584, 96912709, 382289362, 691110821, 2841057442, 5154280744, 22033974854, 40105797777, 177946445580
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Papaya words are concatenations of two palindromes or palindromes themselves. A165136 is the number of papaya patterns for ndigit numbers. Thus a(n) coincides with A165136 for small n, and is greater than A165136 for larger n. The actual number of ndigit papaya numbers is A165135.
The first 19 terms of this sequence are the same as in A165136. A165137(20) = A165136(20)+10.  Tanya Khovanova, Oct 01 2009, corrected by Franklin T. AdamsWatters, Apr 10 2011


LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..100
Chuan Guo, J. Shallit, A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
Tanya Khovanova, Papaya Words and Numbers


FORMULA

a(n) = R(n)  Sum_{dn,d<n} phi(n/d)*a(d) where R(2*k)=k*(bell(k)+bell(k+1)), R(2*k+1)=(2*k+1)*bell(k+1), bell(k)=A000110(k).  Andrew Howroyd, Mar 29 2016


EXAMPLE

There are two types of twodigit papaya numbers: aa, or ab. Hence a(2) = 2. There are four types of threedigit papaya numbers: aaa, aab, aba, abb. Hence a(3) = 4.


MATHEMATICA

R[k_?EvenQ] := (1/2)*k*(BellB[1 + k/2] + BellB[k/2]);
R[k_?OddQ] := k*BellB[1 + (k  1)/2];
a[0] = 1; a[n_] := a[n] = R[n]  Sum[EulerPhi[n/d]*a[d], {d, Most[Divisors[ n]]}];
Table[a[n], {n, 0, 30}] (* JeanFrançois Alcover, Oct 08 2017, after Andrew Howroyd *)


CROSSREFS

Cf. A165136, A165135, A165610, A165611, A188792, A007055.
Sequence in context: A255711 A204804 A165136 * A065023 A123445 A104431
Adjacent sequences: A165134 A165135 A165136 * A165138 A165139 A165140


KEYWORD

nonn


AUTHOR

Sergei Bernstein and Tanya Khovanova, Sep 04 2009


EXTENSIONS

a(0) and a(7)a(14) from Franklin T. AdamsWatters, Apr 10 2011
a(15)a(30) from Andrew Howroyd, Mar 29 2016


STATUS

approved



