The asymptotic number of $BCK(p)$-terms
Source: arxiv.org/abs/2611.16554
A $BCK(p)$-term is a closed lambda-term in which each abstraction binds at most $p$ variables; for $p=1$ these terms are related to the axiom system BCK of combinatory logic. We determine the number of $BCK(p)$-terms of size $n$, up to a constant multiplicative factor, for every $p\ge2$. For $p=2$ the result is fully explicit: \[ f\_n\sim A\,n^{2n/5}2^{n/5}e^{-2n/5}n^{-3/5}e^{P(n^{1/5})}, \] where $P$ is an explicit polynomial of degree $4$. In general the asymptotic formula involves $n^{pn/(2p+1)}$ and an exponential of a polynomial in $n^{1/(2p+1)}$. The proof combines a linearization of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.16554
curl -X POST /api/v1/records/arxiv/2611.16554/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.16554/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'