A062980 -id:A062980 - cp's OEIS frontend

A262301 Number of normal linear lambda terms of size n with no free variables.

1, 3, 26, 367, 7142, 176766, 5304356, 186954535, 7566084686, 345664350778, 17592776858796, 986961816330662, 60502424162842876, 4023421969420255644, 288464963899330354104, 22180309834307193611287, 1820641848410408158704734, 158897008602951290424279330

Offset: 1

N. J. A. Sloane, Sep 30 2015

nonn

			A(x) = x + 3*x^2 + 26*x^3 + 367*x^4 + 7142*x^5 + ...

Gheorghe Coserea, Table of n, a(n) for n = 1..100
Paul Tarau, Valeria de Paiva, Deriving Theorems in Implicational Linear Logic, Declaratively, arXiv:2009.10241 [cs.LO], 2020. See also Github, (2020).
Noam Zeilberger, Counting isomorphism classes of beta-normal linear lambda terms, arXiv:1509.07596 [cs.LO], 2015.
Wikipedia, Lambda calculus

Column 0 of A318110.

Cf. A062980, A267827.

terms = 18; F[, ] = 0;
Do[F[x_, t_] = Series[x t/(1-F[x, t]) + D[F[x, t], t], {x, 0, terms}, {t, 0, terms}] // Normal, {2 terms}];
CoefficientList[F[x, 0], x][[2 ;; terms+1]] (* Jean-François Alcover, Sep 02 2018, after Gheorghe Coserea *)

F(N) = {
  my(x='x+O('x^N), t='t, F0=x, F1=0, n=1);
  while(n++,
    F1 = x*t/(1-F0) + deriv(F0,t);
    if (F1 == F0, break()); F0 = F1;);
  F0;
};
seq(N) = Vec(subst(F(N+1), 't, 0));
seq(18) \\ Gheorghe Coserea, Apr 01 2017

A(x) = F(x,0), where A(x) = Sum_{n>=1} a(n)*x^n and F(x,t) satisfies F = x*t/(1-F) + deriv(F,t), with F(0,t)=0, deriv(F,x)(0,t)=1+t. - Gheorghe Coserea, Apr 01 2017

More terms from Gheorghe Coserea, Apr 01 2017

A281270 a(n) is the number of closed BCK (a.k.a. affine) lambda terms of size n.

Original entry on oeis.org

0, 0, 1, 2, 3, 9, 30, 81, 242, 838, 2799, 9365, 33616, 122937, 449698, 1696724, 6558855, 25559806, 101294687, 409363758, 1673735259, 6928460475, 29115833976, 123835124242, 532449210893, 2317382872404, 10199542298725, 45345006540851, 203704505953902, 924427259637953, 4234544300812834

Offset: 0

Gheorghe Coserea, Apr 02 2017

nonn

It appears that for n >= 1, a(n + 5) == a(n) (mod 5), a(n + 38*7) == a(n) (mod 7), a(n + 30*11) == a(n) (mod 11) and a(n + 288*17) == a(n) (mod 17). - Peter Bala, Apr 11 2022

			A(x) = x^2 + 2*x^3 + 3*x^4 + 9*x^5 + 30*x^6 + 81*x^7 + 242*x^8 + ...

Gheorghe Coserea, Table of n, a(n) for n = 0..201
O. Bodini, D. Gardy, and A. Jacquot, Asymptotics and random sampling for BCI and BCK lambda terms, Theor. Comput. Sci. 502: 227-238 (2013).
Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, How big is BCI fragment of BCK logic, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. (the authors of the paper incorrectly identified this sequence as A073950)
Pierre Lescanne, Quantitative aspects of linear and affine closed lambda term, arXiv:1702.03085 [cs.DM], 2017.

Cf. A062980, A262301, A267827.

a[0] = a[1] = 0; a[n_] := a[n] = 1 + a[n - 1] + 2 Sum[ k a[k], {k, 2, n - 3}] + Sum[a[k] a[n - 1 - k], {k, 2, n - 3}]; Table[a@ n, {n, 0, 30}] (* Michael De Vlieger, Apr 02 2017 *)

seq(N) = {
  my(a = vector(N));
  for (n=2, N, my(s1 = sum(k=2, n-3, k*a[k]));
    a[n] = 1 + a[n-1] + 2*s1 + sum(k=2, n-3, a[k]*a[n-1-k]));
  concat(0,a);
};
seq(30)
\\ test: y = Ser(seq(201)); 0 == 2*x^4*y' + (x-x^2)*y^2 - (1-x)^2*y + x^2

a(n) = 1 + a(n-1) + 2*Sum_{k=2..n-3} k*a(k) + Sum_{k=2..n-3} a(k)*a(n-1-k) for n>=2.
0 = 2*x^4*y' + (x-x^2)*y^2 - (1-x)^2*y + x^2, where y(x) is the g.f.
a(3*n+1) = Sum_{k=0..n-1} binomial(3*n,3*k+1)*A062980(k).

Name clarified by Pierre Lescanne, May 19 2017

A129114 Number of unrooted unlabeled connected triangular maps on a compact closed oriented surface with 2n faces (and thus 3n edges).

Original entry on oeis.org

1, 3, 11, 81, 1228, 28174, 843186, 30551755, 1291861997, 62352938720, 3381736322813, 203604398647922, 13475238697911184, 972429507963453210, 75993857157285258473, 6393779463050776636807, 576237114190853665462712, 55385308766655472416299110, 5655262782600929403228668176

Offset: 0

Samuel A. Vidal, Mar 30 2007

nonn

Equivalently, the number of pairs of permutations (sigma,tau) up to simultaneous conjugacy on a set of size 6*n with sigma^3=tau^2=1, acting transitively and with no fixed point.

Andrew Howroyd, Table of n, a(n) for n = 0..300

Column 3 of A380626.
Connected version of A129115.
Unrooted version of A062980.
Cf. also A121350, A121352, A005133.

Inverse Euler transform of A129115. - Andrew Howroyd, Jan 29 2025

a(0)=1 prepended and terms a(17) onwards from Andrew Howroyd, Jan 29 2025

A129115 Number of unrooted unlabeled not necessarily connected triangular maps on a compact closed oriented surface with 2n faces (and thus 3n edges).

Original entry on oeis.org

1, 3, 17, 124, 1618, 33564, 956263, 33736198, 1402665692, 66902717187, 3596481426812, 215049652739982, 14154852098315796, 1016911004448831247, 79174846391508487198, 6640511488761139957873, 596865894849670793348763, 57234563024075319273338452, 5832189914390355126473955563

Offset: 0

Samuel A. Vidal, Mar 30 2007

nonn

Equivalently, the number of pair of permutations (sigma,tau) up to simultaneous conjugacy on a set of size 6*n with sigma^3=tau^2=1 with no fixed point.

Andrew Howroyd, Table of n, a(n) for n = 0..300

Not necessarily connected version of A129114.
Unrooted, not necessarily connected version of A062980.
Cf. also A121350, A121352, A005133.

D(m,k)={my(g=gcd(m,k)); sumdiv(g, d, my(j=m/d); x^j*eulerphi(d)*k^(j-1)/j)}
seq(n)={my(t=6*n); Vec(prod(k=1, t, my(A=O(x^(t\k+1)), p=serconvol(exp(A + D(3,k)), exp(A + D(2,k)))); sum(r=0, t\k, if(k*r%6==0, r!*polcoef(p,r)/(k^r)*x^(k*r/6)), O(x*x^n)) ))} \\ Andrew Howroyd, Jan 29 2025

Euler transform of A129114. - Andrew Howroyd, Jan 29 2025

a(17) onwards from Andrew Howroyd, Jan 28 2025

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

Original entry on oeis.org

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

Offset: 0

Sasha Kolpakov, Sep 11 2017

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

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.

Cf. A000698, A062980, A292186.

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)]

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)

