login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #19 Feb 04 2022 09:55:15

%S 2,3,3,13,9,4,75,52,18,5,541,375,130,30,6,4683,3246,1125,260,45,7,

%T 47293,32781,11361,2625,455,63,8,545835,378344,131124,30296,5250,728,

%U 84,9,7087261,4912515,1702548,393372,68166,9450,1092,108,10

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

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

%H D. Galvin, G. Wesley and B. Zacovic, <a href="https://arxiv.org/abs/2110.08953">Enumerating threshold graphs and some related graph classes</a>, arXiv:2110.08953 [math.CO], 2021.

%F T(n,n) = n+1 for n >= 1; T(n,1) = Sum_{j=0..n-1} A173018(n,j)*2^j for n >= 2; T(n,k) = binomial(n, k-1)*T(n-k+1,1) for n >= 3, 2 <= k <= n-1.

%e Triangle begins:

%e 2;

%e 3, 3;

%e 13, 9, 4;

%e 75, 52, 18, 5;

%e 541, 375, 130, 30, 6;

%e 4683, 3246, 1125, 260, 45, 7;

%e 47293, 32781, 11361, 2625, 455, 63, 8;

%e 545835, 378344, 131124, 30296, 5250, 728, 84, 9;

%e 7087261, 4912515, 1702548, 393372, 68166, 9450, 1092, 108, 10;

%e ...

%t eulerian[n_, m_] := eulerian[n, m] =

%t 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 *); T[1, 1] = 2; T[n_, 1] := T[n, 1] = Sum[eulerian[n, k]*(2^k), {k, 0, n - 1}]; T[n_, n_] := T[n, n] = n + 1; T[n_, k_] := T[n, k] = Binomial[n, k - 1]*T[n - k + 1, 1]; Table[T[n, k], {n, 1, 12}, {k, 1, n}]

%Y Row sums are A000629.

%Y Except at n = 1, first column is A000670.

%Y Essentially the same as A154921 --- in A350531 (this triangle), replace the last nonzero entry in row m (this entry is m+1) with the two entries m, 1 to get A154921.

%Y Cf. A173018.

%K nonn,tabl

%O 1,1

%A _David Galvin_, Jan 03 2022