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.
1, 2, 5, 18, 113, 1450, 40069, 2350602, 286192513, 71213783666, 35883905263781, 36419649682706466, 74221659280476136241, 303193505953871645562970, 2480118046704094643352358501, 40601989176407026666590990422106, 1329877330167226219547875498464516481
Offset: 0
Examples
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)
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.
Programs
-
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 *) -
PARI
a(n)=sum(k=0,n,binomial(n,k)*2^((k^2-k)/2))
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.
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
Comments