A380622 -id:A380622 - cp's OEIS frontend

A062980 a(0) = 1, a(1) = 5; for n > 1, a(n) = 6na(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1).

1, 5, 60, 1105, 27120, 828250, 30220800, 1282031525, 61999046400, 3366961243750, 202903221120000, 13437880555850250, 970217083619328000, 75849500508999712500, 6383483988812390400000, 575440151532675686278125, 55318762960656722780160000

Offset: 0

Michael Praehofer (praehofer(AT)ma.tum.de), Jul 24 2001

Number of rooted unlabeled connected triangular maps on a compact closed oriented surface with 2n faces (and thus 3n edges). [Vidal]
Equivalently, the number of pair of permutations (sigma,tau) up to simultaneous conjugacy on a pointed set of size 6*n with sigma^3=tau^2=1, acting transitively and with no fixed point. [Vidal]
Also, the asymptotic expansion of the Airy function Ai'(x)/Ai(x) = -sqrt(x) - 1/(4x) + Sum_{n>=2} (-1)^n a(n) (4x)^ (1/2-3n/2). [Praehofer]
Maple 6 gives the wrong asymptotics of Ai'(x)=AiryAi(1,x) as x->oo apart from the 3rd term. Therefore asympt(AiryAi(1,x/4)/AiryAi(x/4),x); reproduces only the value a(1)=1 correctly.
Number of closed linear lambda terms (see [Bodini, Gardy, Jacquot, 2013] and [N. Zeilberger, 2015] references). - Pierre Lescanne, Feb 26 2017
Proved (bijection) by O. Bodini, D. Gardy, A. Jacquot (2013). - Olivier Bodini, Mar 30 2018
The September 2018 talk by Noam Zeilberger (see link to video) connects three topics (planar maps, Tamari lattices, lambda calculus) and eight sequences: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. - N. J. A. Sloane, Sep 17 2018

			1 + 5*x + 60*x^2 + 1105*x^3 + 27120*x^4 + 828250*x^5 + 30220800*x^6 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..100
O. Bodini, D. Gardy, and A. Jacquot, Asymptotics and random sampling for BCI and BCK lambda terms, Theor. Comput. Sci. 502: 227-238 (2013).
Jørgen Ellegaard Andersen, Gaëtan Borot, Leonid O. Chekhov and Nicolas Orantin, The ABCD of topological recursion, arXiv:1703.03307 [math-ph], 2017. [See Appendix A.1]
Laura Ciobanu and Alexander Kolpakov, Free subgroups of free products and combinatorial hypermaps, arXiv:1708.03842 [math.CO], 2017.
P. Cvitanovic, B. Lautrup and R. B. Pearson, The number and weights of Feynman diagrams, Phys. Rev. D18, (1978), 1939-1949, (eq 3.14 and fig 1b). DOI:10.1103/PhysRevD.18.1939
Bertrand Eynard, Topological expansion for the 1-hermitian matrix model correlation functions, Journal of High Energy Physics 11 (2004). [See Eq. (5.12) and Appendix A]
Steven R. Finch, Shapes of binary trees, June 24, 2004. [Cached copy, with permission of the author]
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 2024.
Éric Fusy, Luca Lionni, Adrian Tanasa, Combinatorial study of graphs arising from the Sachdev-Ye-Kitaev model, arXiv:1810.02146 [math.CO], 2018.
Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, How big is BCI fragment of BCK logic, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. [From _N. J. A. Sloane_, Feb 21 2012]
Kristian Gustavsson and Bernhard Mehlig, Statistical models for spatial patterns of heavy particles in turbulence, arxiv:1412.4374 [physics.flu-dyn], 2014-2016. [See Figure 14]
M. J. Kearny and R. J. Martin, Normalized functionals of first passage Brownian motion and a curious connection with the maximal relative height of fluctuating interfaces, J. Phys. A, Math. Theor. 49, No. 19, Article ID 195001, 20 p. (2016).
George Kaye, A visualiser for linear lambda-terms as 3-valent rooted maps, University of Birmingham (UK, 2019).
S. Janson, The Wiener index of simply generated random trees, Random Structures Algorithms 22 (2003) 337-358.
Michael J. Kearney, Satya N. Majumdar and Richard J. Martin, The first-passage area for drifted Brownian motion and the moments of the Airy distribution, arXiv:0706.2038 [cond-mat.stat-mech], 2007. [a(n) = 8^n * K_n from Eq. (3)]
Pierre Lescanne, Quantitative aspects of linear and affine closed lambda terms, arXiv:1702.03085 [cs.DM], 2017. Also in ACM Transactions on Computational Logic (TOCL 2019), Vol. 19, No. 2, Article No. 9.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. See p. 292.
NIST Digital Library of Mathematical Functions, Airy Functions.
A. N. Stokes, Continued fraction solutions of the Riccati equation, Bull. Austral. Math. Soc. Vol. 25 (1982), 207-214.
Paul Tarau and Valeria de Paiva, Deriving Theorems in Implicational Linear Logic, Declaratively, arXiv:2009.10241 [cs.LO], 2020. See also Github, (2020).
Samuel Vidal and Michel Petitot, Counting Rooted and Unrooted Triangular Maps, Journal of Nonlinear Systems and Applications (2009) 151-154.
Eric Weisstein's World of Mathematics, Airy Functions, contains the definitions of Ai(x), Bi(x).
Noam Zeilberger, Counting isomorphism classes of beta-normal linear lambda terms, arXiv:1509.07596 [cs.LO], 2015.
Noam Zeilberger, Linear lambda terms as invariants of rooted trivalent maps, arXiv preprint arXiv:1512.06751 [cs.LO], 2015.
Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018.
Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv preprint 1803.10030 [math.LO], March 2018 (A revised version of a 2017 conference paper).
Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Part 2, Rutgers Experimental Math Seminar, Sep 13 2018.
Noam Zeilberger and Alain Giorgetti, A correspondence between rooted planar maps and normal planar lambda terms, arXiv:1408.5028 [cs.LO], 2014-2015; Logical Methods in Computer Science, vol. 11 (3:22), 2015, pp. 1-39.

Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
With interspersed zeros column 3 of A380622.
Pointed version of A129114.
Connected pointed version of A129115.
Cf. A060506, A060507, A094199, A121350, A121352, A005133, A172455.

