A058876 - OEIS

%I #27 Dec 27 2021 23:45:44

%S 1,1,2,1,9,15,1,28,198,316,1,75,1610,10710,16885,1,186,10575,211820,

%T 1384335,2174586,1,441,61845,3268125,64144675,416990763,654313415,1,

%U 1016,336924,43832264,2266772550,44218682312,286992935964,450179768312

%N Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n).

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).

%D R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.

%H Andrew Howroyd, <a href="/A058876/b058876.txt">Table of n, a(n) for n = 1..1275</a> (rows 1..50)

%H R. W. Robinson, <a href="/A003024/a003024.pdf">Enumeration of acyclic digraphs</a>, Manuscript. (Annotated scanned copy)

%F Harary and Prins (following Robinson) give a recurrence.

%e Triangle begins:

%e   1;

%e   1,  2;

%e   1,  9,   15;

%e   1, 28,  198,   316;

%e   1, 75, 1610, 10710, 16885;

%e   ...

%t a[p_, k_] :=a[p, k] =If[p == k, 1, Sum[Binomial[p, k]*a[p - k, n]*(2^k - 1)^n*2^(k (p - k - n)), {n,1, p - k}]];

%t Map[Reverse, Table[Table[a[p, k], {k, 1, p}], {p, 1, 6}]] // Grid (* _Geoffrey Critzer_, Aug 29 2016 *)

%o (PARI)

%o A058876(n)={my(v=vector(n)); for(n=1, #v, v[n]=vector(n, i, if(i==n, 1, my(u=v[n-i]); sum(j=1, #u, 2^(i*(#u-j))*(2^i-1)^j*binomial(n,i)*u[j])))); v}

%o { my(T=A058876(10)); for(n=1, #T, print(Vecrev(T[n]))) } \\ _Andrew Howroyd_, Dec 27 2021

%Y Columns give A058877, A060337.

%Y Diagonals give A003025, A003026, A060335.

%Y Row sums give A003024.

%Y Cf. A122078 (unlabeled case).

%K nonn,easy,tabl

%O 1,3

%A _N. J. A. Sloane_, Jan 07 2001

%E More terms from _Vladeta Jovovic_, Apr 10 2001