A292187 Number of rooted unlabeled bipartite cubic maps on a compact closed oriented surface with 2*n vertices (and thus 3*n edges), with a(0) = 1.

1, 2, 12, 112, 1392, 21472, 394752, 8421632, 204525312, 5572091392, 168331164672, 5585571889152, 201973854584832, 7905697598963712, 333049899230625792, 15025907115679875072, 722841343143300759552, 36935846945562562527232, 1997902532753538016346112, 114050521905958855289864192, 6852141240070150728132329472

Offset: 0

Author

Sasha Kolpakov, Sep 11 2017

Keywords

• nonn
• easy

Comments

Equivalently, the number of rooted bicolored triangulations with 2*n triangles (and thus 3*n edges) for n > 0.

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, for n > 0.

This is also the S(3, -5, 1) sequence of Martin and Kearney, if the offset is set to 1.

This sequence is not D-finite (or holonomic).

Links

• Sasha Kolpakov, Table of n, a(n) for n = 0..119
• Laura Ciobanu and Alexander Kolpakov, Free subgroups of free products and combinatorial hypermaps, Discrete Mathematics, 342 (2019), 1415-1433; arXiv:1708.03842 [math.CO], 2017-2019.
• R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318; arXiv:1103.4936 [math.CO], 2011.

Crossrefs

Cf. A000698, A062980, A292186.

Programs

Python

from sympy.core.cache import cacheit
@cacheit
def a(n): return 1 if n == 0 else (3*n - 1)*a(n - 1) + sum([a(k)*a(n - k - 1) for k in range(1, n)])
[a(n) for n in range(21)]

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)

Extensions

Edited by Andrey Zabolotskiy, Jan 23 2025