
Olivier Bodini

Danièle Gardy

Bernhard Gittenberger

Alice Jacquot
Abstract
We investigate the asymptotic number of elements of size $n$ in a particular class of closed lambdaterms (socalled $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 lambdaterms. Using elementary arguments we obtain upper and lower estimates for the number of closed lambdaterms of size $n$. Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. $BCK(p)$terms are discussed briefly.