|
This article is cited in 2 scientific papers (total in 2 papers)
Asymptotics of the Number of Repetition-Free Boolean Functions in the Elementary Basis
O. V. Zubkov Irkutsk State Pedagogical University
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.
Received: 13.05.2006 Revised: 29.01.2007
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
Linking options:
https://www.mathnet.ru/eng/mzm4193https://doi.org/10.4213/mzm4193 https://www.mathnet.ru/eng/mzm/v82/i6/p822
|
Statistics & downloads: |
Abstract page: | 423 | Full-text PDF : | 193 | References: | 64 | First page: | 4 |
|