A350060 Triangle read by rows: T(n,k) is the number of labeled threshold graphs on vertex set [n] in which k dominating vertices are added in standard iterative construction, n >= 1 and 0 <= k <= n-1.

1, 1, 1, 1, 6, 1, 1, 22, 22, 1, 1, 65, 200, 65, 1, 1, 171, 1265, 1265, 171, 1, 1, 420, 6566, 15050, 6566, 420, 1, 1, 988, 30156, 136346, 136346, 30156, 988, 1, 1, 2259, 127632, 1039878, 2009952, 1039878, 127632, 2259, 1

Offset: 1

Author

David Galvin, Dec 11 2021

Keywords

• nonn
• tabl

Comments

Threshold graphs are constructed from a single vertex by iteratively adding isolated vertices (adjacent to nothing previously added) and dominating vertices (adjacent to everything previously added). The initial vertex is not considered to be a dominating vertex.

Examples

			Triangle begins:
  1;
  1,     1;
  1,     6,      1;
  1,    22,     22,       1;
  1,    65,    200,      65,       1;
  1,   171,   1265,    1265,     171,       1;
  1,   420,   6566,   15050,    6566,     420,      1;
  1,   988,  30156,  136346,  136346,   30156,    988,    1;
  1,  2259, 127632, 1039878, 2009952, 1039878, 127632,  2259,  1;
  ...
		

Links

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

Cf. A348576.

Programs

Mathematica

eulerian[n_,m_] := eulerian[n,m] =
  Sum[((-1)^k)*Binomial[n+1,k]*((m+1-k)^n), {k,0,m+1}] (* eulerian[n, m] is an Eulerian number, counting the permutations of [n] with m descents *);
op2[n_,k_] := op2[n,k] =
   Sum[(n-j)*eulerian[n-1,j-1]*Binomial[j-1,n-k-1], {j,1,n-1}] (* op2[n,k] counts ordered partitions of [n] with k parts, with first part having size at least 2 *);
T[n_, 0] := T[n, 0] = 1; T[2, 1] = 1; T[2, k_] := T[2, k] = 0;
T[n_, k_] :=
T[n, k] =
  Sum[Binomial[n, k + 1]*
     op2[k + 1,
      l]*(Factorial[l - 1]*StirlingS2[n - k - 1, l - 1] +
       Factorial[l]*StirlingS2[n - k - 1, l]) +
    Binomial[n, k]*Factorial[l]*
     StirlingS2[k, l]*(op2[n - k, l + 1] + op2[n - k, l]), {l, 1,
    n}] (* T[n, k] is number of threshold graphs on n vertices with k dominating vertices added in construction*);
Table[T[n, k],{n,1,12},{k,0,n-1}]

Formula

T(n,0) = 1 for n >= 1; T(2,1) = 1; T(n,k) = (Sum_{j=1..k} binomial(n, k+1)*A348576(k+1, j)*((j-1)!*A008277(n-k-1, j-1) + j!*A008277(n-k-1, j))) + (Sum_{j=1..n-k-1} binomial(n, k)*j!*A008277(k, j)*(A348576(n-k, j+1) + A348576(n-k, j))) for n >= 3, k >= 1. (See also equation (7) of paper by Galvin, Wesley and Zacovic.)