A236405 -id:A236405 - cp's OEIS frontend

A236393 Number of typable lambda terms of size n with size 0 for the variables.

0, 0, 1, 1, 2, 2, 3, 5, 8, 13, 22, 36, 58, 103, 177, 307, 535, 949, 1645, 2936, 5207, 9330, 16613, 29921, 53588, 96808, 174443, 316267, 572092, 1040596, 1888505, 3441755, 6268500, 11449522, 20902152, 38256759, 70004696, 128336318, 235302612, 432050796, 793513690, 1459062947, 2683714350

Offset: 0

N. J. A. Sloane, Jan 27 2014

nonn

For definition see Appendix A of Grygiel and Lescanne, arXiv 2014.

Katarzyna Grygiel, Pierre Lescanne. Counting and Generating Terms in the Binary Lambda Calculus (Extended version). 2015.

Katarzyna Grygiel, Pierre Lescanne, Counting and generating lambda terms, arXiv:1210.2610 [cs.LO], 2012.
Katarzyna Grygiel, Pierre Lescanne, Counting Terms in the Binary Lambda Calculus, arXiv:1401.0379 [cs.LO], 2014.
Pierre Lescanne, An exercise on streams: convergence acceleration, arXiv preprint arXiv:1312.4917 [cs.NA], 2013.
P. Lescanne, Boltzmann samplers for random generation of lambda terms, arXiv preprint arXiv:1404.3875 [cs.DS], 2014.

Cf. A114851, A114852, A236405.

Name clarified by Pierre Lescanne, Jul 13 2016

A272794 The numbers of closed simply typable lambda terms of natural size n.

Original entry on oeis.org

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

Offset: 0

Pierre Lescanne, Jul 13 2016

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.

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.

A294450 The numbers of plain simply typable lambda terms of natural size n.

Original entry on oeis.org

0, 1, 2, 3, 8, 17, 42, 106, 287, 747, 2069, 5732, 16012, 45283, 129232, 370761, 1069972

Offset: 0

N. J. A. Sloane, Nov 22 2017

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 [cs.LO], 2016-2017.

Cf. A105633, A220471, A236393, A236405, A272794.

cp's OEIS Frontend

A236393 Number of typable lambda terms of size n with size 0 for the variables.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A272794 The numbers of closed simply typable lambda terms of natural size n.

Views

Author

Keywords

Comments

Links

Crossrefs

A294450 The numbers of plain simply typable lambda terms of natural size n.

Views

Author

Keywords

Links

Crossrefs