A344379 Triangle read by rows: T(n,k) is the number of labeled 3-regular digraphs (multiple arcs and loops allowed) on n nodes with k components.

1, 3, 1, 45, 9, 1, 1782, 207, 18, 1, 142164, 10260, 585, 30, 1, 19943830, 953424, 35235, 1305, 45, 1, 4507660380, 151369792, 3731049, 93555, 2520, 63, 1, 1540185346560, 38205961380, 657600076, 11122209, 211680, 4410, 84, 1, 757560406751120, 14455803484728

Offset

1,2

Comments

Derived by interpreting A001500 as the number of labeled 3-regular digraphs (in-degree and out-degree at each node=3), without regarding the trace (which means loops are allowed) and no limit on the individual entries (so multiple arcs in the same direction between nodes are allowed).

Then the formula of A123543 (Gilbert's article) allows these values to be refined by the number of weakly connected components.

Links

Table of n, a(n) for n=1..38.

E. N. Gilbert, Enumeration of labelled graphs, Can. J. Math. 8 (1956) 405-411.

Formula

T(n,n) = 1. [n nodes, each with a triple loop].

T(n,n-1) = A045943(n-1). [n-1 isolated nodes, one labeled pair with n(n-1)/2 choices of labels and 3 choices of zero, one or two loops at the lower label].

T(n,k) = Sum_{Compositions n=n_1+n_2+...n_k, n_i>=1} multinomial(n; n_1,n_2,...,n_k) * T(n_1,1) * T(n_2,1) * ... *T(n_k,1) / k!.

Example

Triangle begins:
              1;
              3,           1;
             45,           9,         1;
           1782,         207,        18,        1;
         142164,       10260,       585,       30,      1;
       19943830,      953424,     35235,     1305,     45,    1;
     4507660380,   151369792,   3731049,    93555,   2520,   63,  1;
  1540185346560, 38205961380, 657600076, 11122209, 211680, 4410, 84, 1;
...

Maple

# Given a list L[1], L[2], ... for labeled not necessarily connected graphs, generate
# triangle of labeled graphs with k weakly connected components.
lblNonc := proc(L::list)
    local k, x, g, Lkx, t, Lkxt, n, c ;
    add ( op(k, L)*x^k/k!, k=1..nops(L)) ;
    log(1+%) ; # formula from A123543
    g := taylor(%, x=0, nops(L)) ;
    seq( coeftayl(g, x=0, i)*i!, i=1..nops(L)) ;
    print(lc) ; # first column
    Lkx := add ( coeftayl(g, x=0, i)*x^i, i=1..nops(L)) ;
    Lkxt := exp(t*%) ;
    for n from 0 to nops(L)-1 do
        tmp := coeftayl(Lkxt, x=0, n) ;
        for c from 0 to n do
            printf("%a ", coeftayl(tmp, t=0, c)*n!) ;
        end do:
        printf("\n") ;
    end do:
end proc:
L := [1, 4, 55, 2008, 153040, 20933840, 4662857360, 1579060246400, 772200774683520, 523853880779443200, 477360556805016931200, 569060910292172349004800, 868071731152923490921728000, 1663043727673392444887284377600, 3937477620391471128913917360384000] ;
lblNonc(L) ;

Crossrefs

Cf. A307804 (2-regular analog), A001500 (row sums), A045943 (subdiagonal).

Sequence in context: A136517 A366479 A104097 * A155812 A158958 A098341

Adjacent sequences: A344376 A344377 A344378 * A344380 A344381 A344382

Keyword

nonn,tabl

Author

R. J. Mathar, May 16 2021

Status

approved