The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A272794 The numbers of closed simply typable lambda terms of natural size n. 2
0, 0, 1, 1, 2, 5, 13, 27, 74, 198, 508, 1371, 3809, 10477, 29116, 82419, 233748, 666201, 1914668, 5528622, 16019330, 46642245, 136326126, 399652720, 1175422931, 3467251920, 10258152021 (list; graph; refs; listen; history; text; internal format)



Natural size measure lambda terms as follows: all symbols are assigned size 1, namely applications, abstractions, successor symbols in de Bruijn indices and 0 symbol in de Bruijn indices (i.e., a de Bruijn index n is assigned size n+1).

Here we count the closed simply typable terms of natural size n. "Closed" means that there is no free index (no free bound variable). "Simply typable" means that lambda terms have a simple type.

The numbers are computed as follows: all the closed terms are generated and then filtered using a type reconstruction algorithm. The values given above are the only known values of the sequence.


Table of n, a(n) for n=0..26.

Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc, A natural counting of Lambda terms, arXiv:1506.02367 [cs.LO], 2015.

Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc, A Natural Counting of Lambda Terms, SOFSEM 2016: 183-194

Maciej Bendkowski, K Grygiel, P Tarau, Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers, arXiv preprint arXiv:1612.07682, 2016


Cf. A105633, A220471, A236393, A236405.

Sequence in context: A322593 A289774 A126656 * A026522 A216378 A225690

Adjacent sequences:  A272791 A272792 A272793 * A272795 A272796 A272797




Pierre Lescanne, Jul 13 2016



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 29 14:59 EDT 2021. Contains 346346 sequences. (Running on oeis4.)