A167625 Square array T(n,k), read by upward antidiagonals, counting isomorphism classes of k-regular multigraphs of order n, loops allowed.

1, 1, 0, 1, 1, 1, 1, 0, 2, 0, 1, 1, 3, 2, 1, 1, 0, 5, 0, 3, 0, 1, 1, 7, 8, 7, 3, 1, 1, 0, 11, 0, 20, 0, 4, 0, 1, 1, 15, 31, 56, 32, 13, 4, 1, 1, 0, 22, 0, 187, 0, 66, 0, 5, 0, 1, 1, 30, 140, 654, 727, 384, 101, 22, 5, 1, 1, 0, 42, 0, 2705, 0, 3369, 0, 181, 0, 6, 0, 1, 1, 56, 722, 12587, 42703

Offset

1,9

Comments

The number of vertices n is positive; valency k is nonnegative.

Each loop contributes two to the valency of its vertex.

The antidiagonal having coordinate sum t=n+k is read from T(t,0) to T(1,t-1).

Terms may be computed without generating each graph by enumerating the number of graphs by degree sequence. A PARI program showing this technique for graphs with labeled vertices is given in A333467. Burnside's lemma can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 23 2020

Links

Andrew Howroyd, Table of n, a(n) for n = 1..378 (27 antidiagonals, first 19 antidiagonals from Jason Kimberley)

J. S. Kimberley, Table in user subpage of wiki.

R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436.

Formula

T(n,k) = N\{S_n[S_k] * S_{nk/2}[S_2]\}.

Example

Array begins:
==============================================
n\k | 0 1  2   3    4     5      6       7
----+-----------------------------------------
  1 | 1 0  1   0    1     0      1       0 ...
  2 | 1 1  2   2    3     3      4       4 ...
  3 | 1 0  3   0    7     0     13       0 ...
  4 | 1 1  5   8   20    32     66     101 ...
  5 | 1 0  7   0   56     0    384       0 ...
  6 | 1 1 11  31  187   727   3369   12782 ...
  7 | 1 0 15   0  654     0  40365       0 ...
  8 | 1 1 22 140 2705 42703 675368 8584767 ...
  ...

Crossrefs

Column sequences: A000012 (k=0), A059841 (k=1), A000041 (k=2), A129427 (k=3), A129429 (k=4), A129431 (k=5), A129433 (k=6), A129435 (k=7), A129437 (k=8).

Cf. A333330 (loopless), A333397 (connected), A333467 (labeled).

Sequence in context: A058725 A068446 A253830 * A372442 A107261 A265336

Adjacent sequences: A167622 A167623 A167624 * A167626 A167627 A167628

Keyword

nonn,tabl

Author

Jason Kimberley, Nov 07 2009

Status

approved