a062980 n = a062980_list !! n
a062980_list = 1 : 5 : f 2 [5,1] where
   f u vs'@(v:vs) = w : f (u + 1) (w : vs') where
     w = 6 * u * v + sum (zipWith (*) vs_ $ reverse vs_)
     vs_ = init vs
-- Reinhard Zumkeller, Jun 03 2013

a:= proc(n) option remember; `if`(n<2, 4*n+1,
      6*n*a(n-1) +add(a(k)*a(n-k-1), k=1..n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Mar 31 2017

max = 16; f[y_] := -Sqrt[x] - 1/(4*x) + Sum[(-1)^n*a[n]*(4*x)^(1/2 - 3*(n/2)), {n, 2, max}] /. x -> 1/y^2; s[y_] := Normal[ Series[ AiryAiPrime[x] / AiryAi[x], {x, Infinity, max + 7}]] /. x -> 1/y^2; sol = SolveAlways[ Simplify[ f[y] == s[y], y > 0], y] // First; Join[{1, 5}, Table[a[n], {n, 3, max}] /. sol] (* Jean-François Alcover, Oct 09 2012, from Airy function asymptotics *)
a[0] = 1; a[n_] := a[n] = (6*(n-1)+4)*a[n-1] + Sum[a[i]*a[n-i-1], {i, 0, n-1}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Nov 29 2013, after Vladimir Reshetnikov *)

{a(n) = local(A); n++; if( n<1, 0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = (6*k - 8) * A[k-1] + sum( j=1, k-1, A[j] * A[k-j])); A[n])} /* Michael Somos, Jul 24 2011 */

from sympy.core.cache import cacheit
@cacheit
def a(n): return n*4 + 1 if n<2 else 6*n*a(n - 1) + sum(a(k)*a(n - k - 1) for k in range(1, n - 1))
print([a(n) for n in range(21)]) # Indranil Ghosh, Aug 09 2017

With offset 1, then a(1) = 1 and, for n > 1, a(n) = (6*n-8)*a(n-1) + Sum_{k=1..n-1} a(k)*a(n-k) [Praehofer] [Martin and Kearney].
a(n) = (6/Pi^2)*Integral_{x=0..oo} ((4*x)^(3*n/2)/(Ai(x)^2 + Bi(x)^2)) dt. - Vladimir Reshetnikov, Sep 24 2013
a(n) ~ 3 * 6^n * n! / Pi. - Vaclav Kotesovec, Jan 19 2015
0 = 6*x^2*y' + x*y^2 + (4*x-1)*y + 1, where y(x) = Sum_{n>=0} a(n)*x^n. - Gheorghe Coserea, Apr 02 2017
From Peter Bala, May 21 2017: (Start)
G.f. as an S-fraction: A(x) = 1/(1 - 5*x/(1 - 7*x/(1 - 11*x/(1 - 13*x/(1 - ... - (6*n - 1)*x/(1 - (6*n + 1)*x/(1 - .... See Stokes.
x*A(x) = B(x)/(1 + 2*B(x)), where B(x) = x + 7*x^2 + 84*x^3 + 1463*x^4 + ... is the o.g.f. of A172455.
A(x) = 1/(1 + 2*x - 7*x/(1 - 5*x/(1 - 13*x/(1 - 11*x/(1 - ... - (6*n + 1)*x/(1 - (6*n - 1)*x/(1 - .... (End)

Entry revised by N. J. A. Sloane based on comments from Samuel A. Vidal, Mar 30 2007

A380626 Array read by antidiagonals: T(n,k) is the number of sensed k-regular combinatorial maps with n vertices, n >= 0, k >= 1.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 2, 3, 1, 0, 1, 0, 7, 0, 1, 0, 1, 5, 29, 36, 11, 1, 0, 1, 0, 174, 0, 365, 0, 1, 0, 1, 18, 1475, 26614, 44106, 5250, 81, 1, 0, 1, 0, 16162, 0, 10107019, 0, 103801, 0, 1, 0, 1, 105, 214215, 102762168, 3703659517, 6605320523, 549530780, 2492164, 1228, 1, 0

Offset: 0

Andrew Howroyd, Jan 29 2025

The combinatorial maps considered are connected, unrooted, unlabeled, may have loops and parallel edges and are of any orientable genus.

			Array begins:
==================================================================
n\k | 1 2  3       4         5          6          7         8 ...
----+-------------------------------------------------------------
  0 | 1 1  1       1         1          1          1         1 ...
  1 | 0 1  0       2         0          5          0        18 ...
  2 | 1 1  3       7        29        174       1475     16162 ...
  3 | 0 1  0      36         0      26614          0 102762168 ...
  4 | 0 1 11     365     44106   10107019 3703659517 ...
  5 | 0 1  0    5250         0 6605320523 ...
  6 | 0 1 81  103801 549530780 ...
  7 | 0 1  0 2492164 ...
   ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)

Columns 2..6 (odd columns with interspersed zeros) are A000012, A129114, A292206, A380627, A380628.
Row n=1 is A007769 (with interspersed zeros).
Cf. A170946, A380622 (rooted), A380629.

InvEulerT(v)={dirdiv(Vec(log(1+x*Ser(v)),-#v), vector(#v,n,1/n))}
D(m,k)={my(g=gcd(m,k)); sumdiv(g, d, my(j=m/d); x^j*eulerphi(d)*k^(j-1)/j)}
G(n,m)={my(t=m*n); prod(k=1, t, my(A=O(x^(t\k+1)), p=serconvol(exp(A + D(m,k)), exp(A + D(2,k)))); sum(r=0, t\k, if(k*r%m==0, r!*polcoef(p,r)/(k^r)*x^(k*r/m)), O(x*x^n)) )}
T(n,k)=if(n==0, 1, InvEulerT(Vec(-1 + G(n,k), -n))[n])

A380629(n) = Sum_{d|2*n} T(d,2*n/d).

A292186 Number of rooted unlabeled connected four-regular maps on a compact closed oriented surface with n vertices (and thus 2*n edges), with a(0) = 1.

Original entry on oeis.org

1, 3, 24, 297, 4896, 100278, 2450304, 69533397, 2247492096, 81528066378, 3280382613504, 145009234904922, 6986546222800896, 364418301804218028, 20459842995693256704, 1230262900677124568397, 78884016707711348637696, 5372823210133041283250178, 387394283866652086938107904

Offset: 0

Sasha Kolpakov, Sep 11 2017

Equivalently, the number of rooted quadrangulations of oriented surfaces with n quadrangles (and thus 2*n edges) for n > 0.
Equivalently, the number of pairs (alpha,sigma) of permutations on a pointed set of size 4*n up to simultaneous conjugacy such that alpha (resp. sigma) has only cycles of length 2 (resp. 4) and the subgroup generated by them acts transitively, for n > 0.
This is also the S(4, -6, 1) sequence of Martin and Kearney, if the offset is set to 1.
This sequence is not D-finite (or holonomic).

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.
A. N. Stokes, Continued fraction solutions of the Riccati equation, Bull. Austral. Math. Soc. Vol. 25 (1982), 207-214.

Column 4 of A380622.

Cf. A172455, A292187, A128709.

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

a(0)=1, a(1)=3, a(n) = 4*n*a(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1) for n>=2.
From Peter Bala, Aug 22 2023: (Start)
The o.g.f. A(x) = 1 + 3*x + 24*x^2 + 297*x^3 + 4896*x^4 + 100278*x^5 + 2450304*x^6 + ... satisfies the Riccati differential equation (4*x^2)*A'(x) = -1 + (1 - 2*x)*A(x) - x*A(x)^2 with A(0) = 1.
O.g.f. as a continued fraction of Stieltjes type: 1/(1 - 3*x/(1 - 5*x/(1 - 7*x/(1 - 9*x/(1 - ... - (2*n+1)*x/(1 - ... )))))).
Also A(x) = 1/(1 + 2*x - 5*x/(1 - 3*x/(1 - 9*x/(1 - 7*x/(1 - ... - (4*n+1)*x/(1 - (4*n-1)*x/(1 - ... ))))))). (End)

Edited by Andrey Zabolotskiy, Jan 23 2025

cp's OEIS Frontend

A062980 a(0) = 1, a(1) = 5; for n > 1, a(n) = 6*n*a(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A380626 Array read by antidiagonals: T(n,k) is the number of sensed k-regular combinatorial maps with n vertices, n >= 0, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A292186 Number of rooted unlabeled connected four-regular maps on a compact closed oriented surface with n vertices (and thus 2*n edges), with a(0) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

Extensions

A380623 Number of rooted 5-regular combinatorial maps with 2n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

A380624 Number of rooted 6-regular combinatorial maps with n vertices.

Views

Author

Keywords

Links

Crossrefs

A380625 Number of rooted regular combinatorial maps with n edges.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A380629 Number of sensed regular combinatorial maps with n edges.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A062980 a(0) = 1, a(1) = 5; for n > 1, a(n) = 6na(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1).