cp's OEIS Frontend

A081064 Irregular array, read by rows: T(n,k) is the number of labeled acyclic digraphs with n nodes and k arcs (n >= 0, 0 <= k <= n*(n-1)/2).

%I A081064 #64 Mar 16 2023 04:50:46
%S A081064 1,1,1,2,1,6,12,6,1,12,60,152,186,108,24,1,20,180,940,3050,6180,7960,
%T A081064 6540,3330,960,120,1,30,420,3600,20790,83952,240480,496680,750810,
%U A081064 838130,691020,416160,178230,51480,9000,720,1,42,840,10570,93030,601944
%N A081064 Irregular array, read by rows: T(n,k) is the number of labeled acyclic digraphs with n nodes and k arcs (n >= 0, 0 <= k <= n*(n-1)/2).
%H A081064 Andrew Howroyd, <a href="/A081064/b081064.txt">Table of n, a(n) for n = 0..1350</a> (rows 0..20)
%H A081064 E. de Panafieu and S. Dovgal, <a href="https://arxiv.org/abs/1903.09454">Symbolic method and directed graph enumeration</a>, arXiv:1903.09454 [math.CO], 2019.
%H A081064 R. W. Robinson, <a href="http://cobweb.cs.uga.edu/~rwr/publications/components.pdf">Counting digraphs with restrictions on the strong components</a>, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
%H A081064 V. I. Rodionov, <a href="https://doi.org/10.1016/0012-365X(92)90155-9">On the number of labeled acyclic digraphs</a>, Discr. Math. 105 (1-3) (1992), 319-321.
%F A081064 1 = 1*exp(-x) + 1*exp(-(1+y)*x)*x/1! + (2*y+1)*exp(-(1+y)^2*x)*x^2/2! + (6*y^3 + 12*y^2 + 6*y + 1)*exp(-(1+y)^3*x)*x^3/3! + (24*y^6 + 108*y^5 + 186*y^4 + 152*y^3 + 60*y^2 + 12*y + 1)*exp(-(1+y)^4*x)*x^4/4! + (120*y^10 + 960*y^9 + 3330*y^8 + 6540*y^7 + 7960*y^6 + 6180*y^5 + 3050*y^4 + 940*y^3 + 180*y^2 + 20*y + 1)*exp(-(1+y)^5*x)*x^5/5! + ... - _Vladeta Jovovic_, Jun 07 2005
%F A081064 We explain _Vladeta Jovovic_'s functional equation above. If F_n(y) = Sum_{k = 0..n*(n-1)/2) T(n,k) * y^k for n >= 0, then Sum_{n >= 0} F_n(y) * exp(-(1 + y)^n * x) * x^n/n! = 1. - _Petros Hadjicostas_, Apr 11 2020
%F A081064 From _Petros Hadjicostas_, Apr 10 2020: (Start)
%F A081064 If A_n(x) = Sum_{k >= 0} T(n,k)*x^k (with T(n,k) = 0 for k > n*(n-1)/2)), then Sum_{m=1..n} (-1)^(m-1) * binomial(n,m) * (1 + x)^(m*(n-m)) * A_m(x) = 1.
%F A081064 T(n,0) = 1, T(n,1) = n*(n-1), T(n,2) = 12*binomial(n+1,4), and T(n,3) = binomial(n,3)*(n^3 - 5*n - 6).
%F A081064 Also, T(n, n*(n-1)/2 - 1) = A055533(n) = n!*(n-1)^2/2 for n > 1. (End)
%e A081064 Array T(n,k) (with n >= 0 and 0 <= k <= n*(n-1)/2) begins as follows:
%e A081064   1;
%e A081064   1;
%e A081064   1,  2;
%e A081064   1,  6,  12,   6;
%e A081064   1, 12,  60, 152,  186,  108,   24;
%e A081064   1, 20, 180, 940, 3050, 6180, 7960, 6540, 3330, 960, 120;
%e A081064   ...
%e A081064 From _Petros Hadjicostas_, Apr 10 2020: (Start)
%e A081064 For n=2 and k=2, we have T(2,2) = 2 labeled directed acyclic graphs with 2 nodes and 2 arcs: [A (double ->) B] and [B (double ->) A].
%e A081064 For n=3 and k=4, we have T(3,4) = 6 labeled directed acyclic graphs with 3 nodes and 4 arcs: [X (double ->) Y (single ->) Z (single <-) X] with (X,Y,Z) a permutation of {A,B,C}. (End)
%p A081064 A081064gf := proc(n,x)
%p A081064     local m,a ;
%p A081064     option remember;
%p A081064     if n = 0 then
%p A081064         1;
%p A081064     else
%p A081064         a := 0 ;
%p A081064         for m from 1 to n do
%p A081064             a := a+(-1)^(m-1)*binomial(n,m)*(1+x)^(m*(n-m)) *procname(n-m,x) ;
%p A081064         end do:
%p A081064         expand(a) ;
%p A081064     end if;
%p A081064 end proc:
%p A081064 A081064 := proc(n,k)
%p A081064     coeff(A081064gf(n,x),x,k) ;
%p A081064 end proc:
%p A081064 for n from 0 to 8 do
%p A081064     for k from 0 do
%p A081064         tnk := A081064(n,k) ;
%p A081064         if tnk =0 then
%p A081064             break;
%p A081064         end if;
%p A081064         printf("%d ",tnk) ;
%p A081064     end do:
%p A081064     printf("\n") ;
%p A081064 end do: # _R. J. Mathar_, Mar 21 2019
%t A081064 nn = 6; a[n_] := a[n] = Sum[(-1)^(k + 1) Binomial[n, k] (1 + x)^(k (n - k)) a[   n - k], {k, 1, n}]; a[0] = 1; Table[CoefficientList[a[n], x], {n, 0, nn}] // Grid (* _Geoffrey Critzer_, Mar 11 2023 *)
%o A081064 (PARI)
%o A081064 B(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, (1+'y)^(i*(#u-j))*((1+'y)^i-1)^j * binomial(n,i) * u[j])))); v}
%o A081064 T(n)={my(v=B(n)); vector(#v+1, n, if(n==1, [1], Vecrev(vecsum(v[n-1]))))}
%o A081064 { my(A=T(5)); for(i=1, #A, print(A[i])) } \\ _Andrew Howroyd_, Dec 27 2021
%Y A081064 Cf. A003024 (row sums), A055533 (subdiagonal).
%Y A081064 Columns: A147796 (k = 3), A147817 (k = 4), A147821 (k = 5), A147860 (k = 6), A147872 (k = 7), A147881 (k = 8), A147883 (k = 9), A147964 (k = 10).
%K A081064 easy,nonn,tabf
%O A081064 0,4
%A A081064 _Vladeta Jovovic_, Apr 15 2003
%E A081064 T(0,0) = 1 prepended by _Petros Hadjicostas_, Apr 11 2020