login
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

%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