A369283 Triangle read by rows: T(n,k) is the number of labeled point-determining graphs with n nodes and k edges, n >= 0, 0 <= k <= n*(n - 1)/2.

1, 1, 0, 1, 0, 3, 0, 1, 0, 0, 3, 16, 12, 0, 1, 0, 0, 15, 60, 130, 132, 140, 80, 30, 0, 1, 0, 0, 0, 15, 600, 1692, 3160, 4635, 4620, 3480, 2088, 885, 240, 60, 0, 1, 0, 0, 0, 105, 1260, 7665, 28042, 74280, 142380, 218960, 271404, 276150, 230860, 157710, 86250, 38752, 13524, 3360, 560, 105, 0, 1

Offset

0,6

Comments

Point-determining graphs are also called mating graphs.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)

Ira M. Gessel and Ji Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612.

Formula

Sum_{k>=0} 2^k*T(n,k) = A102596(n).

Sum_{k>=0} 3^k*T(n,k) = A102579(n).

Example

Triangle begins:
 [0] 1;
 [1] 1;
 [2] 0, 1;
 [3] 0, 3,  0,  1;
 [4] 0, 0,  3, 16,  12,    0,    1;
 [5] 0, 0, 15, 60, 130,  132,  140,   80,   30,    0,    1;
 [6] 0, 0,  0, 15, 600, 1692, 3160, 4635, 4620, 3480, 2088, 885, 240, 60, 0, 1;
  ...

Prog

(PARI)
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(p, t) = {prod(i=2, #p, prod(j=1, i-1, t(p[i]*p[j])))}
row(n) = {my(s=0); forpart(p=n, s += permcount(p)*(-1)^(n-#p)*edges(p, w->1 + x^w)); Vecrev(s)}

Crossrefs

Row sums are A006024.

Cf. A102579, A102596, A368987 (unlabeled).

Sequence in context: A356098 A106216 A035676 * A129685 A292835 A372503

Adjacent sequences: A369280 A369281 A369282 * A369284 A369285 A369286

Keyword

nonn,tabf

Author

Andrew Howroyd, Jan 18 2024

Status

approved