cp's OEIS Frontend

A195691 The number of closed normal form lambda calculus terms of size n, where size(lambda x.M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda (corresponding to a binary encoding).

%I A195691 #28 May 23 2017 06:21:21
%S A195691 0,0,0,0,1,0,1,1,2,1,4,4,8,7,18,23,42,50,105,153,271,385,721,1135,
%T A195691 1992,3112,5535,9105,15916,26219,45815,77334,135029,229189,399498,
%U A195691 685710,1198828,2070207,3619677,6286268,11024475,19241836,33795365,59197968,104234931
%N A195691 The number of closed normal form lambda calculus terms of size n, where size(lambda x.M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda (corresponding to a binary encoding).
%H A195691 Wikipedia, <a href="http://en.wikipedia.org/wiki/Binary_lambda_calculus">Binary lambda calculus</a>
%H A195691 John Tromp, <a href="/A195691/a195691.hs.txt">A195691.hs</a>
%F A195691 a(n) = N(1,0,n) with
%F A195691   N(q,k,0) = N(q,k,1) = 0
%F A195691   N(q,k,n+2) = (if k>n then 1 else 0) +
%F A195691                q * N(1,k+1,n) +
%F A195691                Sum_{i=0..n} N(0,k,i) * N(1,k,n-i)
%e A195691 This sequence first differs from A114852 at n=10, where it excludes the two reducible terms (lambda x.x)(lambda x.x) and lambda x.(lambda x.x)x, so normal 10 = (closed 10)-2 = 6-2 = 4.
%t A195691 A[_, _, 0] = A[_, _, 1] = 0; A[q_, k_, n_] := A[q, k, n] = Boole[k > n-2] + q*A[1, k+1, n-2] + Sum[A[0, k, i]*A[1, k, n-i-2], {i, 0, n-2}];
%t A195691 a[n_] := A[1, 0, n];
%t A195691 Table[a[n], {n, 0, 44}] (* _Jean-François Alcover_, May 23 2017 *)
%o A195691 (Haskell)
%o A195691 a195691 = normal True 0 where
%o A195691   normal qLam k n = if n<2 then 0 else
%o A195691     (if n-2<k then 1 else 0) +
%o A195691     (if qLam then normal True (k+1) (n-2) else 0) +
%o A195691     sum [normal False k i * normal True k (n-2-i) | i <- [0..n-2]]
%o A195691 -- See link for a more efficient version.
%Y A195691 Cf. A114851, A114852.
%Y A195691 Cf. A224345 for another way of counting normal forms in lambda-calculus.
%K A195691 nonn
%O A195691 0,9
%A A195691 _John Tromp_, Sep 22 2011