A062980 - OEIS

%I #222 Dec 18 2024 09:22:06

%S 1,5,60,1105,27120,828250,30220800,1282031525,61999046400,

%T 3366961243750,202903221120000,13437880555850250,970217083619328000,

%U 75849500508999712500,6383483988812390400000,575440151532675686278125,55318762960656722780160000

%N 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).

%C Number of rooted unlabeled connected triangular maps on a compact closed oriented surface with 2n faces (and thus 3n edges). [Vidal]

%C 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]

%C 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]

%C 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.

%C Number of closed linear lambda terms (see [Bodini, Gardy, Jacquot, 2013] and [N. Zeilberger, 2015] references). - _Pierre Lescanne_, Feb 26 2017

%C Proved (bijection) by O. Bodini, D. Gardy, A. Jacquot (2013). - _Olivier Bodini_, Mar 30 2018

%C 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

%H Reinhard Zumkeller, <a href="/A062980/b062980.txt">Table of n, a(n) for n = 0..100</a>

%H O. Bodini, D. Gardy, and A. Jacquot, <a href="https://doi.org/10.1016/j.tcs.2013.01.008">Asymptotics and random sampling for BCI and BCK lambda terms</a>, Theor. Comput. Sci. 502: 227-238 (2013).

%H Jørgen Ellegaard Andersen, Gaëtan Borot, Leonid O. Chekhov and Nicolas Orantin, <a href="https://arxiv.org/abs/1703.03307">The ABCD of topological recursion</a>, arXiv:1703.03307 [math-ph], 2017. [See Appendix A.1]

%H Laura Ciobanu and Alexander Kolpakov, <a href="https://arxiv.org/abs/1708.03842">Free subgroups of free products and combinatorial hypermaps</a>, arXiv:1708.03842 [math.CO], 2017.

%H P. Cvitanovic, B. Lautrup and R. B. Pearson, <a href="https://cns.gatech.edu/~predrag/papers/PRD18-78.pdf">The number and weights of Feynman diagrams</a>, Phys. Rev. D18, (1978), 1939-1949, (eq 3.14 and fig 1b). <a href="https://doi.org/10.1103/PhysRevD.18.1939">DOI:10.1103/PhysRevD.18.1939</a>

%H Bertrand Eynard, <a href="http://ipht.cea.fr/Docspht/articles/t04/086/public/1126-6708_2004_11_031.pdf">Topological expansion for the 1-hermitian matrix model correlation functions</a>, Journal of High Energy Physics 11 (2004). [See Eq. (5.12) and Appendix A]

%H Steven R. Finch, <a href="/A062980/a062980.pdf">Shapes of binary trees</a>, June 24, 2004. [Cached copy, with permission of the author]

%H Steven R. Finch, <a href="https://arxiv.org/abs/2408.12440">An exceptional convolutional recurrence</a>, arXiv:2408.12440 [math.CO], 2024.

%H Éric Fusy, Luca Lionni, Adrian Tanasa, <a href="https://arxiv.org/abs/1810.02146">Combinatorial study of graphs arising from the Sachdev-Ye-Kitaev model</a>, arXiv:1810.02146 [math.CO], 2018.

%H Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, <a href="http://arxiv.org/abs/1112.0643">How big is BCI fragment of BCK logic</a>, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. [From _N. J. A. Sloane_, Feb 21 2012]

%H Kristian Gustavsson and Bernhard Mehlig, <a href="https://arxiv.org/abs/1412.4374">Statistical models for spatial patterns of heavy particles in turbulence</a>, arxiv:1412.4374 [physics.flu-dyn], 2014-2016. [See Figure 14]

%H M. J. Kearny and R. J. Martin, <a href="https://doi.org/10.1088/1751-8113/49/19/195001">Normalized functionals of first passage Brownian motion and a curious connection with the maximal relative height of fluctuating interfaces</a>, J. Phys. A, Math. Theor. 49, No. 19, Article ID 195001, 20 p. (2016).

%H George Kaye, <a href="https://www.georgejkaye.com/pages/lambda-visualiser/docs/2019-04-08-final-report.pdf">A visualiser for linear lambda-terms as 3-valent rooted maps</a>, University of Birmingham (UK, 2019).

%H S. Janson, <a href="http://dx.doi.org/10.1002/rsa.10074">The Wiener index of simply generated random trees</a>, Random Structures Algorithms 22 (2003) 337-358.

%H Michael J. Kearney, Satya N. Majumdar and Richard J. Martin, <a href="http://arxiv.org/abs/0706.2038">The first-passage area for drifted Brownian motion and the moments of the Airy distribution</a>, arXiv:0706.2038 [cond-mat.stat-mech], 2007. [a(n) = 8^n * K_n from Eq. (3)]

