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).

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

Adjacent sequences: A123524 A123525 A123526 * A123528 A123529 A123530

Keyword

nonn,tabf

Author

N. J. A. Sloane, Nov 13 2006

Status

approved