A165137 - OEIS

%I #29 Feb 19 2024 10:29:44

%S 1,1,2,4,10,21,50,99,250,454,1242,2223,6394,11389,35002,62034,202010,

%T 359483,1233518,2203507,7944110,14249736,53811584,96912709,382289362,

%U 691110821,2841057442,5154280744,22033974854,40105797777,177946445580

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

%C 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.

%C 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

%H Andrew Howroyd, <a href="/A165137/b165137.txt">Table of n, a(n) for n = 0..100</a>

%H Chuan Guo, J. Shallit, and A. M. Shur, <a href="http://arxiv.org/abs/1503.09112">On the Combinatorics of Palindromes and Antipalindromes</a>, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.

%H Tanya Khovanova, <a href="http://blog.tanyakhovanova.com/?p=177">Papaya Words and Numbers</a>

%F a(n) = R(n) - Sum_{d|n,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

%e 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.

%t R[k_?EvenQ] := (1/2)*k*(BellB[1 + k/2] + BellB[k/2]);

%t R[k_?OddQ] := k*BellB[1 + (k - 1)/2];

%t a[0] = 1; a[n_] := a[n] = R[n] - Sum[EulerPhi[n/d]*a[d], {d, Most[Divisors[ n]]}];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Oct 08 2017, after _Andrew Howroyd_ *)

%o (Python)

%o from functools import lru_cache

%o from sympy import bell, totient, proper_divisors

%o @lru_cache(maxsize=None)

%o 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

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

%K nonn

%O 0,3

%A Sergei Bernstein and _Tanya Khovanova_, Sep 04 2009

%E a(0) and a(7)-a(14) from _Franklin T. Adams-Watters_, Apr 10 2011

%E a(15)-a(30) from _Andrew Howroyd_, Mar 29 2016