id:A114851 - OEIS Search Results

Search: id:A114851

Displaying 1-1 of 1 results found.

page 1

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.

+0
2

0, 0, 1, 1, 2, 2, 4, 5, 10, 14, 27, 41, 78, 126, 237, 399, 745, 1292, 2404, 4259, 7915, 14242, 26477, 48197, 89721, 164766, 307294, 568191, 1061969, 1974266, 3698247, 6905523, 12964449 (list; graph; listen)

	OFFSET	`0,5`
	LINKS	`John Tromp, John's Lambda Calculus and Combinatory Logic Playground` `John Tromp, Binary Lambda Calculus and Combinatory Logic`
	FORMULA	`open n \| n<2 = 0 \| otherwise = 1 + open (n-2) + sum [open i * open (n-2-i) \| i <- [0..n-2]]`
	EXAMPLE	`open 4 = 2 because` `lambda 0` `and` `2` `are all the de Bruijn indexed lambda terms of size 4.`
	PROGRAM	`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] ]`
	CROSSREFS	`Cf. A114852.` `Sequence in context: A127712 A032090 A000014 this_sequence A099364 A125951 A054538` `Adjacent sequences: A114848 A114849 A114850 this_sequence A114852 A114853 A114854`
	KEYWORD	`nonn`
	AUTHOR	`John Tromp (tromp(AT)cwi.nl), Feb 20 2006`

page 1

Search completed in 0.002 seconds

Last modified December 15 00:47 EST 2009. Contains 170825 sequences.

AT&T Labs Research