Edited by Andrey Zabolotskiy, Jan 23 2025

A172455 The case S(6,-4,-1) of the family of self-convolutive recurrences studied by Martin and Kearney.

Original entry on oeis.org

1, 7, 84, 1463, 33936, 990542, 34938624, 1445713003, 68639375616, 3676366634402, 219208706540544, 14397191399702118, 1032543050697424896, 80280469685284582812, 6725557192852592984064, 603931579625379293509683

Offset: 1

N. J. A. Sloane, Nov 20 2010

nonn

			G.f. = x + 7*x^2 + 84*x^3 + 1463*x^4 + 33936*x^5 + 990542*x^6 + 34938624*x^7 + ...
a(2) = 7 since (6*2 - 4) * a(2-1) - (a(1) * a(2-1)) = 7.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 307.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, arXiv:1103.4936 [math.CO], 2011.
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.
Eric Weisstein's World of Mathematics, Airy Functions, contains the definitions of Ai(x), Bi(x).

Cf. A000079 S(1,1,-1), A000108 S(0,0,1), A000142 S(1,-1,0), A000244 S(2,1,-2), A000351 S(4,1,-4), A000400 S(5,1,-5), A000420 S(6,1,-6), A000698 S(2,-3,1), A001710 S(1,1,0), A001715 S(1,2,0), A001720 S(1,3,0), A001725 S(1,4,0), A001730 S(1,5,0), A003319 S(1,-2,1), A005411 S(2,-4,1), A005412 S(2,-2,1), A006012 S(-1,2,2), A006318 S(0,1,1), A047891 S(0,2,1), A049388 S(1,6,0), A051604 S(3,1,0), A051605 S(3,2,0), A051606 S(3,3,0), A051607 S(3,4,0), A051608 S(3,5,0), A051609 S(3,6,0), A051617 S(4,1,0), A051618 S(4,2,0), A051619 S(4,3,0), A051620 S(4,4,0), A051621 S(4,5,0), A051622 S(4,6,0), A051687 S(5,1,0), A051688 S(5,2,0), A051689 S(5,3,0), A051690 S(5,4,0), A051691 S(5,5,0), A053100 S(6,1,0), A053101 S(6,2,0), A053102 S(6,3,0), A053103 S(6,4,0), A053104 S(7,1,0), A053105 S(7,2,0), A053106 S(7,3,0), A062980 S(6,-8,1), A082298 S(0,3,1), A082301 S(0,4,1), A082302 S(0,5,1), A082305 S(0,6,1), A082366 S(0,7,1), A082367 S(0,8,1), A105523 S(0,-2,1), A107716 S(3,-4,1), A111529 S(1,-3,2), A111530 S(1,-4,3), A111531 S(1,-5,4), A111532 S(1,-6,5), A111533 S(1,-7,6), A111546 S(1,0,1), A111556 S(1,1,1), A143749 S(0,10,1), A146559 S(1,1,-2), A167872 S(2,-3,2), A172450 S(2,0,-1), A172485 S(-1,-2,3), A177354 S(1,2,1), A292186 S(4,-6,1), A292187 S(3, -5, 1).

