A165610 The number of patterns of non-papaya words.

0, 0, 1, 5, 31, 153, 778, 3890, 20693, 114733, 676347, 4207203, 27633048, 190864320, 1382896511, 10479940137, 82864510321, 682075572641, 5832740001550, 51724150291262, 474869801907015, 4506715684635739, 44152005758171637, 445958868912515927, 4638590331538888532

Offset

1,4

Comments

Papaya words are defined as palindromes or concatenations of two palindromes.

Links

Table of n, a(n) for n=1..25.

Tanya Khovanova, Papaya Words and Numbers

Formula

a(n) = A000110(n) - A165137(n).

Example

The only three-character non-papaya pattern is abc - words with all distinct letters. Four-character non-papaya patterns are: aabc, abbc, abcc, abca, abcd.

Mathematica

R[k_?EvenQ] := (1/2)*k*(BellB[1 + k/2] + BellB[k/2]);
R[k_?OddQ] := k*BellB[1 + (k - 1)/2];
b[0] = 1; b[n_] := b[n] = R[n] - Sum[EulerPhi[n/d]*b[d], {d, Most[ Divisors[n]]}];
a[n_] := BellB[n] - b[n];
Array[a, 25] (* Jean-François Alcover, Jul 02 2018, after Andrew Howroyd *)

Crossrefs

Cf. A165137, A165135, A165136, A165137, A165611.

Sequence in context: A294692 A047109 A293028 * A092496 A045904 A034353

Adjacent sequences: A165607 A165608 A165609 * A165611 A165612 A165613

Keyword

nonn

Author

Tanya Khovanova, Sep 22 2009

Extensions

a(7)-a(25) from Andrew Howroyd, Mar 29 2016

Status

approved