%H Pierre Lescanne, <a href="https://arxiv.org/abs/1702.03085">Quantitative aspects of linear and affine closed lambda terms</a>, arXiv:1702.03085 [cs.DM], 2017. Also in <a href="https://doi.org/10.1145/3173547">ACM Transactions on Computational Logic (TOCL 2019)</a>, Vol. 19, No. 2, Article No. 9.

%H R. J. Martin and M. J. Kearney, <a href="http://dx.doi.org/10.1007/s00010-010-0051-0">An exactly solvable self-convolutive recurrence</a>, Aequat. Math., 80 (2010), 291-318. See p. 292.

%H NIST Digital Library of Mathematical Functions, <a href="http://dlmf.nist.gov/9.5">Airy Functions</a>.

%H A. N. Stokes, <a href="https://doi.org/10.1017/S0004972700005219">Continued fraction solutions of the Riccati equation</a>, Bull. Austral. Math. Soc. Vol. 25 (1982), 207-214.

%H Paul Tarau and Valeria de Paiva, <a href="https://arxiv.org/abs/2009.10241">Deriving Theorems in Implicational Linear Logic, Declaratively</a>, arXiv:2009.10241 [cs.LO], 2020. See also <a href="https://vcvpaiva.github.io/includes/pubs/2020-tarau.pdf">Github</a>, (2020).

%H Samuel Vidal and Michel Petitot, <a href="http://www.cafemath.fr/articles/VidalPetitot09-1.pdf">Counting Rooted and Unrooted Triangular Maps</a>, Journal of Nonlinear Systems and Applications (2009) 151-154.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/AiryFunctions.html">Airy Functions</a>, contains the definitions of Ai(x), Bi(x).

%H Noam Zeilberger, <a href="http://arxiv.org/abs/1509.07596">Counting isomorphism classes of beta-normal linear lambda terms</a>, arXiv:1509.07596 [cs.LO], 2015.

%H Noam Zeilberger, <a href="https://arxiv.org/abs/1512.06751">Linear lambda terms as invariants of rooted trivalent maps</a>, arXiv preprint arXiv:1512.06751 [cs.LO], 2015.

%H Noam Zeilberger, <a href="https://arxiv.org/abs/1804.10540">A theory of linear typings as flows on 3-valent graphs</a>, arXiv:1804.10540 [cs.LO], 2018.

%H Noam Zeilberger, <a href="https://arxiv.org/abs/1803.10080">A Sequent Calculus for a Semi-Associative Law</a>, arXiv preprint 1803.10030 [math.LO], March 2018 (A revised version of a 2017 conference paper).

%H Noam Zeilberger, <a href="https://vimeo.com/289907363">A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video)</a>, <a href="https://vimeo.com/289910554">Part 2</a>, Rutgers Experimental Math Seminar, Sep 13 2018.

%H Noam Zeilberger and Alain Giorgetti, <a href="http://arxiv.org/abs/1408.5028">A correspondence between rooted planar maps and normal planar lambda terms</a>, arXiv:1408.5028 [cs.LO], 2014-2015; Logical Methods in Computer Science, vol. 11 (3:22), 2015, pp. 1-39.

%F 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].

%F 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

%F a(n) ~ 3 * 6^n * n! / Pi. - _Vaclav Kotesovec_, Jan 19 2015

%F 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

%F From _Peter Bala_, May 21 2017: (Start)

%F 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.

%F 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.

%F 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)

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

%p a:= proc(n) option remember; `if`(n<2, 4*n+1,

%p       6*n*a(n-1) +add(a(k)*a(n-k-1), k=1..n-2))

%p     end:

%p seq(a(n), n=0..25);  # _Alois P. Heinz_, Mar 31 2017

%t 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 *)

%t 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_ *)

%o (PARI) {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 */

%o (Haskell)

%o a062980 n = a062980_list !! n

%o a062980_list = 1 : 5 : f 2 [5,1] where

%o    f u vs'@(v:vs) = w : f (u + 1) (w : vs') where

%o      w = 6 * u * v + sum (zipWith (*) vs_ $ reverse vs_)

%o      vs_ = init vs

%o -- _Reinhard Zumkeller_, Jun 03 2013

%o (Python)

%o from sympy.core.cache import cacheit

%o @cacheit

%o 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))

%o print([a(n) for n in range(21)]) # _Indranil Ghosh_, Aug 09 2017

%Y Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.

%Y Pointed version of A012114. Connected pointed version of A012115. [Xrefs A012114 and A012115 are probably wrong. - _Vaclav Kotesovec_, Jan 27 2015]

%Y Cf. A060506, A060507, A094199, A121350, A121352, A005133, A172455.

%K nonn,nice,easy,changed

%O 0,2

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

%E Entry revised by _N. J. A. Sloane_ based on comments from _Samuel A. Vidal_, Mar 30 2007