cp's OEIS Frontend

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

%I A165137 #29 Feb 19 2024 10:29:44
%S A165137 1,1,2,4,10,21,50,99,250,454,1242,2223,6394,11389,35002,62034,202010,
%T A165137 359483,1233518,2203507,7944110,14249736,53811584,96912709,382289362,
%U A165137 691110821,2841057442,5154280744,22033974854,40105797777,177946445580
%N A165137 a(n) is the number of patterns for n-character papaya words in an infinite alphabet.
%C A165137 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 A165137 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 A165137 Andrew Howroyd, <a href="/A165137/b165137.txt">Table of n, a(n) for n = 0..100</a>
%H A165137 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 A165137 Tanya Khovanova, <a href="http://blog.tanyakhovanova.com/?p=177">Papaya Words and Numbers</a>
%F A165137 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 A165137 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 A165137 R[k_?EvenQ] := (1/2)*k*(BellB[1 + k/2] + BellB[k/2]);
%t A165137 R[k_?OddQ] := k*BellB[1 + (k - 1)/2];
%t A165137 a[0] = 1; a[n_] := a[n] = R[n] - Sum[EulerPhi[n/d]*a[d], {d, Most[Divisors[ n]]}];
%t A165137 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Oct 08 2017, after _Andrew Howroyd_ *)
%o A165137 (Python)
%o A165137 from functools import lru_cache
%o A165137 from sympy import bell, totient, proper_divisors
%o A165137 @lru_cache(maxsize=None)
%o A165137 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 A165137 Cf. A165136, A165135, A165610, A165611, A188792, A007055.
%K A165137 nonn
%O A165137 0,3
%A A165137 Sergei Bernstein and _Tanya Khovanova_, Sep 04 2009
%E A165137 a(0) and a(7)-a(14) from _Franklin T. Adams-Watters_, Apr 10 2011
%E A165137 a(15)-a(30) from _Andrew Howroyd_, Mar 29 2016