login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A062734 Triangular array T(n,k) giving number of connected graphs with n labeled nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2). 7

%I

%S 1,0,1,0,0,3,1,0,0,0,16,15,6,1,0,0,0,0,125,222,205,120,45,10,1,0,0,0,

%T 0,0,1296,3660,5700,6165,4945,2997,1365,455,105,15,1,0,0,0,0,0,0,

%U 16807,68295,156555,258125,331506,343140,290745,202755,116175,54257,20349

%N Triangular array T(n,k) giving number of connected graphs with n labeled nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2).

%C T(n,n-1) = n^(n-2) counts free labeled trees A000272.

%C T(n,n) counts labeled connected unicyclic graphs A057500. - _Geoffrey Critzer_, Oct 07 2012

%D Cowan, D. D.; Mullin, R. C.; Stanton, R. G. Counting algorithms for connected labelled graphs. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 225-236. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0414417 (54 #2519). - _N. J. A. Sloane_, Apr 06 2012

%D F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, Page 29, Exercise 1.5.

%H Seiichi Manyama, <a href="/A062734/b062734.txt">Table of n, a(n) for n = 1..9919</a> (terms 1..75 from Alex Ermolaev, terms 76..175 from Alois P. Heinz)

%H R. J. Mathar, <a href="http://arxiv.org/abs/1709.09000">Statistics on Small Graphs</a>, arXiv:1709.09000 (2017), Table 58.

%F G.f.: Sum_{n>=1, k>=0} T(n, k) * x^n/n! * y^k = log(Sum_{n>=0} (1 + y)^binomial(n, 2) * x^n/n!). - _Ralf Stephan_, Jan 18 2005

%e Triangle starts:

%e [1],

%e [0, 1],

%e [0, 0, 3, 1],

%e [0, 0, 0, 16, 15, 6, 1],

%e [0, 0, 0, 0, 125, 222, 205, 120, 45, 10, 1],

%e ...

%t nn=6;s=Sum[(1+y)^Binomial[n,2] x^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[Series[Log[ s]+1,{x,0,nn}],{x,y}]//Grid (* returns triangle indexed at n = 0, _Geoffrey Critzer_, Oct 07 2012 *)

%t T[ n_, k_] := If[ n < 0, 0, Coefficient[ n! SeriesCoefficient[ Log[ Sum[ (1 + y)^Binomial[m, 2] x^m/m!, {m, 0, n}]], {x, 0, n}], y, k]]; (* _Michael Somos_, Aug 12 2017 *)

%o (PARI) {T(n, k) = if( n<0, 0, n! * polcoeff( polcoeff( log( sum(m=0, n, (1 + y)^(m * (m-1)/2) * x^m/m!)), n), k))}; /* _Michael Somos_, Aug 12 2017 */

%Y Cf. (row sums) A001187, (unlabeled case) A054924, (a subdiagonal) A061540.

%Y See A123527 for another version (without leading zeros in each row).

%K easy,nonn,tabf

%O 1,6

%A _Vladeta Jovovic_, Jul 12 2001

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 23 22:20 EDT 2019. Contains 326254 sequences. (Running on oeis4.)