On the Number of Fanout-Free Functions and Unate Cascade Functions

In this correspondence, the number of functions and the number of equivalence classes of functions realized by fanout-free networks and cascades of AND´S, OR´S, and inverters are presented. For fanout-free functions, recursive formulas for TND(n) and φND(n), the number of n-p-n-equivalence classes of n-variable functions and p-equivalence classes of n-variable functions, respectively, are derived. For unate cascade functions, a recursive formula for ψND(n), the number of n-variable functions, and formulas for UND(n) and ψND(n), the number of n-p -equivalence classes and p-equivalence classes, respectively, are derived. Some asymptotic properties of ψND(n), UND(n), and ψND(n) are also examined and it is shown that ψND)/ψ(n)→ 1/√2, UND(n)/U(n)→ 1/2, and ψND(n)/ψ(n)→ 1/√2 as n →∞, where ψ(n) is the number of distinct unate cascade functions of up to n variables, and U(n) and ψ(n) are the number of distinct n-p-n-and p-equivalence classes of unate cascade functions of up to n variables, respectively.