login
A165610
The number of patterns of non-papaya words.
4
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.
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
KEYWORD
nonn
AUTHOR
Tanya Khovanova, Sep 22 2009
EXTENSIONS
a(7)-a(25) from Andrew Howroyd, Mar 29 2016
STATUS
approved