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

Author

R. J. Mathar, May 16 2021

Keywords

• nonn
• tabl

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.

Examples

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

Links

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

Crossrefs

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

Programs

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

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