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,5

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

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.

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

Example

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

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}]

Prog

(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

Crossrefs

Row sums are A000629.

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

Cf. A210657.

Sequence in context: A099759 A350819 A072590 * A111636 A220688 A146990

Adjacent sequences: A350742 A350743 A350744 * A350746 A350747 A350748

Keyword

nonn,tabl

Author

David Galvin, Jan 13 2022

Status

approved