The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 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 (list; table; graph; refs; listen; history; text; internal format)
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
KEYWORD
nonn,tabl
AUTHOR
David Galvin, Jan 13 2022
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 12 23:24 EDT 2024. Contains 373362 sequences. (Running on oeis4.)