|
%I M1520 #75 Jun 09 2021 22:40:02
%S 1,2,5,18,113,1450,40069,2350602,286192513,71213783666,35883905263781,
%T 36419649682706466,74221659280476136241,303193505953871645562970,
%U 2480118046704094643352358501,40601989176407026666590990422106,1329877330167226219547875498464516481
%N 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.
%C From _Petros Hadjicostas_, Apr 09 2020: (Start)
%C Hierarchical log-linear models are by definition nonempty because they always include an "intercept" (or "overall effect").
%C 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.)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A006896/b006896.txt">Table of n, a(n) for n = 0..80</a>
%H P. De Causmaecker and S. De Wannemacker, <a href="http://ceur-ws.org/Vol-1062/proceedings-cla2013.pdf#page=69">Decomposition of Intervals in the Space of Anti-Monotonic Functions</a>, in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 57-67, Laboratory L3i, University of La Rochelle, 2013.
%H Patrick De Causmaecker and Stefan De Wannemacker, <a href="http://arxiv.org/abs/1407.4288">On the number of antichains of sets in a finite universe</a>, arXiv:1407.4288 [math.CO], 2014.
%H Niharika Gauraha, <a href="https://arxiv.org/abs/1603.04122">Graphical log-linear models: Fundamental concepts and applications</a>, arXiv:1603.04122 [stat.ME], 2016.
%H Y. Nardi and A. Rinaldo, <a href="https://projecteuclid.org/euclid.bj/1340887009">The log-linear group-lasso estimator and its asymptotic properties</a>, Bernoulli 18(3) (2012), 945-974; see footnote 1 on p. 953 and Table 2 on p. 954.
%H Gete Umbrey and Saifur Rahman, <a href="https://www.researchgate.net/profile/Gete-Umbrey/publication/349880944_Application_of_Graph_Semirings_in_Decision_Networks">Application of Graph Semirings in Decision Networks</a>, Mathematical Forum (2021) Vol. 28, 40-51.
%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.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Log-linear_analysis#Graphical_model">Log-linear analysis</a>.
%F 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).
%F a(n) = 1 + A004140(n).
%F E.g.f.: exp(x)*A(x) where A(x) is e.g.f. for A006125. - _Geoffrey Critzer_, Apr 11 2012.
%e From _Petros Hadjicostas_, Apr 09 2020: (Start)
%e 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.
%e 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.
%e 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.
%e 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)
%p 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);
%t 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 *)
%o (PARI) a(n)=sum(k=0,n,binomial(n,k)*2^((k^2-k)/2))
%Y Cf. A004140, A006897 (unlabeled case).
%K easy,nonn,nice
%O 0,2
%A _N. J. A. Sloane_, _Colin Mallows_, _Simon Plouffe_
%E Error in formula line corrected Sep 15 1997 (thanks to _R. K. Guy_ for pointing this out)
%E Name expanded by _Petros Hadjicostas_, Apr 08 2020
%E Edited by _N. J. A. Sloane_, Apr 23 2020
|
