A217654 Triangular array read by rows. T(n,k) is the number of unlabeled directed graphs of n nodes that have exactly k isolated nodes.

1, 0, 1, 2, 0, 1, 13, 2, 0, 1, 202, 13, 2, 0, 1, 9390, 202, 13, 2, 0, 1, 1531336, 9390, 202, 13, 2, 0, 1, 880492496, 1531336, 9390, 202, 13, 2, 0, 1, 1792477159408, 880492496, 1531336, 9390, 202, 13, 2, 0, 1, 13026163465206704, 1792477159408, 880492496, 1531336, 9390, 202, 13, 2, 0, 1

Offset: 0

Author

Geoffrey Critzer, Oct 09 2012

Keywords

• nonn
• tabl

Comments

Row sums give A000273.

Column k = 0 is A053598.

Examples

			Triangle T(n,k) begins:
        1;
        0,    1;
        2,    0,   1;
       13,    2,   0,  1;
      202,   13,   2,  0, 1;
     9390,  202,  13,  2, 0, 1;
  1531336, 9390, 202, 13, 2, 0, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..43, flattened

Crossrefs

Cf. A000273, A053598.

Programs

Maple

b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(
      igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),
      add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
g:= proc(n) option remember; b(n$2, []) end:
T:= (n, k)-> g(n-k)-`if`(kAlois P. Heinz, Sep 04 2019

Mathematica

Needs["Combinatorica`"]; f[list_]:=Insert[Select[list,#>0&],0,-2]; nn=10; s=Sum[NumberOfDirectedGraphs[n]x^n, {n,0,nn}]; Drop[Flatten[Map[f, CoefficientList[Series[s (1-x)/(1-y x), {x,0,nn}], {x,y}]]], 1]
(* Second program: *)
b[n_, i_, l_List] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[p[[j]] - 1 + Sum[GCD[p[[k]], p[[j]]], {k, 1, j - 1}]*2, {j, 1, Length[p]}]][Join[l, Array[1&, n]]]), Sum[b[n - i*j, i - 1, Join[l, Array[i&, j]]]/j!/i^j, {j, 0, n/i}]];
g[n_] := g[n] = b[n, n, {}];
T[n_, k_] := g[n - k] - If[k < n, g[n - k - 1], 0];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 07 2019, after Alois P. Heinz *)

Formula

O.g.f.: A(x)*(1-x)/(1-y*x) where A(x) is o.g.f. for A000273.