cp's OEIS Frontend

A058876 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).

%I A058876 #27 Dec 27 2021 23:45:44
%S A058876 1,1,2,1,9,15,1,28,198,316,1,75,1610,10710,16885,1,186,10575,211820,
%T A058876 1384335,2174586,1,441,61845,3268125,64144675,416990763,654313415,1,
%U A058876 1016,336924,43832264,2266772550,44218682312,286992935964,450179768312
%N A058876 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 A058876 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
%D A058876 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 A058876 Andrew Howroyd, <a href="/A058876/b058876.txt">Table of n, a(n) for n = 1..1275</a> (rows 1..50)
%H A058876 R. W. Robinson, <a href="/A003024/a003024.pdf">Enumeration of acyclic digraphs</a>, Manuscript. (Annotated scanned copy)
%F A058876 Harary and Prins (following Robinson) give a recurrence.
%e A058876 Triangle begins:
%e A058876   1;
%e A058876   1,  2;
%e A058876   1,  9,   15;
%e A058876   1, 28,  198,   316;
%e A058876   1, 75, 1610, 10710, 16885;
%e A058876   ...
%t A058876 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 A058876 Map[Reverse, Table[Table[a[p, k], {k, 1, p}], {p, 1, 6}]] // Grid (* _Geoffrey Critzer_, Aug 29 2016 *)
%o A058876 (PARI)
%o A058876 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 A058876 { my(T=A058876(10)); for(n=1, #T, print(Vecrev(T[n]))) } \\ _Andrew Howroyd_, Dec 27 2021
%Y A058876 Columns give A058877, A060337.
%Y A058876 Diagonals give A003025, A003026, A060335.
%Y A058876 Row sums give A003024.
%Y A058876 Cf. A122078 (unlabeled case).
%K A058876 nonn,easy,tabl
%O A058876 1,3
%A A058876 _N. J. A. Sloane_, Jan 07 2001
%E A058876 More terms from _Vladeta Jovovic_, Apr 10 2001