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.

Sequence in context: A195788 A201930 A176979 * A299989 A058022 A215202

Adjacent sequences: A370316 A370317 A370318 * A370320 A370321 A370322

Keyword

nonn,tabl

Author

Gus Wiseman, Feb 18 2024

Extensions

More terms from Giorgos Kalogeropoulos, Feb 25 2024

Status

approved