A370319 Triangle read by rows where T(n,k) is the number of labeled graphs with n vertices and k non-isolated vertices.
1, 1, 0, 1, 0, 1, 1, 0, 3, 4, 1, 0, 6, 16, 41, 1, 0, 10, 40, 205, 768, 1, 0, 15, 80, 615, 4608, 27449, 1, 0, 21, 140, 1435, 16128, 192143, 1887284, 1, 0, 28, 224, 2870, 43008, 768572, 15098272, 252522481, 1, 0, 36, 336, 5166, 96768, 2305716, 67942224, 2272702329, 66376424160
Offset: 0
Examples
Triangle begins:
1
1 0
1 0 1
1 0 3 4
1 0 6 16 41
1 0 10 40 205 768
1 0 15 80 615 4608 27449
Row n = 3 counts the following edge sets:
{} . {{1,2}} {{1,2},{1,3}}
{{1,3}} {{1,2},{2,3}}
{{2,3}} {{1,3},{2,3}}
{{1,2},{1,3},{2,3}}
Crossrefs
Programs
-
Mathematica
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[Union@@#]==k&]],{n,0,5},{k,0,n}] Flatten@Table[Binomial[n,k]*Sum[(-1)^(k-m) Binomial[k,m] 2^Binomial[m,2],{m,0,k}],{n,0,10},{k,0,n}] (* Giorgos Kalogeropoulos, Feb 25 2024 *)
Formula
T(n,k) = binomial(n,k) * A006129(k).
T(n,n-1) = (n-1) * A006129(n-1).
T(n,k) = A198261(n, n-k). - Andrew Howroyd, Feb 26 2024
Extensions
More terms from Giorgos Kalogeropoulos, Feb 25 2024