login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A120587 Number of inequivalent (under the group of permutations and "inversion of variables") nondegenerate monotone Boolean functions of n variables. 2
1, 1, 1, 3, 11, 95 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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.

LINKS

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

EXAMPLE

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.

CROSSREFS

Sequence in context: A091547 A063854 A066384 * A086914 A123996 A201425

Adjacent sequences:  A120584 A120585 A120586 * A120588 A120589 A120590

KEYWORD

nonn,more

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 17:40 EST 2018. Contains 299584 sequences. (Running on oeis4.)