|
|
A167625
|
|
Square array T(n,k), read by upward antidiagonals, counting isomorphism classes of k-regular multigraphs of order n, loops allowed.
|
|
11
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|