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,2

Links

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

Formula

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

Example

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

Mathematica

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

Prog

(PARI)
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

Crossrefs

Column 0 of A318110.

Cf. A062980, A267827.

Sequence in context: A328269 A136046 A206404 * A368033 A317654 A143155

Adjacent sequences: A262298 A262299 A262300 * A262302 A262303 A262304

Keyword

nonn

Author

N. J. A. Sloane, Sep 30 2015

Extensions

More terms from Gheorghe Coserea, Apr 01 2017

Status

approved