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.

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

Author

R. J. Mathar, Apr 29 2019

Keywords

• nonn
• tabl
• easy

Examples

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

Links

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

Crossrefs

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

Programs

Maple

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

Mathematica

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

Formula

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)