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

%I #43 Jan 05 2021 21:36:31

%S 1,3,26,367,7142,176766,5304356,186954535,7566084686,345664350778,

%T 17592776858796,986961816330662,60502424162842876,4023421969420255644,

%U 288464963899330354104,22180309834307193611287,1820641848410408158704734,158897008602951290424279330

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

%H Gheorghe Coserea, <a href="/A262301/b262301.txt">Table of n, a(n) for n = 1..100</a>

%H Paul Tarau, 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 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lambda_calculus">Lambda calculus</a>

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

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

%t terms = 18; F[_, _] = 0;

%t 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}];

%t CoefficientList[F[x, 0], x][[2 ;; terms+1]] (* _Jean-François Alcover_, Sep 02 2018, after _Gheorghe Coserea_ *)

%o (PARI)

%o F(N) = {

%o my(x='x+O('x^N), t='t, F0=x, F1=0, n=1);

%o while(n++,

%o F1 = x*t/(1-F0) + deriv(F0,t);

%o if (F1 == F0, break()); F0 = F1;);

%o F0;

%o };

%o seq(N) = Vec(subst(F(N+1), 't, 0));

%o seq(18) \\ _Gheorghe Coserea_, Apr 01 2017

%Y Column 0 of A318110.

%Y Cf. A062980, A267827.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, Sep 30 2015

%E More terms from _Gheorghe Coserea_, Apr 01 2017