login
A123527
Triangular array T(n,k) giving number of connected graphs with n labeled nodes and k edges (n >= 1, n-1 <= k <= n(n-1)/2).
6
1, 1, 3, 1, 16, 15, 6, 1, 125, 222, 205, 120, 45, 10, 1, 1296, 3660, 5700, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 16807, 68295, 156555, 258125, 331506, 343140, 290745, 202755, 116175, 54257, 20349, 5985, 1330, 210, 21, 1, 262144, 1436568
OFFSET
1,3
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). - From N. J. A. Sloane, Apr 06 2012
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
LINKS
Seiichi Manyama, Rows n = 1..40, flattened (rows 1..14 from R. W. Robinson, rows 15..20 from Henrique G. G. Pereira)
T. Yanagita, T. Ichinomiya, Thermodynamic Characterization of Synchronization-Optimized Oscillator-Networks, arXiv preprint arXiv:1409.1979 [nlin.AO], 2014.
FORMULA
For k >= C(n-1, 2) + 1 (not smaller!), T(n,k) = C(C(n,2),k) where C(n,k) is the binomial coefficient. See A084546. - Geoffrey Critzer, Dec 08 2011
EXAMPLE
Triangle begins:
n = 1
k = 0: 1
****** total(1) = 1
n = 2
k = 1: 1
****** total(2) = 1
n = 3
k = 2: 3
k = 3: 1
****** total(3) = 4
n = 4
k = 3: 16
k = 4: 15
k = 5: 6
k = 6: 1
****** total(4) = 38
n = 5
k = 4: 125
k = 5: 222
k = 6: 205
k = 7: 120
k = 8: 45
k = 9: 10
k = 10: 1
****** total(5) = 728
MATHEMATICA
nn = 8; a = Sum[(1 + y)^Binomial[n, 2] x^n/n!, {n, 0, nn}]; f[list_] := Select[list, # > 0 &]; Flatten[Map[f, Drop[Range[0, nn]! CoefficientList[Series[Log[a], {x, 0, nn}], {x, y}], 1]]] (* Geoffrey Critzer, Dec 08 2011 *)
T[ n_, k_] := If[ n < 1, 0, Coefficient[ n! SeriesCoefficient[ Log[ Sum[ (1 + y)^Binomial[m, 2] x^m/m!, {m, 0, n}]], {x, 0, n}], y, n - 1 + k]]; (* Michael Somos, Aug 12 2017 *)
CROSSREFS
See A062734 for another version with more information. Row sums give A001187.
Sequence in context: A156653 A048159 A276640 * A288265 A096611 A176666
KEYWORD
nonn,tabf
AUTHOR
N. J. A. Sloane, Nov 13 2006
STATUS
approved