a[1] = 1; a[n_]:= a[n] = (6*n-4)*a[n-1] - Sum[a[k]*a[n-k], {k, 1, n-1}]; Table[a[n], {n, 1, 20}] (* Vaclav Kotesovec, Jan 19 2015 *)

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

S(v1, v2, v3, N=16) = {
  my(a = vector(N)); a[1] = 1;
  for (n = 2, N, a[n] = (v1*n+v2)*a[n-1] + v3*sum(j=1,n-1,a[j]*a[n-j])); a;
};
S(6,-4,-1)
\\ test: y = x*Ser(S(6,-4,-1,201)); 6*x^2*y' == y^2 - (2*x-1)*y - x
\\ Gheorghe Coserea, May 12 2017

a(n) = (6*n - 4) * a(n-1) - Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - Michael Somos, Jul 24 2011
G.f.: x / (1 - 7*x / (1 - 5*x / (1 - 13*x / (1 - 11*x / (1 - 19*x / (1 - 17*x / ... )))))). - Michael Somos, Jan 03 2013
a(n) = 3/(2*Pi^2)*int((4*x)^((3*n-1)/2)/(Ai'(x)^2+Bi'(x)^2), x=0..inf), where Ai'(x), Bi'(x) are the derivatives of the Airy functions. [Vladimir Reshetnikov, Sep 24 2013]
a(n) ~ 6^n * (n-1)! / (2*Pi) [Martin + Kearney, 2011, p.16]. - Vaclav Kotesovec, Jan 19 2015
6*x^2*y' = y^2 - (2*x-1)*y - x, where y(x) = Sum_{n>=1} a(n)*x^n. - Gheorghe Coserea, May 12 2017
G.f.: x/(1 - 2*x - 5*x/(1 - 7*x/(1 - 11*x/(1 - 13*x/(1 - ... - (6*n - 1)*x/(1 - (6*n + 1)*x/(1 - .... Cf. A062980. - Peter Bala, May 21 2017

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

Original entry on oeis.org

1, 49, 9800, 4412401, 3530881200, 4414129955298, 7945866428953600, 19467894010226044005, 62298157203907977632000, 252309651689367225339613486, 1261554846529199611110022246400, 7632433016288078444696820350362442, 54953647052313016042619300361129676800

Offset: 1

Steven Finch, May 25 2004

nonn

The unknown constant in the article "Shapes of binary trees" by S. Finch (page 3, unsolved problem) is C = 0.0196207628432398766811334785902747944894235476341... = sqrt(15)/(20*Pi^2). - Vaclav Kotesovec, Jan 19 2015

			a(2) = 2*(10-4)*(10-6)*a(1)+a(1) = 49 since a(1)=1.

S. R. Finch, Shapes of binary trees, June 24, 2004. [Cached copy, with permission of the author]
S. R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
S. Janson, The Wiener index of simply generated random trees, Random Structures Algorithms 22 (2003) 337-358.
S. Janson and P. Chassaing, The center of mass of the ISE and the Wiener index of trees, arXiv:math/0309284 [math.PR], 2003.
Jian Zhou, On a Mean Field Theory of Topological 2D Gravity, arXiv:1503.08546 [math.AG], 30 Mar 2015.

Cf. A062980.

a[1] = 1; a[n_] := a[n] = 2*(5*n - 4)*(5*n - 6)*a[n - 1] + Sum[a[k]*a[n - k], {k, 1, n - 1}]; Table[a[n], {n, 1, 10}] (* Jean-François Alcover, Jun 20 2013 *)

With a(0) = -1/2 one has for n > 0 the recurrence a(n) = 2*(5*n-4)*(5*n-6)*a(n-1)+sum(a(k)*a(n-k), k=1..n-1).

a(n) ~ sqrt(3) * 2^(n-1) * 5^(2*n-1/2) * n^(2*n-1) / (Pi * exp(2*n)). The unknown constant in theorem 4.2. in the article by S. Janson and P. Chassaing is beta = 5*sqrt(15)/(2*Pi^2) = 0.981038142161993834... . - Vaclav Kotesovec, Jan 19 2015

Name corrected by Steven Finch, Aug 12 2024

A305873 Coefficients of polynomials g_b(x) that arise in the generating function for rooted maps (A053979).

Original entry on oeis.org

1, 3, 5, 15, 65, 60, 105, 804, 1730, 1105, 945, 10824, 39110, 55645, 27120, 10395, 162357, 854250, 1987270, 2105070, 828250, 135135, 2714445, 19180410, 63897550, 108878610, 91692550, 30220800, 2027025, 50301360, 452984532, 2004435096, 4836052370, 6479714440, 4523710100, 1282031525

Offset: 1

R. J. Mathar, Jun 12 2018

The generating function of the b-th subdiagonal of A053979 is g_b(y)*(1-sqrt(1-4x))/2/(1-4x)^b, b>=0, where g_b(y) = 1 (b= 0 or 1), 3+5*y (b=2), 15+65*y+60*y^2 (b=3) etc are the coefficients in this table, and where y=(1/sqrt(1-4x)-1)/2.

The coefficient 794 cited by Walsh-Lehman (1972) has been corrected to 804.

T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I, J. Comb. Theory B 13 (1972), 192-218, eq. (5a).

Cf. A062980 (diagonal), A001147 (first column)

A305873:= proc(b,x)
    local gn1,k ;
    option remember;
    if b = 0 or b= 1 then
        return 1 ;
    else
        gn1 := procname(b-1,x) ;
        add(procname(k,x)*procname(b-k,x),k=1..b-1) ;
        gbx := %*x+(2*(b-1)*(1+2*x)+1)*gn1 ;
        expand(gbx+2*x*(x+1)*diff(gn1,x)) ;
    end if;
end proc:
for b from 1 to 8 do
    gx := A305873(b,x) ;
    for l from 0 to b-1 do
        printf("%d,",coeff(gx,x,l)) ;
    end do:
    printf("\n") ;
end do:

A305873[b_, x_] := A305873[b, x] = Module[{gn1, k, s}, If[b == 0 || b == 1, Return@1, gn1 = A305873[b - 1, x]; s = Sum[A305873[k, x]*A305873[b - k, x], {k, 1, b - 1}]; gbx = s*x + (2*(b - 1)*(1 + 2*x) + 1)*gn1; Expand[gbx + 2*x*(x + 1)*D[gn1, x]]]];
Reap[For[b = 1, b <= 8, b++, gx = A305873[b, x]; For[l = 0, l <= b - 1, l++, Sow[Coefficient[gx, x, l]]]]][[2, 1]] (* Jean-François Alcover, Nov 09 2023, after Maple program *)

A359181 Number of commutative BCK-algebras of order n up to isomorphism.

Original entry on oeis.org

1, 2, 5, 11, 28, 72, 192, 515, 1426

Offset: 2

Choiwah Chow, Dec 18 2022

a(2)-a(10) were generated using the model enumerator Mace4.

Y. H. Lin, Some properties on commutative BCK-algebras, Scientiae Mathematicae Japonicae, 55(1) (2002), 129-134.
MathStructures, Commutative BCK-algebras.

Cf. A287141, A062980, A281270.

cp's OEIS Frontend

A262301 Number of normal linear lambda terms of size n with no free variables.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A281270 a(n) is the number of closed BCK (a.k.a. affine) lambda terms of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A129114 Number of unrooted unlabeled connected triangular maps on a compact closed oriented surface with 2n faces (and thus 3n edges).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A129115 Number of unrooted unlabeled not necessarily connected triangular maps on a compact closed oriented surface with 2n faces (and thus 3n edges).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

Extensions

A172455 The case S(6,-4,-1) of the family of self-convolutive recurrences studied by Martin and Kearney.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

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