login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 14
1, 1, 1, 2, 1, 6, 12, 6, 1, 12, 60, 152, 186, 108, 24, 1, 20, 180, 940, 3050, 6180, 7960, 6540, 3330, 960, 120, 1, 30, 420, 3600, 20790, 83952, 240480, 496680, 750810, 838130, 691020, 416160, 178230, 51480, 9000, 720, 1, 42, 840, 10570, 93030, 601944 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

LINKS

Table of n, a(n) for n=0..47.

V. I. Rodionov, On the number of labeled acyclic digraphs, Discr. Math. 105 (1-3) (1992), 319-321.

FORMULA

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

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

From Petros Hadjicostas, Apr 10 2020: (Start)

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.

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

Also, T(n, n*(n-1)/2 - 1) = A055533(n) = n!*(n-1)^2/2 for n > 1. (End)

EXAMPLE

Array T(n,k) (with n >= 0 and 0 <= k <= n*(n-1)/2) begins as follows:

  1;

  1;

  1,  2;

  1,  6,  12,   6;

  1, 12,  60, 152,  186,  108,   24;

  1, 20, 180, 940, 3050, 6180, 7960, 6540, 3330, 960, 120;

  ...

From Petros Hadjicostas, Apr 10 2020: (Start)

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

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)

MAPLE

A081064gf := proc(n, x)

    local m, a ;

    option remember;

    if n = 0 then

        1;

    else

        a := 0 ;

        for m from 1 to n do

            a := a+(-1)^(m-1)*binomial(n, m)*(1+x)^(m*(n-m)) *procname(n-m, x) ;

        end do:

        expand(a) ;

    end if;

end proc:

A081064 := proc(n, k)

    coeff(A081064gf(n, x), x, k) ;

end proc:

for n from 0 to 8 do

    for k from 0 do

        tnk := A081064(n, k) ;

        if tnk =0 then

            break;

        end if;

        printf("%d ", tnk) ;

    end do:

    printf("\n") ;

end do: # R. J. Mathar, Mar 21 2019

CROSSREFS

Cf. A003024 (row sums), A055533 (subdiagonal).

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

Sequence in context: A303986 A342589 A325635 * A128534 A002562 A218492

Adjacent sequences:  A081061 A081062 A081063 * A081065 A081066 A081067

KEYWORD

easy,nonn,tabf

AUTHOR

Vladeta Jovovic, Apr 15 2003

EXTENSIONS

T(0,0) = 1 prepended by Petros Hadjicostas, Apr 11 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 1 00:13 EDT 2021. Contains 346377 sequences. (Running on oeis4.)