OFFSET
1,5
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.
LINKS
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 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.)
EXAMPLE
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;
...
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}]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
David Galvin, Dec 11 2021
STATUS
approved