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
Keywords
Examples
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.
Links
- 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
Programs
-
Mathematica
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 *) -
Python
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
Formula
a(n) = R(n) - Sum_{d|n,dA000110(k). - Andrew Howroyd, Mar 29 2016
Extensions
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
Comments