login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006126 Number of hierarchical models on n labeled factors or variables with linear terms forced. Also number of antichain covers of a labeled n-set.
(Formerly M1954)
143

%I M1954

%S 2,1,2,9,114,6894,7785062,2414627396434,56130437209370320359966

%N Number of hierarchical models on n labeled factors or variables with linear terms forced. Also number of antichain covers of a labeled n-set.

%C An antichain cover is a cover such that no element of the cover is a subset of another element of the cover.

%C Also, the number of nondegenerate monotone Boolean functions of n variables in an n-variable Boolean algebra. - Rodrigo A. Obando (R.Obando(AT)computer.org), Jul 26 2004

%C Also, number of simplicial complexes on an n-element vertex set. - _Richard Stanley_, Feb 10 2019

%C There are two antichains of size zero, namely {} and {{}}, while there is only one simplicial complex, namely {}. The unlabeled case is A006602. The non-covering case is A000372, which is A014466 plus 1. - _Gus Wiseman_, Mar 31 2019

%C From _Petros Hadjicostas_, Apr 10 2020: (Start)

%C Hierarchical models are always nonempty because they always include an intercept (or overall effect).

%C The total number of log-linear hierarchical models on n labeled factors (categorical variables) with no forcing of terms is given by A000372(n) - 1 (Dedekind numbers minus 1).

%C Hierarchical log-linear models for analyzing contingency tables are defined in the classic book by Bishop, Fienberg, and Holland (1975). (End)

%D Y. M. M. Bishop, S. E. Fienberg and P. W. Holland, Discrete Multivariate Analysis. MIT Press, 1975, p. 34. [In part (e), the Hierarchy Principle for log-linear models is defined. It essentially says that if a higher-order parameter term is included in the log-linear model, then all the lower-order parameter terms should also be included. - _Petros Hadjicostas_, Apr 08 2020]

%D V. Jovovic and G. Kilibarda, On enumeration of the class of all monotone Boolean functions, in preparation.

%D C. L. Mallows, personal communication.

%D A. A. Mcintosh, personal communication.

%D R. A. Obando, On the number of nondegenerate monotone boolean functions of n variables, In Preparation.

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

%H R. Baumann and H. Strass, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.719.7011">On the number of bipolar Boolean functions</a>, 2014, preprint.

%H R. Baumann and H. Strass, <a href="https://doi.org/10.1093/logcom/exx025">On the number of bipolar Boolean functions</a>, Journal of Logic and Computation, 27(8) (2017), 2431-2449.

%H Florian Bridoux, Amélia Durbec, Kévin Perrot, and Adrien Richard, <a href="https://arxiv.org/abs/2012.02513">Complexity of fixed point counting problems in Boolean Networks</a>, arXiv:2012.02513 [math.CO], 2020.

%H Florian Bridoux, Nicolas Durbec, Kevin Perrot, and Adrien Richard, <a href="https://doi.org/10.1007/978-3-030-22996-2_12">Complexity of Maximum Fixed Point Problem in Boolean Networks</a>, Conference on Computability in Europe (CiE 2019) Computing with Foresight and Industry (Lecture Notes in Computer Science book series, Vol. 11558), Springer, Cham, 132-143.

%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath515.htm">Dedekind's problem</a>

%H Patrick De Causmaecker and Stefan De Wannemacker, <a href="https://arxiv.org/abs/1407.4288">On the number of antichains of sets in a finite universe</a>, arXiv:1407.4288 [math.CO], 2014.

%H V. Jovovic and G. Kilibarda, <a href="http://mi.mathnet.ru/eng/dm398">On the number of Boolean functions in the Post classes F^{mu}_8</a>, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).

%H C. L. Mallows, <a href="/A000372/a000372_5.pdf">Emails to N. J. A. Sloane, Jun-Jul 1991</a>

%H C. L. Mallows & N. J. A. Sloane, <a href="/A006123/a006123.pdf">Emails, May 1991</a>

