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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001206 Number of self-dual monotone Boolean functions of n variables.
(Formerly M1267 N0486)
9
0, 1, 2, 4, 12, 81, 2646, 1422564, 229809982112, 423295099074735261880 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Sometimes called Hosten-Morris numbers (or HM numbers).

Also the number of simplicial complexes on the set {1, ..., n-1} such that no pair of faces covers all of {1, ..., n-1}. [Miller-Sturmfels]. - N. J. A. Sloane, Feb 18 2008

Also the maximal number of generators of a neighborly monomial ideal in n variables. [Miller-Sturmfels]. - N. J. A. Sloane, Feb 18 2008

Also the number of intersecting antichains on a labeled (n-1)-set or (n-1)-variable Boolean functions in the Post class F(7,2). Cf. A059090. - Vladeta Jovovic, Goran Kilibarda, Dec 28 2000

Also the number of nondominated coteries on n members. - D. E. Knuth Sep 01 2005

The number of maximal families of intersecting subsets of an n element set. - Bridget Tenner, Nov 16 2006

Rivière gives a(n) for n <= 5. - N. J. A. Sloane, May 12 2012

REFERENCES

Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, Third Edition, Springer-Verlag, 2004. See chapter 22.

Jan C. Bioch and Toshihide Ibaraki, Generating and approximating nondominated coteries, IEEE Transactions on parallel and distributed systems, 6 (1995), 905-914.

A. E. Brouwer and A. Verbeek, Counting families of mutually intersecting sets, Report ZN 41, March 1972, Math. Centr., Amsterdam. Gives a(n) for n <= 7.

Serkan Hosten and Walter D. Morris, Jr., The order dimension of the complete graph, Discrete Math. 201 (1999), pp. 133-139.

V. Jovovic and G. Kilibarda, The number of n-variable Boolean functions in the Post class F(7,2), Belgrade, 2001, in preparation.

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.

W. F. Lunnon, The IU function: the size of a free distributive lattice, pp. 173-181 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.

Charles F. Mills and W. M. Mills, The calculation of λ(8), preprint, 1979. Gives a(8).

E. Miller and B. Sturmfels, Combinatorial Commutative Algebra, Springer, 2005.

N. M. Rivière, Recursive formulas on free distributive lattices. J. Combinatorial Theory 5 1968 229--234. MR0231764 (38 #92).

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Tom Trotter, An Application of the Erdos/Stone Theorem, Sept. 13, 2001; http://people.math.gatech.edu/~trotter/slides/newhak.pdf

LINKS

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

D. E. Loeb, Challenges in playing multiplayer games, in Levy and Beal, editors, Heuristic Programming in Artificial Intelligence, vol. 4, Ellis Horwood, 1994. [broken link]

D. E. Loeb and A. Meyerowitz, The maximal intersecting family of sets graph, in H. Barcelo and G. Kalai, editors, Proceedings of the Conference on Jerusalem Combinatorics 1993. AMS series Contemporary Mathematics, 1994.

Index entries for sequences related to Boolean functions

FORMULA

a(n+1)=Sum_{m=0..A037952(n)} A059090(n, m).

EXAMPLE

a(2) = 1 + 1 = 2;

a(3) = 1 + 3 = 4;

a(4) = 1 + 7 + 3 + 1 = 12;

a(5) = 1 + 15 + 30 + 30 + 5 = 81;

a(6) = 1 + 31 + 195 + 605 + 780 + 543 + 300 + 135 + 45 + 10 + 1 = 2646;

a(7) = 1 + 63 + 1050 + 9030 + 41545 + 118629 + 233821 + 329205 + 327915 + 224280 + 100716 + 29337 + 5950 + 910 + 105 + 1 = 1422564.

Cf. A059090.

CROSSREFS

Cf. A059090, A000372.

Sequence in context: A038054 A003180 A002080 * A144295 A119489 A217757

Adjacent sequences:  A001203 A001204 A001205 * A001207 A001208 A001209

KEYWORD

nonn,hard,nice,more

AUTHOR

N. J. A. Sloane.

EXTENSIONS

a(8) due to C. F. Mills & W. H. Mills, 1979

a(8) from Daniel E. Loeb, Jan 04 1996

a(8) confirmed by Don Knuth, Feb 08 2008

a(9) from Andries E. Brouwer, Aug 25 2012

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified November 23 16:14 EST 2014. Contains 249851 sequences.