A123543 -id:A123543 - cp's OEIS frontend

A123544 Number of connected labeled 2-regular relations of order n.

0, 0, 1, 6, 87, 1980, 66270, 3050460, 184716630, 14231775600, 1359481407480, 157694893448400, 21835679256606600, 3557942554594428000, 673941365091485290800, 146851484638349504613600

Offset: 0

N. J. A. Sloane, Nov 13 2006

nonn

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.

R. W. Robinson, Table of n, a(n) for n = 0..48

Connected version of A001499. Unlabeled version is A005642.

Cf. A123543.

m = 16;
a1499[n_] := (n - 1)*n!*Gamma[n - 1/2]*Hypergeometric1F1[2 - n, 3/2 - n, -1/2]/Sqrt[Pi];
egf = Log[1 + Sum[a1499[k] x^k/k!, {k, 1, m}]];
CoefficientList[egf + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Aug 26 2019 *)

seq(n)={Vec(serlaplace(log(serlaplace(exp(-x/2 + O(x*x^n))/sqrt(1-x + O(x*x^n))))), -(n+1))}; \\ Andrew Howroyd, Sep 09 2018

E.g.f.: log(1 + Sum_{k>0} A001499(k)*x^k/k!). - Andrew Howroyd, Sep 09 2018

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

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 14, 6, 1, 0, 201, 68, 12, 1, 0, 4704, 1285, 200, 20, 1, 0, 160890, 36214, 4815, 460, 30, 1, 0, 7538040, 1422288, 160594, 13755, 910, 42, 1, 0, 462869190, 74416131, 7151984, 535864, 33110, 1624, 56, 1, 0, 36055948320, 5016901734, 413347787, 26821368, 1490664, 70686, 2688, 72, 1

Offset: 0

R. J. Mathar, Apr 29 2019

			Triangle T(n,k) starts:
  1;
  0,       1;
  0,       2,       1;
  0,      14,       6,      1;
  0,     201,      68,     12,     1;
  0,    4704,    1285,    200,    20,   1;
  0,  160890,   36214,   4815,   460,  30,  1;
  0, 7538040, 1422288, 160594, 13755, 910, 42, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Tom Copeland, Production matrix for certain family of integer coefficients, answer to question on MathOverflow (2025).
E. N. Gilbert, Enumeration of labelled graphs, Can. J. Math. 8 (1956) 405-411.
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.

Cf. A123543 (column k=1), A000681 (row sums).

b:= proc(n) option remember; `if`(n<2, 1,
      n^2*b(n-1)-n*(n-1)^2*b(n-2)/2)
    end:
a:= proc(n) option remember; `if`(n=0, 0, b(n)-
      add(j*binomial(n, j)*b(n-j)*a(j), j=1..n-1)/n)
    end:
g:= proc(n, k) option remember; `if`(n=0, x^k/k!,
      add(g(n-j, k+1)*a(j)*binomial(n,j), j=1..n))
    end:
T:= (n,k)-> coeff(g(n, 0), x, k):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Mar 22 2025

b[n_] := b[n] = If[n < 2, 1, n^2*b[n - 1] - n*(n - 1)^2*b[n - 2]/2];
a[n_] := a[n] = If[n == 0, 0, b[n] - Sum[j*Binomial[n, j]*b[n - j]*a[j], {j, 1, n - 1}]/n];
g[n_, k_] := g[n, k] = If[n == 0, x^k/k!, Sum[g[n - j, k + 1]*a[j]* Binomial[n, j], {j, 1, n}]];
T[n_, k_] := Coefficient[g[n, 0], x, k];
Table[Table[T[n, k], { k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 16 2025, after Alois P. Heinz *)

T(n,1) = A123543(n).
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.g.f.: Sum_{n,k>=0} T(n,k)*x^n*t^k/n! = exp(t*E123543(x)) where E123543(x) = Sum_{n>=1} A123543(n)*x^n/t^n. [Gilbert]. - R. J. Mathar, May 08 2019
Conjectures from Mikhail Kurkov, Mar 22 2025: (Start)
Recursion for the k-th column (independently of other columns): T(n,k) = (1/(n-k))*Sum_{j=2..n-k+1} c(j-1)*binomial(n,j)*T(n-j+1,k) for 1 <= k < n with T(n,n) = 1 where b(n) = A123543(n), c(n) = n*b(n+1) - Sum_{j=1..n-1} binomial(n+1,j+1)*b(n-j+1)*c(j) for n > 0.
Production matrix is binomial(n,k)*d(n-k) (starting from the first row) for 0 <= k <= n, 0 otherwise where d(n) = E_n^{(-1)} from A356145 with a_k = b(k+1) for k > 0 (see Tom Copeland link).
The same things seems to work for any b(n) with b(1) = 1 (I mean that it works for e.g.f. exp(t*F(x)) where F(x) = Sum_{n>=1} b(n)*x^n/n!). (End)

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.

Original entry on oeis.org

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

R. J. Mathar, May 16 2021

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.

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

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

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

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

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

cp's OEIS Frontend

A123544 Number of connected labeled 2-regular relations of order n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula