A372495 Number of inequivalent unate functions of n or fewer variables.

2, 4, 10, 34, 200, 3466, 829744

Offset

0,1

Comments

A Boolean function is unate in a variable if it is either nondecreasing or nonincreasing with respect to that variable. Therefore in the circuit representation of unate functions, each variable appears either in its original form or in complemented form. Thus 𝑥⊕𝑦=(𝑥∧¬𝑦)∨(¬𝑥∧𝑦) is not a unate function.

Moreover, two Boolean functions are said to be equivalent if they are equivalent under the permutation of variables. For example, 𝑓(𝑥,𝑦)=𝑥 is equivalent to 𝑓(𝑥,𝑦)=𝑦 under the permutation of input variables.

Links

Table of n, a(n) for n=0..6.

Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.

Index entries for sequences related to Boolean functions

Example

The list of all 2-variable inequivalent unate functions f(x,y)  is 0,1,x,¬x,x∧y,¬x∧y,¬x∧¬y,x∨y,¬x∨y,¬x∨¬y. So a(2)=10.

Crossrefs

Cf. A000372, A003182, A245079.

Sequence in context: A003422 A117402 A109455 * A258948 A343158 A189591

Adjacent sequences: A372492 A372493 A372494 * A372496 A372497 A372498

Keyword

nonn,hard,more

Author

Aniruddha Biswas, May 03 2024

Status

approved