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.
Citation:
O. V. Zubkov, “Asymptotics of the Number of Repetition-Free Boolean Functions in the Elementary Basis”, Mat. Zametki, 82:6 (2007), 822–828; Math. Notes, 82:6 (2007), 741–747
\Bibitem{Zub07}
\by O.~V.~Zubkov
\paper Asymptotics of the Number of Repetition-Free Boolean Functions in the Elementary Basis
\jour Mat. Zametki
\yr 2007
\vol 82
\issue 6
\pages 822--828
\mathnet{http://mi.mathnet.ru/mzm4193}
\crossref{https://doi.org/10.4213/mzm4193}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2399962}
\zmath{https://zbmath.org/?q=an:1143.05006}
\elib{https://elibrary.ru/item.asp?id=9901586}
\transl
\jour Math. Notes
\yr 2007
\vol 82
\issue 6
\pages 741--747
\crossref{https://doi.org/10.1134/S0001434607110181}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000252128700018}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-38349075347}
Linking options:
https://www.mathnet.ru/eng/mzm4193
https://doi.org/10.4213/mzm4193
https://www.mathnet.ru/eng/mzm/v82/i6/p822
This publication is cited in the following 2 articles:
O. V. Zubkov, “Refined Estimates of the Number of Repetition-Free Boolean Functions in the Full Binary Basis $\{\&,\vee,\oplus,-\}$”, Math. Notes, 87:5 (2010), 687–699
O. V. Zubkov, “Finding and estimating the number of repetition-free Boolean functions over the elementary basis in the form of a convergent series”, Discrete Math. Appl., 19:5 (2009), 505–513