|
%I M1267 N0486 #101 Oct 09 2023 01:07:22
%S 0,1,2,4,12,81,2646,1422564,229809982112,423295099074735261880
%N Number of self-dual monotone Boolean functions of n variables.
%C Sometimes called Hosten-Morris numbers (or HM numbers).
%C 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
%C Also the maximal number of generators of a neighborly monomial ideal in n variables. [Miller-Sturmfels]. - _N. J. A. Sloane_, Feb 18 2008
%C 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
%C Also the number of nondominated coteries on n members. - _Don Knuth_, Sep 01 2005
%C The number of maximal families of intersecting subsets of an n-element set. - _Bridget Tenner_, Nov 16 2006
%C Rivière gives a(n) for n <= 5. - _N. J. A. Sloane_, May 12 2012
%D Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, Third Edition, Springer-Verlag, 2004. See chapter 22.
%D V. Jovovic and G. Kilibarda, The number of n-variable Boolean functions in the Post class F(7,2), Belgrade, 2001, in preparation.
%D D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
%D 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.
%D Charles F. Mills and W. M. Mills, The calculation of λ(8), preprint, 1979. Gives a(8).
%D E. Miller and B. Sturmfels, Combinatorial Commutative Algebra, Springer, 2005.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Taras Banakh, Volodymyr Gavrylkiv, <a href="https://arxiv.org/abs/1802.05804">Automorphism groups of superextensions of groups</a>, arXiv:1802.05804 [math.GR], 2018.
%H Jan C. Bioch and Toshihide Ibaraki, <a href="http://dx.doi.org/10.1109/71.466629">Generating and approximating nondominated coteries</a>, IEEE Transactions on parallel and distributed systems 6 (1995), 905-914.
%H A. E. Brouwer and A. Verbeek, <a href="https://web.archive.org/web/20160713010641/http://oai.cwi.nl/oai/asset/7461/7461A.pdf">Counting families of mutually intersecting sets</a>, Report ZN 41, March 1972, Math. Centr., Amsterdam. Gives a(n) for n <= 7.
%H A. E. Brouwer and A. Verbeek, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p8">Counting families of mutually intersecting sets</a>, Electronic Journal of Combinatorics, Volume 20, Issue 2 (2013), Paper #P8.
%H Gábor Damásdi, Stefan Felsner, António Girão, Balázs Keszegh, David Lewis, Dániel T. Nagy, Torsten Ueckerdt, <a href="https://arxiv.org/abs/2001.06367">On Covering Numbers, Young Diagrams, and the Local Dimension of Posets</a>, arXiv:2001.06367 [math.CO], 2020.
%H Jesús A. De Loera, Serkan Hoşten, Robert Krone, Lily Silverstein, <a href="https://arxiv.org/abs/1802.06537">Average Behavior of Minimal Free Resolutions of Monomial Ideals</a>, arXiv:1802.06537 [math.AC], 2018.
%H Serkan Hosten and Walter D. Morris, Jr., <a href="http://dx.doi.org/10.1016/S0012-365X(98)00315-X">The order dimension of the complete graph</a>, Discrete Math. 201 (1999), pp. 133-139.
%H D. E. Loeb, <a href="http://www.labri.u-bordeaux.fr/~loeb/london">Challenges in playing multiplayer games</a>, in Levy and Beal, editors, Heuristic Programming in Artificial Intelligence, vol. 4, Ellis Horwood, 1994. [broken link]
%H D. E. Loeb and A. Meyerowitz, <a href="/A007007/a007007.pdf">The maximal intersecting family of sets graph</a>, in H. Barcelo and G. Kalai, editors, Proceedings of the Conference on Jerusalem Combinatorics 1993. AMS series Contemporary Mathematics, 1994.
%H Bartlomiej Pawelski and Andrzej Szepietowski, <a href="https://arxiv.org/abs/2302.04615">Divisibility properties of Dedekind numbers</a>, arXiv:2302.04615 [math.CO], 2023.
%H N. M. Rivière, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80068-7">Recursive formulas on free distributive lattices</a>, J. Combinatorial Theory 5 1968 229--234. MR0231764 (38 #92).
%H Tom Trotter, <a href="http://people.math.gatech.edu/~trotter/slides/newhak.pdf">An Application of the Erdős/Stone Theorem</a>, Slides, Sept. 13, 2001.
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F a(n+1) = Sum_{m=0..A037952(n)} A059090(n, m).
%F For n > 0, a(n) = A326372(n - 1) - 1. - _Gus Wiseman_, Jul 03 2019
%e a(2) = 1 + 1 = 2;
%e a(3) = 1 + 3 = 4;
%e a(4) = 1 + 7 + 3 + 1 = 12;
%e a(5) = 1 + 15 + 30 + 30 + 5 = 81;
%e a(6) = 1 + 31 + 195 + 605 + 780 + 543 + 300 + 135 + 45 + 10 + 1 = 2646;
%e a(7) = 1 + 63 + 1050 + 9030 + 41545 + 118629 + 233821 + 329205 + 327915 + 224280 + 100716 + 29337 + 5950 + 910 + 105 + 1 = 1422564.
%e Cf. A059090.
%e From _Gus Wiseman_, Jul 03 2019: (Start)
%e The a(1) = 1 through a(4) = 12 intersecting antichains of nonempty sets (see Jovovic and Kilibarda's comment):
%e {} {} {} {}
%e {{1}} {{1}} {{1}}
%e {{2}} {{2}}
%e {{1,2}} {{3}}
%e {{1,2}}
%e {{1,3}}
%e {{2,3}}
%e {{1,2,3}}
%e {{1,2},{1,3}}
%e {{1,2},{2,3}}
%e {{1,3},{2,3}}
%e {{1,2},{1,3},{2,3}}
%e (End)
%t 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]]]];
%t Table[Length[stableSets[Subsets[Range[n],{1,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&]],{n,0,5}] (* _Gus Wiseman_, Jul 03 2019 *)
%Y Cf. A000372, A059090.
%Y The case with empty edges allowed is A326372.
%Y The maximal case is A007363, or A326363 with empty edges allowed.
%Y The case with empty intersection is A326366.
%Y The inverse binomial transform is the covering case A305844.
%Y Cf. A006126, A014466, A051185, A326361, A326362.
%K nonn,hard,nice,more
%O 0,3
%A _N. J. A. Sloane_
%E a(8) due to C. F. Mills & W. H. Mills, 1979
%E a(8) from _Daniel E. Loeb_, Jan 04 1996
%E a(8) confirmed by _Don Knuth_, Feb 08 2008
%E a(9) from _Andries E. Brouwer_, Aug 25 2012
|
