A006896 a(n) is the number of hierarchical linear models on n labeled factors allowing 2-way interactions (but no higher order interactions); or the number of simple labeled graphs with nodes chosen from an n-set. (Formerly M1520)

1, 2, 5, 18, 113, 1450, 40069, 2350602, 286192513, 71213783666, 35883905263781, 36419649682706466, 74221659280476136241, 303193505953871645562970, 2480118046704094643352358501, 40601989176407026666590990422106, 1329877330167226219547875498464516481

Offset

0,2

Comments

From Petros Hadjicostas, Apr 09 2020: (Start)

Hierarchical log-linear models are by definition nonempty because they always include an "intercept" (or "overall effect").

Note that this is different from the number of graphical hierarchical log-linear models on n labeled factors as defined in the referenced Wikipedia article about log-linear models, "A log-linear model is graphical if, whenever the model contains all two-factor terms generated by a higher-order interaction, the model also contains the higher-order interaction." See also Gauraha (2016). (End) (Comment revised by N. J. A. Sloane, Apr 23 2020.)

References

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

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..80

P. De Causmaecker and S. De Wannemacker, Decomposition of Intervals in the Space of Anti-Monotonic Functions, in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 57-67, Laboratory L3i, University of La Rochelle, 2013.

Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.

Niharika Gauraha, Graphical log-linear models: Fundamental concepts and applications, arXiv:1603.04122 [stat.ME], 2016.

Y. Nardi and A. Rinaldo, The log-linear group-lasso estimator and its asymptotic properties, Bernoulli 18(3) (2012), 945-974; see footnote 1 on p. 953 and Table 2 on p. 954.

Gete Umbrey and Saifur Rahman, Application of Graph Semirings in Decision Networks, Mathematical Forum (2021) Vol. 28, 40-51.

R. I. P. Wickramasinghe, Topics in log-linear models, Master of Science thesis in Statistics, Texas Tech University, Lubbock, TX, 2008.

Wikipedia, Log-linear analysis.

Formula

a(n) = 1 + C(n, 1) + C(n, 2)*2 + C(n, 3)*2^3 + C(n, 4)*2^6 + ... + C(n, n)*2^(n*(n-1)/2).

a(n) = 1 + A004140(n).

E.g.f.: exp(x)*A(x) where A(x) is e.g.f. for A006125. - Geoffrey Critzer, Apr 11 2012.

Example

From Petros Hadjicostas, Apr 09 2020: (Start)
For n = 2, consider the pair of nodes {X, Y}. The simple labeled graphs with nodes from this set are the empty graph G1 = [], G2 = [X], G3 = [Y], G4 = [X, Y], and G5 = [X, Y, X-Y]. Thus a(2) = 5.
For n = 3, consider the three nodes {X, Y, Z}. The simple labeled graphs with nodes from this set are G1 = [], G2 = [X], G3 = [Y], G4 = [Z], G5 = [X, Y], G6 = [X, Z], G7 = [Y, Z], G8 = [X, Y, X-Y], G9 = [X, Z, X-Z], G10 = [Y, Z, Y-Z], G11 = [X, Y, Z], G12 = [X-Y Z], G13 = [X, Y,Z, X-Z], G14 = [X, Y, Z, Y-Z ], G15 = [X, Y, Z, Y-X-Z], G16 = [X, Y, Z, X-Y-Z], G17 = [Z, Y, Z, X-Z-Y], and G18 = [X, Y, Z, triangle with nodes X, Y, Z]. Thus a(3) = 18.
In Wickramasinghe (2008), for n = 2, all A014466(2) = 5 hierarchical log-linear models on two factors X and Y, which appear on p. 18, are trivially graphical; thus a(2) = 5.
For n = 3, among the A014466(3) = 19 hierarchical log-linear models on three factors X, Y, and Z, which appear on p. 36, only Model 18 is not graphical because it contains the X-Y, Y-Z, and Z-X interactions but does not contain the 3-way X-Y-Z interaction; thus a(3) = 19 - 1 = 18. (End)

Maple

A006896 := proc(n) local k; 1+binomial(n, 1) +add(binomial(n, k)*2^(1/2*k*(k-1)), k = 2 .. n) end; seq (A006896(n), n=0..20);

Mathematica

nn=20; g=Sum[2^Binomial[n, 2]x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[Exp[x]g, {x, 0, nn}], x]  (* Geoffrey Critzer, Apr 11 2012 *)

Prog

(PARI) a(n)=sum(k=0, n, binomial(n, k)*2^((k^2-k)/2))

Crossrefs

Cf. A004140, A006897 (unlabeled case).

Sequence in context: A174122 A005805 A058338 * A125625 A281532 A097584

Adjacent sequences: A006893 A006894 A006895 * A006897 A006898 A006899

Keyword

easy,nonn,nice

Author

N. J. A. Sloane, Colin Mallows, Simon Plouffe

Extensions

Error in formula line corrected Sep 15 1997 (thanks to R. K. Guy for pointing this out)

Name expanded by Petros Hadjicostas, Apr 08 2020

Edited by N. J. A. Sloane, Apr 23 2020

Status

approved