Enumeration of generalized BCI lambda-terms (Q396960)

Summary: We investigate the asymptotic number of elements of size \(n\) in a particular class of closed lambda-terms (so-called \(\mathrm{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 \(\mathrm{BCK}(p)\)-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lower estimates 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. \(\mathrm{BCK}(p)\)-terms are discussed briefly.