cp's OEIS Frontend

A054923 Triangle read by rows: number of connected graphs with k >= 0 edges and n nodes (1<=n<=k+1).

%I A054923 #36 Mar 23 2023 23:08:57
%S A054923 1,0,1,0,0,1,0,0,1,2,0,0,0,2,3,0,0,0,1,5,6,0,0,0,1,5,13,11,0,0,0,0,4,
%T A054923 19,33,23,0,0,0,0,2,22,67,89,47,0,0,0,0,1,20,107,236,240,106,0,0,0,0,
%U A054923 1,14,132,486,797,657,235,0,0,0,0,0,9,138,814,2075,2678,1806,551,0,0,0,0,0,5,126,1169,4495,8548,8833,5026,1301
%N A054923 Triangle read by rows: number of connected graphs with k >= 0 edges and n nodes (1<=n<=k+1).
%C A054923 The diagonal n = k+1 is A000055(n). - _Jonathan Vos Post_, Aug 10 2008
%D A054923 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 93, Table 4.2.2; p. 241, Table A2.
%H A054923 Andrew Howroyd, <a href="/A054923/b054923.txt">Table of n, a(n) for n = 0..1325</a>
%H A054923 G. A. Baker et al., <a href="http://dx.doi.org/10.1103/PhysRev.164.800">High-temperature expansions for the spin-1/2 Heisenberg model</a>, Phys. Rev., 164 (1967), 800-817.
%H A054923 R. J. Mathar, <a href="http://arxiv.org/abs/1709.09000">Statistics on Small Graphs</a>, arXiv:1709.09000  [math.CO] (2017), Table 57.
%H A054923 Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/graphs/">Small graphs</a>
%H A054923 Gus Wiseman, <a href="/A054923/a054923.png">Non-isomorphic representatives of the 12 connected graphs counted in row 5.</a>
%e A054923 Triangle begins:
%e A054923   1;
%e A054923   0, 1;
%e A054923   0, 0, 1;
%e A054923   0, 0, 1, 2;
%e A054923   0, 0, 0, 2, 3;
%e A054923   0, 0, 0, 1, 5   6;
%e A054923   0, 0, 0, 1, 5, 13,  11;
%e A054923   0, 0, 0, 0, 4, 19,  33,  23;
%e A054923   0, 0, 0, 0, 2, 22,  67,  89,  47;
%e A054923   0, 0, 0, 0, 1, 20, 107, 236, 240, 106;
%e A054923   ... (so with 5 edges there's 1 graph with 4 nodes, 5 with 5 nodes and 6 with 6 nodes). [Typo corrected by Anders Haglund, Jul 08 2008]
%o A054923 (PARI)
%o A054923 InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i), 1))}
%o A054923 permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
%o A054923 edges(v,t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i],v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
%o A054923 G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p,i->1+x^i)); s/n!}
%o A054923 T(n)={Mat([Col(p+O(y^n), -n) | p<-InvEulerMT(vector(n, k, G(k, y + O(y^n))))])}
%o A054923 {my(A=T(10)); for(n=1, #A, print(A[n,1..n]))} \\ _Andrew Howroyd_, Oct 23 2019
%Y A054923 Main diagonal is A000055.
%Y A054923 Subsequent diagonals give the number of connected unlabeled graphs with n nodes and n+k edges for k=0..2: A001429, A001435, A001436.
%Y A054923 Cf. A002905 (row sums), A001349 (column sums), A008406, A046751 (transpose), A054924 (transpose), A046742 (w/o left column), A343088 (labeled).
%Y A054923 Cf. A000664, A007718, A050535, A054923, A191646, A191970, A317672, A322114, A322151.
%K A054923 nonn,easy,nice,tabl
%O A054923 0,10
%A A054923 _N. J. A. Sloane_
%E A054923 a(83)-a(89) corrected by _Andrew Howroyd_, Oct 24 2019