Search: id:A114851
Results 1-1 of 1 results found.

%I A114851
%S A114851 0,0,1,1,2,2,4,5,10,14,27,41,78,126,237,399,745,1292,2404,4259,7915,
%T A114851 14242,26477,48197,89721,164766,307294,568191,1061969,1974266,3698247,
%U A114851 6905523,12964449
%N A114851 The number of "de Bruijn"-indexed lambda calculus terms of size n measured 
               in bits according to the encoding: E(lambda body) = 00 E(body), E(term1 
               term2) = 01 E(term1) E(term2), E(i) = 1^{i+1}0.
%H A114851 John Tromp, <a href="http://www.cwi.nl/~tromp/cl/cl.html">John's Lambda 
               Calculus and Combinatory Logic Playground</a>
%H A114851 John Tromp, <a href="http://www.cwi.nl/~tromp/cl/LC.pdf">Binary Lambda 
               Calculus and Combinatory Logic</a>
%F A114851 open n | n<2 = 0 | otherwise = 1 + open (n-2) + sum [open i * open (n-2-i) 
               | i <- [0..n-2]]
%e A114851 open 4 = 2 because
%e A114851 lambda 0
%e A114851 and
%e A114851 2
%e A114851 are all the de Bruijn indexed lambda terms of size 4.
%o A114851 The formula above is a valid Haskell program. A faster version using 
               arrays is opena n = a where a = array (0,n-1) $ (0,0):(1,0):[(2+i, 
               1 + a!i + sum (zipWith (*) (map (a!) [0..i]) (map (a!) [i,i-1..0]))) 
               | i<-[0..n-3] ]
%Y A114851 Cf. A114852.
%Y A114851 Sequence in context: A127712 A032090 A000014 this_sequence A099364 A125951 
               A054538
%Y A114851 Adjacent sequences: A114848 A114849 A114850 this_sequence A114852 A114853 
               A114854
%K A114851 nonn
%O A114851 0,5
%A A114851 John Tromp (tromp(AT)cwi.nl), Feb 20 2006

Search completed in 0.001 seconds