A120587 Number of inequivalent (under the group of permutations and "inversion of variables") nondegenerate monotone Boolean functions of n variables.

1, 1, 1, 3, 11, 95

Offset: 0

Author

Alan Veliz-Cuba (alanavc(AT)vt.edu), Jun 16 2006

Keywords

• nonn
• more

Comments

Given f, a function of n variables, we define the "inversion of variables", i, by (i.f)(x1,...,xn)=1+f(1+x1,...,1+xn) (we can write (i.f)(x)=1+f(1+x) where the second "1" denotes (1,...,1)). It turns out that if f is monotone, then i.f is also monotone.

On the other hand, a permutation of n elements, p, acts on f by (p.f)(x)=f(p(x)). It turns out that if f is monotone, then p.f is also monotone. Then we define p.i by (p.i)(f)=p.(i.f) and i.p by (i.p)(f)=i.(p.f). If we define a.b by (a.b).f=a.(b.f) for a,b elements of G, it turns out that G={p.i.p, where p is a permutation of n elements} is a group.

In this context, f and g are equivalent if there exists b (an element of G) such that b.f=g. If we need to study monotone Boolean functions, we only need to study a "few" of them.

For example, if we want to study monotone Boolean functions of 5 variables (there are 7581 of them) we only need to study 1 of 0 variables, 1 of 1 variable, 1 of 2 variables, 3 of 3 variables, 11 of 4 variables and 95 of five variables (a total of 112 functions). Those functions "generate" all the monotone Boolean functions of 5 variables.

Examples

			a(2)=1 because f(x,y)=xy is equivalent to g(x,y)=x+y+xy and there are no more nondegenerate monotone Boolean functions of 2 variables.