A344379 - OEIS

%I #11 Jan 07 2022 19:34:41

%S 1,3,1,45,9,1,1782,207,18,1,142164,10260,585,30,1,19943830,953424,

%T 35235,1305,45,1,4507660380,151369792,3731049,93555,2520,63,1,

%U 1540185346560,38205961380,657600076,11122209,211680,4410,84,1,757560406751120,14455803484728

%N 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.

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

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

%H E. N. Gilbert, <a href="https://doi.org/10.4153/CJM-1956-046-2">Enumeration of labelled graphs</a>, Can. J. Math. 8 (1956) 405-411.

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

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

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

%e Triangle begins:

%e               1;

%e               3,           1;

%e              45,           9,         1;

%e            1782,         207,        18,        1;

%e          142164,       10260,       585,       30,      1;

%e        19943830,      953424,     35235,     1305,     45,    1;

%e      4507660380,   151369792,   3731049,    93555,   2520,   63,  1;

%e   1540185346560, 38205961380, 657600076, 11122209, 211680, 4410, 84, 1;

%e ...

%p # Given a list L[1], L[2],... for labeled not necessarily connected graphs, generate

%p # triangle of labeled graphs with k weakly connected components.

%p lblNonc := proc(L::list)

%p     local k,x,g,Lkx,t,Lkxt,n,c ;

%p     add ( op(k,L)*x^k/k!,k=1..nops(L)) ;

%p     log(1+%) ; # formula from A123543

%p     g := taylor(%,x=0,nops(L)) ;

%p     seq( coeftayl(g,x=0,i)*i!,i=1..nops(L)) ;

%p     print(lc) ;# first column

%p     Lkx := add ( coeftayl(g,x=0,i)*x^i,i=1..nops(L)) ;

%p     Lkxt := exp(t*%) ;

%p     for n from 0 to nops(L)-1 do

%p         tmp := coeftayl(Lkxt,x=0,n) ;

%p         for c from 0 to n do

%p             printf("%a ", coeftayl(tmp,t=0,c)*n!) ;

%p         end do:

%p         printf("\n") ;

%p     end do:

%p end proc:

%p L := [1, 4, 55, 2008, 153040, 20933840, 4662857360, 1579060246400, 772200774683520, 523853880779443200, 477360556805016931200, 569060910292172349004800, 868071731152923490921728000, 1663043727673392444887284377600, 3937477620391471128913917360384000] ;

%p lblNonc(L) ;

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

%K nonn,tabl

%O 1,2

%A _R. J. Mathar_, May 16 2021