A333351 Array read by antidiagonals: T(n,k) is the number of k-regular loopless multigraphs on n labeled nodes, n >= 0, k >= 0.

1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 3, 1, 1, 0, 1, 0, 6, 0, 1, 1, 0, 1, 1, 10, 22, 15, 1, 1, 0, 1, 0, 15, 0, 130, 0, 1, 1, 0, 1, 1, 21, 158, 760, 822, 105, 1, 1, 0, 1, 0, 28, 0, 3355, 0, 6202, 0, 1, 1, 0, 1, 1, 36, 654, 12043, 93708, 190050, 52552, 945, 1, 1, 0, 1, 0, 45, 0, 36935, 0, 3535448, 0, 499194, 0, 1

Offset

0,20

Links

Andrew Howroyd, Table of n, a(n) for n = 0..405

Example

Array begins:
=================================================================
n\k | 0   1    2      3       4        5         6          7
----+------------------------------------------------------------
  0 | 1   1    1      1       1        1         1          1 ...
  1 | 1   0    0      0       0        0         0          0 ...
  2 | 1   1    1      1       1        1         1          1 ...
  3 | 1   0    1      0       1        0         1          0 ...
  4 | 1   3    6     10      15       21        28         36 ...
  5 | 1   0   22      0     158        0       654          0 ...
  6 | 1  15  130    760    3355    12043     36935     100135 ...
  7 | 1   0  822      0   93708        0   3226107          0 ...
  8 | 1 105 6202 190050 3535448 45163496 431400774 3270643750 ...
  ...

Prog

(PARI)
MultigraphsByDegreeSeq(n, limit, ok)={
  local(M=Map(Mat([0, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(r, h, p, q, v, e) = if(!p, if(ok(x^e+q, r), acc(x^e+q, v)), my(i=poldegree(p), t=pollead(p)); self()(r, limit, p-t*x^i, q+t*x^i, v, e); for(m=1, h-i, for(k=1, min(t, (limit-e)\m), self()(r, if(k==t, limit, i+m-1), p-k*x^i, q+k*x^(i+m), binomial(t, k)*v, e+k*m)))));
  for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(n-r, limit, src[i, 1], 0, src[i, 2], 0))); Mat(M);
}
T(n, k)={if((n%2&&k%2)||(n==1&&k>0), 0, vecsum(MultigraphsByDegreeSeq(n, k, (p, r)->subst(deriv(p), x, 1)>=(n-2*r)*k)[, 2]))}
{ for(n=0, 8, for(k=0, 7, print1(T(n, k), ", ")); print) }

Crossrefs

Rows n=4..6 are A000217(n+1), A244868 (with interspersed zeros), A244878.

Columns k=0..4 are A000012, A123023, A002137, A108243 (with interspersed zeros), A367497.

Cf. A059441 (graphs), A333157, A333330 (unlabeled nodes), A333467 (with loops).

Sequence in context: A195151 A271024 A125208 * A193140 A319993 A122776

Adjacent sequences: A333348 A333349 A333350 * A333352 A333353 A333354

Keyword

nonn,tabl

Author

Andrew Howroyd, Mar 15 2020

Status

approved