login
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

%I #19 Aug 04 2016 09:47:30

%S 1,1,1,4,2,1,38,10,3,1,728,100,18,4,1,26704,1856,192,28,5,1,1866256,

%T 63728,3528,320,40,6,1,251548592,4169200,114792,5912,490,54,7,1,

%U 66296291072,535647520,7034832,184576,9200,708,70,8,1,34496488594816,137186152064,858485568,10624672,278840,13608,980,88,9,1

%N 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.

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge Univ. Press, 2009, page 142.

%F 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.

%e 1,

%e 1, 1,

%e 4, 2, 1,

%e 38, 10, 3, 1,

%e 728, 100, 18, 4, 1,

%e ...

%e 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.

%t 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

%Y Row sums give A275597.

%Y Cf. A001187.

%K nonn,tabl

%O 1,4

%A _Geoffrey Critzer_, Aug 03 2016