2013/05/03 by Olivier Bodini, Danièle Gardy, Bodini, Olivier +5
Mathematics · #03B40 #05A16 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #math.CO #math.LO #msc:03B40 #msc:05A16
paper · pdf · doi:10.48550/arxiv.1305.0640
17 pages, 5 figures
arxiv created 2013/05/03 · arxiv updated 2013/05/06
We investigate the asymptotic number of elements of size n in a particular class of closed lambda-terms (so-called BCI(p)-terms) which are related to axiom systems of combinatory logic. By deriving a differential equation for the generating function of the counting sequence we obtain a recurrence relation which can be solved asymptotically. We derive differential equations for the generating functions of the counting sequences of other more general classes of terms as well: the class of BCK(p)-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lowerestimates for the number of closed lambda-terms of size n. Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. BCK(p)-terms are discussed briefly.