login
A275595
Triangular array read by rows: T(n,k) is the number of simple labeled graphs on n vertices, n>=1, with exactly k connected components, 1<=k<=n, such that the vertices labeled with 1,2,...,k are all in different components.
1
1, 1, 1, 4, 2, 1, 38, 10, 3, 1, 728, 100, 18, 4, 1, 26704, 1856, 192, 28, 5, 1, 1866256, 63728, 3528, 320, 40, 6, 1, 251548592, 4169200, 114792, 5912, 490, 54, 7, 1, 66296291072, 535647520, 7034832, 184576, 9200, 708, 70, 8, 1, 34496488594816, 137186152064, 858485568, 10624672, 278840, 13608, 980, 88, 9, 1
OFFSET
1,4
LINKS
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 142.
FORMULA
E.g.f. for column k (without leading 0's): (d[A(x)]/dx)^k where A(x) is the e.g.f. for A001187.
EXAMPLE
1,
1, 1,
4, 2, 1,
38, 10, 3, 1,
728, 100, 18, 4, 1,
...
T(4,3)=3. There is only one unlabeled graph with 4 vertices and exactly three components. It consists of a path of length one and two isolated vertices. This graph can be labeled so that the 1,2,3 are all in different components in 3 ways.
MATHEMATICA
nn = 10; Map[Select[#, # > 0 &] &, Transpose[Map[Take[#, nn] &, Table[Clear[g]; g[z_] := Sum[2^Binomial[n, 2] z^n/n!, {n, 0, nn + k}]; Join[Table[0, {k - 1}], Range[0, nn]! CoefficientList[Series[D[Log[g[z]], z]^k, {z, 0, nn}], z]], {k, 1, nn}]]]] //Grid
CROSSREFS
Row sums give A275597.
Cf. A001187.
Sequence in context: A136212 A136215 A136737 * A298906 A004551 A284398
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Aug 03 2016
STATUS
approved