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

Comments

Row sums give A000273.

Column k = 0 is A053598.

Links

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

Formula

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

Example

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

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`(k<n, g(n-k-1), 0):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois 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 *)

Crossrefs

Cf. A000273, A053598.

Sequence in context: A367381 A322221 A328924 * A267164 A158234 A270882

Adjacent sequences: A217651 A217652 A217653 * A217655 A217656 A217657

Keyword

nonn,tabl

Author

Geoffrey Critzer, Oct 09 2012

Status

approved