login
A292187
Number of rooted unlabeled bipartite cubic maps on a compact closed oriented surface with 2*n vertices (and thus 3*n edges).
4
1, 2, 12, 112, 1392, 21472, 394752, 8421632, 204525312, 5572091392, 168331164672, 5585571889152, 201973854584832, 7905697598963712, 333049899230625792, 15025907115679875072, 722841343143300759552, 36935846945562562527232, 1997902532753538016346112, 114050521905958855289864192, 6852141240070150728132329472
OFFSET
0,2
COMMENTS
Equivalently, the number of rooted bicolored triangulations with 2*n triangles (and thus 3*n edges).
Equivalently, the number of pairs of permutations (alpha,sigma) up to simultaneous conjugacy on a pointed set of size 3*n with alpha^3=sigma^3=1, acting transitively and without fixed points.
This is also the S(3, -5, 1) sequence of Martin and Kearney.
This sequence is not D-finite (or holonomic).
LINKS
L. Ciobanu and A. Kolpakov, Free subgroups of free products and combinatorial hypermaps, arXiv:1708.03842 [math.CO], 2017-2019.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, arXiv:1103.4936 [math.CO], 2011.
FORMULA
a(0)=1, a(1)=2, a(n) = 3*n*a(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1) for n>=2.
From Peter Bala, Sep 01 2023: (Start)
The o.g.f. A(x) = 1 + 2*x + 12*x^2 + 112*x^3 + 1392*x^4 + 21472*x^5 + 394752*x^6 + ... satisfies the Riccati differential equation (3*x^2)*A'(x) = -1 + (1 - x)*A(x) - x*A(x)^2 with A(0) = 1.
O.g.f. as a continued fraction of Stieltjes type: A(x) = 1/(1 - 2*x/(1 - 4*x/(1 - 5*x/(1 - 7*x/(1 - 8*x/(1 - 10*x/(1 - ... ))))))).
Also A(x) = 1/(1 + 2*x - 4*x/(1 - 2*x/(1 - 7*x/(1 - 5*x/(1 - 10*x/(1 - 8*x/(1 - ... ))))))). (End)
PROG
(Python)
from sympy.core.cache import cacheit
@cacheit
def a(n): return n + 1 if n < 2 else 3*n*a(n - 1) + sum([a(k)*a(n - k - 1) for k in range(1, n - 1)])
[a(n) for n in range(21)]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Sasha Kolpakov, Sep 11 2017
STATUS
approved