%H C. L. Mallows & N. J. A. Sloane, <a href="/A006123/a006123_1.pdf">Emails, Jun. 1991</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Antichain.html">Antichain</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Cover.html">Cover</a>.

%H R. I. P. Wickramasinghe, <a href="https://ttu-ir.tdl.org/handle/2346/20089">Topics in log-linear models</a>, Master of Science thesis in Statistics, Texas Tech University, Lubbock, TX, 2008. [From the A000372(2) - 1 = 4 hierarchical log-linear models on two factors X and Y, on p. 18 of his thesis, only Models 11 and 15 force all the linear terms (i.e., a(2) = 2). From the A000372(3) - 1 = 19 hierarchical log-linear models on three factors X, Y, and Z, on p. 36 of his thesis, only Models 11-19 force all the linear terms (i.e., a(3) = 9). - _Petros Hadjicostas_, Apr 08 2020]

%H D. H. Wiedemann, <a href="/A000372/a000372.pdf">Letter to N. J. A. Sloane, Nov 03, 1990</a>

%H D. H. Wiedermann, <a href="/A006126/a006126.pdf">Email to N. J. A. Sloane, May 28 1991</a>

%H Gus Wiseman, <a href="/A048143/a048143_4.txt">Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons</a>.

%F a(n) = Sum_{k = 1..C(n, floor(n/2))} b(k, n), where b(k, n) is the number of k-antichain covers of a labeled n-set.

%F Inverse binomial transform of A000372. - _Gus Wiseman_, Feb 24 2019

%e a(5) = 1 + 90 + 790 + 1895 + 2116 + 1375 + 490 + 115 + 20 + 2 = 6894.

%e There are 9 antichain covers of a labeled 3-set: {{1,2,3}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}, {{1,2},{1,3}}, {{1,2},{2,3}}, {{1,3},{2,3}}, {{1},{2},{3}}, {{1,2},{1,3},{2,3}}.

%e From _Gus Wiseman_, Feb 23 2019: (Start)

%e The a(0) = 2 through a(3) = 9 antichains:

%e {} {{1}} {{12}} {{123}}

%e {{}} {{1}{2}} {{1}{23}}

%e {{2}{13}}

%e {{3}{12}}

%e {{12}{13}}

%e {{12}{23}}

%e {{13}{23}}

%e {{1}{2}{3}}

%e {{12}{13}{23}}

%e (End)

%t nn=4;

%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[Select[stableSets[Subsets[Range[n]],SubsetQ],Union@@#==Range[n]&]],{n,0,nn}] (* _Gus Wiseman_, Feb 23 2019 *)

%t A000372 = Cases[Import["https://oeis.org/A000372/b000372.txt", "Table"], {_, _}][[All, 2]];

%t lg = Length[A000372];

%t a372[n_] := If[0 <= n <= lg-1, A000372[[n+1]], 0];

%t a[n_] := Sum[(-1)^(n-k+1) Binomial[n, k-1] a372[k-1], {k, 0, lg}];

%t a /@ Range[0, lg-1] (* _Jean-François Alcover_, Jan 07 2020 *)

%Y Cf. A000372, A056046-A056049, A056052, A056101, A056104, A051112-A051118.

%Y Cf. A006602, A014466, A261005, A293606, A293993, A305000, A305844, A306550, A307249, A317674, A319721, A320449.

%K nonn,nice,hard,more

%O 0,1

%A _N. J. A. Sloane_

%E Last 3 terms from Michael Bulmer (mrb(AT)maths.uq.edu.au)

%E Antichain interpretation from _Vladeta Jovovic_ and Goran Kilibarda, Jul 31 2000

%E a(0) = 2 added by _Gus Wiseman_, Feb 23 2019

%E Name edited by _Petros Hadjicostas_, Apr 08 2020

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 19 07:25 EDT 2021. Contains 343107 sequences. (Running on oeis4.)