|
%I #66 Nov 11 2018 09:39:42
%S 0,0,1,2,4,13,42,139,506,1915,7558,31092,132170,580466,2624545,
%T 12190623,58083923,283346273,1413449148,7200961616,37425264180,
%U 198239674888,1069228024931,5867587726222,32736878114805,185570805235978
%N Number of closed lambda-terms of size n with size 1 for the variables.
%C A lambda-term is a term which is either a variable "x" (of size 1), an application of two lambda-terms (of size 1 + the sum of the sizes of the two subterms), or a lambda binding a new variable in a term (of size 1 + the size of the subterm).
%C The size of a lambda-term t can be equivalently defined as the number of ways of selecting a subterm of t (distinguishing between different occurrences of the same subterm). For example, the 2 closed terms with three subterms are \x.\y.x (subterms \x.\y.x, \y.x, and x) and \x.\y.y (subterms \x.\y.y, \y.y, and y), while the 4 with four subterms are \x.\y.\z.x, \x.\y.\z.y, \x.\y.\z.z, and \x.x(x) (subterms \x.x(x), x(x), x[1], and x[2], distinguishing between the two occurrences of the variable x). - _Noam Zeilberger_, Nov 10 2018
%H Noam Zeilberger, <a href="/A135501/b135501.txt">Table of n, a(n) for n = 0..300</a> (terms 2-63 from Christophe Raffalli)
%H Olivier Bodini, Danièle Gardy, Bernhard Gittenberger, Zbigniew Gołębiewski, <a href="http://arxiv.org/abs/1510.01167">On the number of unary-binary tree-like structures with restrictions on the unary height</a>, arXiv:1510.01167 [math.CO], 2015, see p. 4.
%H Olivier Bodini, Paul Tarau, <a href="https://arxiv.org/abs/1709.04302">On Uniquely Closable and Uniquely Typable Skeletons of Lambda Terms</a>, arXiv:1709.04302 [cs.PL], 2017.
%H Katarzyna Grygiel and Pierre Lescanne, <a href="http://arxiv.org/abs/1210.2610">Counting and generating lambda-terms</a>, arXiv preprint arXiv:1210.2610 [cs.LO], 2012-2013.
%H Pierre Lescanne, <a href="http://arxiv.org/abs/1107.1327">On counting untyped lambda terms</a>, arXiv:1107.1327 [cs.LO], 2011-2012.
%H Paul Tarau, <a href="http://www.cse.unt.edu/~tarau/research/2015/dbt.pdf">On Type-directed Generation of Lambda Terms</a>, preprint, 2015.
%H Paul Tarau, <a href="http://www.cse.unt.edu/~tarau/research/2015/dbx.pdf">On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization</a>, 2015.
%H P. Tarau, <a href="http://arxiv.org/abs/1507.06944">A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations</a>, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.
%H Noam Zeilberger, 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.
%F f(n,0) where f(1,1) = 1; f(0,k) = 0; f(n,k) = 0 if k>2n-1; f(n,k) = f(n-1,k) + f(n-1,k+1) + sum_{p=1 to n-2} sum_{c=0 to k} sum_{l=0 to k - c} [C^c_k C^l_(k-c) f(p,l+c) f(n-p-1,k-l)], where C^p_n are binomial coefficients (the last term is for the application where "c" is the number of common variables in both subterms). f(n,k) can be computed only using f(n',k') with n' < n and k' <= k + n - n'. f(n,k) is the number of lambda terms of size n (with size 1 for the variables) having exactly k free variables.
%F T(n,0) where T(0,m) = 0; T(1,m) = m; T(n+1,m) = T(n,m+1) + sum{k=0 to n-11} [T(n-k,m) T(k,m)]. T(n,m) is the number of lambda terms of size n (with size 1 for the variables) having at most m free variables. [_Pierre Lescanne_, Nov 18 2012]
%F The ordinary generating function l(z) can be computed using a catalytic variable as l(z) = L(z,0), where L(z,f) satisfies the functional equation L(z,f) = f*z + z*L(z,f)^2 + z*L(z,f+1). See equation (2) of [Bodini et al., 2015]. - _Noam Zeilberger_, Nov 10 2018
%p T := proc(n, k) option remember; `if`(n <= 0, 0, `if`(n = 1, k,
%p T(n-1, k+1) + add(T(n-1-j, k)*T(j, k), j = 0..n-2))) end:
%p a := n -> T(n, 0): seq(a(n), n=0..25); # _Peter Luschny_, Nov 10 2018
%t T[0, _] = 0; T[1, m_] := m;
%t T[n_, m_] := T[n, m] = T[n-1, m+1] + Sum[T[n-1-k, m] T[k, m], {k, 0, n-2}];
%t a[n_] := T[n, 0]; Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Aug 06 2018, after _Pierre Lescanne_ *)
%Y Cf. A220894, A062980.
%K nonn
%O 0,4
%A Christophe Raffalli (christophe.raffalli(AT)univ-savoie.fr), Feb 09 2008
%E Two terms prepended by _Noam Zeilberger_, Nov 10 2018
|
