login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001206 Number of self-dual monotone Boolean functions of n variables.
(Formerly M1267 N0486)
25
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. - Don 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.
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. 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).
LINKS
Taras Banakh, Volodymyr Gavrylkiv, Automorphism groups of superextensions of groups, arXiv:1802.05804 [math.GR], 2018.
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.
A. E. Brouwer and A. Verbeek, Counting families of mutually intersecting sets, Electronic Journal of Combinatorics, Volume 20, Issue 2 (2013), Paper #P8.
Gábor Damásdi, Stefan Felsner, António Girão, Balázs Keszegh, David Lewis, Dániel T. Nagy, Torsten Ueckerdt, On Covering Numbers, Young Diagrams, and the Local Dimension of Posets, arXiv:2001.06367 [math.CO], 2020.
Jesús A. De Loera, Serkan Hoşten, Robert Krone, Lily Silverstein, Average Behavior of Minimal Free Resolutions of Monomial Ideals, arXiv:1802.06537 [math.AC], 2018.
Serkan Hosten and Walter D. Morris, Jr., The order dimension of the complete graph, Discrete Math. 201 (1999), pp. 133-139.
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.
Bartlomiej Pawelski and Andrzej Szepietowski, Divisibility properties of Dedekind numbers, arXiv:2302.04615 [math.CO], 2023.
N. M. Rivière, Recursive formulas on free distributive lattices, J. Combinatorial Theory 5 1968 229--234. MR0231764 (38 #92).
Tom Trotter, An Application of the Erdős/Stone Theorem, Slides, Sept. 13, 2001.
FORMULA
a(n+1) = Sum_{m=0..A037952(n)} A059090(n, m).
For n > 0, a(n) = A326372(n - 1) - 1. - Gus Wiseman, Jul 03 2019
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.
From Gus Wiseman, Jul 03 2019: (Start)
The a(1) = 1 through a(4) = 12 intersecting antichains of nonempty sets (see Jovovic and Kilibarda's comment):
{} {} {} {}
{{1}} {{1}} {{1}}
{{2}} {{2}}
{{1,2}} {{3}}
{{1,2}}
{{1,3}}
{{2,3}}
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}
(End)
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
Table[Length[stableSets[Subsets[Range[n], {1, n}], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&]], {n, 0, 5}] (* Gus Wiseman, Jul 03 2019 *)
CROSSREFS
The case with empty edges allowed is A326372.
The maximal case is A007363, or A326363 with empty edges allowed.
The case with empty intersection is A326366.
The inverse binomial transform is the covering case A305844.
Sequence in context: A038054 A003180 A002080 * A144295 A119489 A353743
KEYWORD
nonn,hard,nice,more
AUTHOR
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 | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:15 EDT 2024. Contains 371265 sequences. (Running on oeis4.)