

A006126


Number of hierarchical models on n labeled factors or variables with linear terms forced. Also number of antichain covers of a labeled nset.
(Formerly M1954)


161




OFFSET

0,1


COMMENTS

An antichain cover is a cover such that no element of the cover is a subset of another element of the cover.
Also, the number of nondegenerate monotone Boolean functions of n variables in an nvariable Boolean algebra.  Rodrigo A. Obando (R.Obando(AT)computer.org), Jul 26 2004
Also, number of simplicial complexes on an nelement vertex set.  Richard Stanley, Feb 10 2019
There are two antichains of size zero, namely {} and {{}}, while there is only one simplicial complex, namely {}. The unlabeled case is A006602. The noncovering case is A000372, which is A014466 plus 1.  Gus Wiseman, Mar 31 2019
Hierarchical models are always nonempty because they always include an intercept (or overall effect).
The total number of loglinear hierarchical models on n labeled factors (categorical variables) with no forcing of terms is given by A000372(n)  1 (Dedekind numbers minus 1).
Hierarchical loglinear models for analyzing contingency tables are defined in the classic book by Bishop, Fienberg, and Holland (1975). (End)


REFERENCES

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 loglinear models is defined. It essentially says that if a higherorder parameter term is included in the loglinear model, then all the lowerorder parameter terms should also be included.  Petros Hadjicostas, Apr 08 2020]
V. Jovovic and G. Kilibarda, On enumeration of the class of all monotone Boolean functions, in preparation.
C. L. Mallows, personal communication.
A. A. Mcintosh, personal communication.
R. A. Obando, On the number of nondegenerate monotone boolean functions of n variables, In Preparation.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Eric Weisstein's World of Mathematics, Antichain.
Eric Weisstein's World of Mathematics, Cover.
R. I. P. Wickramasinghe, Topics in loglinear models, Master of Science thesis in Statistics, Texas Tech University, Lubbock, TX, 2008. [From the A000372(2)  1 = 4 hierarchical loglinear 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 loglinear models on three factors X, Y, and Z, on p. 36 of his thesis, only Models 1119 force all the linear terms (i.e., a(3) = 9).  Petros Hadjicostas, Apr 08 2020]


FORMULA

a(n) = Sum_{k = 1..C(n, floor(n/2))} b(k, n), where b(k, n) is the number of kantichain covers of a labeled nset.


EXAMPLE

a(5) = 1 + 90 + 790 + 1895 + 2116 + 1375 + 490 + 115 + 20 + 2 = 6894.
There are 9 antichain covers of a labeled 3set: {{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}}.
The a(0) = 2 through a(3) = 9 antichains:
{} {{1}} {{12}} {{123}}
{{}} {{1}{2}} {{1}{23}}
{{2}{13}}
{{3}{12}}
{{12}{13}}
{{12}{23}}
{{13}{23}}
{{1}{2}{3}}
{{12}{13}{23}}
(End)


MATHEMATICA

nn=4;
stableSets[u_, Q_]:=If[Length[u]===0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r===wQ[r, w]Q[w, r]], Q]]]];
Table[Length[Select[stableSets[Subsets[Range[n]], SubsetQ], Union@@#==Range[n]&]], {n, 0, nn}] (* Gus Wiseman, Feb 23 2019 *)
A000372 = Cases[Import["https://oeis.org/A000372/b000372.txt", "Table"], {_, _}][[All, 2]];
a372[n_] := If[0 <= n <= lg1, A000372[[n+1]], 0];
a[n_] := Sum[(1)^(nk+1) Binomial[n, k1] a372[k1], {k, 0, lg}];


CROSSREFS

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


KEYWORD

nonn,nice,hard,more


AUTHOR



EXTENSIONS

Last 3 terms from Michael Bulmer (mrb(AT)maths.uq.edu.au)
Antichain interpretation from Vladeta Jovovic and Goran Kilibarda, Jul 31 2000


STATUS

approved



