A165136 -id:A165136 - cp's OEIS frontend

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

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

Offset: 0

Sergei Bernstein and Tanya Khovanova, Sep 04 2009

nonn

Papaya words are concatenations of two palindromes or palindromes themselves. A165136 is the number of papaya patterns for n-digit numbers. Thus a(n) coincides with A165136 for small n, and is greater than A165136 for larger n. The actual number of n-digit 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. Adams-Watters, Apr 10 2011

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

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

Cf. A165136, A165135, A165610, A165611, A188792, A007055.

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}] (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

from functools import lru_cache
from sympy import bell, totient, proper_divisors
@lru_cache(maxsize=None)
def A165137(n): return (n*bell((n>>1)+1) if n&1 else (a:=n>>1)*(bell(a)+bell(a+1)))-sum(totient(n//d)*A165137(d) for d in proper_divisors(n,generator=True)) if n else 1 # Chai Wah Wu, Feb 19 2024

a(n) = R(n) - Sum_{d|n,dA000110(k). - Andrew Howroyd, Mar 29 2016

a(0) and a(7)-a(14) from Franklin T. Adams-Watters, Apr 10 2011

a(15)-a(30) from Andrew Howroyd, Mar 29 2016

A165610 The number of patterns of non-papaya words.

Original entry on oeis.org

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

Tanya Khovanova, Sep 22 2009

nonn

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

			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.

Tanya Khovanova, Papaya Words and Numbers

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

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

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

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

A165611 The number of n-digit non-papaya numbers.

Original entry on oeis.org

0, 0, 648, 7128, 85536, 870750, 8937054, 89606088, 899190558, 8995054860, 89990100090, 899940633714, 8999883000108, 89999307063540, 899998650010008, 8999992080398088, 89999984700000144, 899999910900869040, 8999999829000000162, 89999999010004961988

Offset: 1

Tanya Khovanova, Sep 22 2009

These are numbers that are neither palindromes nor concatenations of two palindromes. Three digit numbers that are non-papaya are numbers with all distinct digits. There are 9*9*8 of them: 648.

Tanya Khovanova, Papaya Words and Numbers

Cf. A165135, A165136, A165137, A165610.

a(n) = A052268(n) - A165135(n).

a(6)-a(20) from Andrew Howroyd, Mar 29 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A165610 The number of patterns of non-papaya words.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A165611 The number of n-digit non-papaya numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions