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, 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

Table of n, a(n) for n=1..55.

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

Adjacent sequences: A275592 A275593 A275594 * A275596 A275597 A275598

Keyword

nonn,tabl

Author

Geoffrey Critzer, Aug 03 2016

Status

approved