|
This article is cited in 1 scientific paper (total in 1 paper)
Refined Estimates of the Number of Repetition-Free Boolean Functions in the Full Binary Basis $\{\&,\vee,\oplus,-\}$
O. V. Zubkov Irkutsk State Pedagogical University
Abstract:
We consider repetition-free Boolean functions in the basis $\{\&,\vee,\oplus,-\}$, and prove a formula expressing the number of such functions of $n$ variables as a product of Fibonacci numbers. These products are estimated; as a result, we obtain asymptotic estimates for the number of repetition-free Boolean functions. These estimates involve Euler numbers of second order and can be reduced by well-known methods to the form of an exponential-power series. These estimates can be used to construct the final asymptotics of the number of repetition-free Boolean functions in the full binary basis.
Keywords:
repetition-free Boolean function, full binary basis, binary function, Fibonacci numbers, Euler numbers, index preserving structure.
Received: 26.09.2008 Revised: 22.10.2009
Citation:
O. V. Zubkov, “Refined Estimates of the Number of Repetition-Free Boolean Functions in the Full Binary Basis $\{\&,\vee,\oplus,-\}$”, Mat. Zametki, 87:5 (2010), 721–733; Math. Notes, 87:5 (2010), 687–699
Linking options:
https://www.mathnet.ru/eng/mzm8720https://doi.org/10.4213/mzm8720 https://www.mathnet.ru/eng/mzm/v87/i5/p721
|
Statistics & downloads: |
Abstract page: | 312 | Full-text PDF : | 177 | References: | 39 | First page: | 14 |
|