cp's OEIS Frontend

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.

%I A344379 #11 Jan 07 2022 19:34:41
%S A344379 1,3,1,45,9,1,1782,207,18,1,142164,10260,585,30,1,19943830,953424,
%T A344379 35235,1305,45,1,4507660380,151369792,3731049,93555,2520,63,1,
%U A344379 1540185346560,38205961380,657600076,11122209,211680,4410,84,1,757560406751120,14455803484728
%N 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.
%C A344379 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 A344379 Then the formula of A123543 (Gilbert's article) allows these values to be refined by the number of weakly connected components.
%H A344379 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 A344379 T(n,n) = 1. [n nodes, each with a triple loop].
%F A344379 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 A344379 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 A344379 Triangle begins:
%e A344379               1;
%e A344379               3,           1;
%e A344379              45,           9,         1;
%e A344379            1782,         207,        18,        1;
%e A344379          142164,       10260,       585,       30,      1;
%e A344379        19943830,      953424,     35235,     1305,     45,    1;
%e A344379      4507660380,   151369792,   3731049,    93555,   2520,   63,  1;
%e A344379   1540185346560, 38205961380, 657600076, 11122209, 211680, 4410, 84, 1;
%e A344379 ...
%p A344379 # Given a list L[1], L[2],... for labeled not necessarily connected graphs, generate
%p A344379 # triangle of labeled graphs with k weakly connected components.
%p A344379 lblNonc := proc(L::list)
%p A344379     local k,x,g,Lkx,t,Lkxt,n,c ;
%p A344379     add ( op(k,L)*x^k/k!,k=1..nops(L)) ;
%p A344379     log(1+%) ; # formula from A123543
%p A344379     g := taylor(%,x=0,nops(L)) ;
%p A344379     seq( coeftayl(g,x=0,i)*i!,i=1..nops(L)) ;
%p A344379     print(lc) ;# first column
%p A344379     Lkx := add ( coeftayl(g,x=0,i)*x^i,i=1..nops(L)) ;
%p A344379     Lkxt := exp(t*%) ;
%p A344379     for n from 0 to nops(L)-1 do
%p A344379         tmp := coeftayl(Lkxt,x=0,n) ;
%p A344379         for c from 0 to n do
%p A344379             printf("%a ", coeftayl(tmp,t=0,c)*n!) ;
%p A344379         end do:
%p A344379         printf("\n") ;
%p A344379     end do:
%p A344379 end proc:
%p A344379 L := [1, 4, 55, 2008, 153040, 20933840, 4662857360, 1579060246400, 772200774683520, 523853880779443200, 477360556805016931200, 569060910292172349004800, 868071731152923490921728000, 1663043727673392444887284377600, 3937477620391471128913917360384000] ;
%p A344379 lblNonc(L) ;
%Y A344379 Cf. A307804 (2-regular analog), A001500 (row sums), A045943 (subdiagonal).
%K A344379 nonn,tabl
%O A344379 1,2
%A A344379 _R. J. Mathar_, May 16 2021