login
The OEIS is supported by the many generous donors 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). 17
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, 0, 0, 1296, 3660, 5700, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 0, 0, 0, 0, 0, 0, 16807, 68295, 156555, 258125, 331506, 343140, 290745, 202755, 116175, 54257, 20349 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,6
COMMENTS
T(n,n-1) = n^(n-2) counts free labeled trees A000272.
T(n,n) counts labeled connected unicyclic graphs A057500. - Geoffrey Critzer, Oct 07 2012
REFERENCES
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
F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, Page 29, Exercise 1.5.
LINKS
Seiichi Manyama, Table of n, a(n) for n = 1..9919 (terms 1..75 from Alex Ermolaev, terms 76..175 from Alois P. Heinz)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO], 2017; Table 58.
FORMULA
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
EXAMPLE
Triangle starts:
[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],
...
MATHEMATICA
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[ 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 *)
PROG
(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 */
CROSSREFS
Cf. A001187 (row sums), A054924 (unlabeled case), A061540 (a subdiagonal).
See A123527 for another version (without leading zeros in each row).
Sequence in context: A300812 A144209 A094544 * A336567 A361902 A205531
KEYWORD
easy,nonn,tabf
AUTHOR
Vladeta Jovovic, Jul 12 2001
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:34 EDT 2024. Contains 370951 sequences. (Running on oeis4.)