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

%I #24 Dec 07 2019 12:06:13

%S 1,0,1,2,0,1,13,2,0,1,202,13,2,0,1,9390,202,13,2,0,1,1531336,9390,202,

%T 13,2,0,1,880492496,1531336,9390,202,13,2,0,1,1792477159408,880492496,

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

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

%C Row sums give A000273.

%C Column k = 0 is A053598.

%H Alois P. Heinz, <a href="/A217654/b217654.txt">Rows n = 0..43, flattened</a>

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

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 2, 0, 1;

%e 13, 2, 0, 1;

%e 202, 13, 2, 0, 1;

%e 9390, 202, 13, 2, 0, 1;

%e 1531336, 9390, 202, 13, 2, 0, 1;

%e ...

%p b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(

%p igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),

%p add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))

%p end:

%p g:= proc(n) option remember; b(n$2, []) end:

%p T:= (n, k)-> g(n-k)-`if`(k<n, g(n-k-1), 0):

%p seq(seq(T(n, k), k=0..n), n=0..10); # _Alois P. Heinz_, Sep 04 2019

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

%t (* Second program: *)

%t 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}]];

%t g[n_] := g[n] = b[n, n, {}];

%t T[n_, k_] := g[n - k] - If[k < n, g[n - k - 1], 0];

%t Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Dec 07 2019, after _Alois P. Heinz_ *)

%Y Cf. A000273, A053598.

%K nonn,tabl

%O 0,4

%A _Geoffrey Critzer_, Oct 09 2012