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

Author

Tanya Khovanova, Sep 22 2009

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

• Tanya Khovanova, Papaya Words and Numbers

Crossrefs

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

Programs

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

Formula

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

Extensions

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