Abstract:
In this paper, we obtain an asymptotic approximation of the number $K_n$ of repetition-free Boolean functions of $n$ variables in the elementary basis $\{\&,\vee,-\}$ as $n\to\infty$ with relative error $O(1/\sqrt n\,)$. As a consequence, we verify conjectures on the existence of constants $\delta$ and $\alpha$ such that
$$
K_n\sim\delta\cdot\alpha^{n-1}\cdot(2n-3)!!,
$$
and obtain these constants.
Keywords:repetition-free Boolean function, Euler number, Stirling number of the second kind, improper integral, two-pole serial set.
Fulltext:
PDF file (401 kB)
