|
Search: id:A114852
|
|
|
| A114852 |
|
The number of closed lambda calculus terms of size n measured in bits according to the encoding: E(lambda x. body) = 00 E(body), E(term1 term2) = 01 E(term1) E(term2), E(x) = 1^{i+1}0, where x is bound by the i-th enclosing lambda, counting from 0. |
|
+0
2
|
|
| 0, 0, 0, 0, 1, 0, 1, 1, 2, 1, 6, 5, 13, 14, 37, 44, 101, 134, 298, 431, 883, 1361, 2736, 4405, 8574, 14334, 27465, 47146, 89270, 156360, 293840, 522913, 978447, 1761907, 3288605, 5977863, 11148652, 20414058, 38071898, 70125402, 130880047
(list; graph; listen)
|
|
|
OFFSET
|
0,9
|
|
|
LINKS
|
John Tromp, John's Lambda Calculus and Combinatory Logic Playground
John Tromp, Binary Lambda Calculus and Combinatory Logic
|
|
FORMULA
|
closed k n | n<2 = 0 | otherwise = (if n-2<k then 1 else 0) + closed (k+1) (n-2) + sum [closed k i * closed k (n-2-i) | i <- [0..n-2]]
|
|
EXAMPLE
|
closed 8 = 2 because
lambda x. lambda y. lambda z. z
and
lambda x. (x x)
are all the closed lambda terms of size 8.
|
|
PROGRAM
|
The formula above is a valid Haskell program. A faster version using arrays is closeda n = a where a = array ((0, 0), (n, n)) $ [((k, i), 0) | k<-[0..n], i<-[0..1]] ++ [((k, 2+i), (if i<k then 1 else 0) + a!(if k<n then k+1 else k, i) + sum (let f i = a!(k, i) in (zipWith (*) (map f [0..i]) (map f [i, i-1..0])))) | k<-[0..n], i<-[0..n-2]]
|
|
CROSSREFS
|
Cf. A114851.
Sequence in context: A105225 A011018 A030770 this_sequence A095132 A028940 A048998
Adjacent sequences: A114849 A114850 A114851 this_sequence A114853 A114854 A114855
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
John Tromp (tromp(AT)cwi.nl), Feb 20 2006
|
|
|
Search completed in 0.002 seconds
|
