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,9

Links

Table of n, a(n) for n=0..54.

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

Example

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}}

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 *)

Crossrefs

Row sums are A006125, unlabeled A000088.

Column k = n is A006129, unlabeled A002494.

Mirror of A198261, unlabeled A217653.

The unlabeled version is the partial subsequences of A002494.

Cf. A001187, A003465, A006126, A116508, A143543, A287689, A367862.

Keyword

nonn,tabl

Author

Gus Wiseman, Feb 18 2024

Extensions

More terms from Giorgos Kalogeropoulos, Feb 25 2024

Status

approved