A350745 Triangle read by rows: T(n,k) is the number of labeled loop-threshold graphs on vertex set [n] with k loops, for n >= 0 and 0 <= k <= n.

1, 1, 1, 1, 4, 1, 1, 12, 12, 1, 1, 32, 84, 32, 1, 1, 80, 460, 460, 80, 1, 1, 192, 2190, 4600, 2190, 192, 1, 1, 448, 9534, 37310, 37310, 9534, 448, 1, 1, 1024, 39032, 264208, 483140, 264208, 39032, 1024, 1, 1, 2304, 152856, 1702344, 5229756, 5229756, 1702344, 152856, 2304, 1

Offset: 0

Author

David Galvin, Jan 13 2022

Keywords

• nonn
• tabl

Comments

Loop-threshold graphs are constructed from either a single unlooped vertex or a single looped vertex by iteratively adding isolated vertices (adjacent to nothing previously added) and looped dominating vertices (looped, and adjacent to everything previously added).

Examples

			Triangle begins:
  1;
  1,    1;
  1,    4,      1;
  1,   12,     12,       1;
  1,   32,     84,      32,       1;
  1,   80,    460,     460,      80,       1;
  1,  192,   2190,    4600,    2190,     192,       1;
  1,  448,   9534,   37310,   37310,    9534,     448,      1;
  1, 1024,  39032,  264208,  483140,  264208,   39032,   1024,    1;
  1, 2304, 152856, 1702344, 5229756, 5229756, 1702344, 152856, 2304, 1;
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50).
• D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.

Crossrefs

Row sums are A000629.

Columns k=0..1 give: A000012, A001787,

Cf. A210657.

Programs

Mathematica

T[n_, 0] := T[n, 0] = 1; T[n_, k_] := T[n, k] = Binomial[n, k]*Sum[Factorial[l]*StirlingS2[k, l]*(Factorial[l - 1]*StirlingS2[n - k, l - 1] + 2*Factorial[l]*StirlingS2[n - k, l] + Factorial[l + 1]*StirlingS2[n - k, l + 1]), {l, 1, n + 1}]; Table[T[n, k], {n, 0, 12}, {k, 0, n}]

PARI

T(n,k) = if(k==0, 1, binomial(n,k) * sum(j=1, n, j!*stirling(k,j,2) * ((j-1)! * stirling(n-k,j-1,2) + 2*j!*stirling(n-k,j,2) + (j+1)!*stirling(n-k,j+1,2)))) \\ Andrew Howroyd, May 06 2023

Formula

T(n,0) = 1; T(n,k) = binomial(n,k) * Sum_{j=1..n} j!*Stirling2(k,j) * ((j-1)! * Stirling2(n-k,j-1) + 2*j!*Stirling2(n-k,j) + (j+1)!*Stirling2(n-k,j+1)).

T(n,k) = T(n,n-k).

Sum_{k=0..2*n} (-1)^k * T(2*n,k) = A210657(n). - Alois P. Heinz, Feb 01 2022