A333893 - OEIS

A333893

Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 4, 5, 3, 1, 1, 1, 5, 8, 10, 3, 1, 1, 1, 6, 14, 26, 16, 4, 1, 1, 1, 7, 20, 61, 60, 29, 4, 1, 1, 1, 8, 30, 128, 243, 184, 45, 5, 1, 1, 1, 9, 40, 254, 800, 1228, 488, 75, 5, 1, 1, 1, 10, 55, 467, 2518, 7252, 6684, 1509, 115, 6, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,9

COMMENTS

T(n,k) is the number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to k and isomorphism being up to simultaneous permutation of rows and columns. The case that allows independent permutations of rows and columns is covered by A333737.

Terms may be computed without generating each graph by enumerating the graphs by degree sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A188403. Burnside's lemma as applied in A192517 can be used to extend this method to the unlabeled case.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..377 (antidiagonals 0..26)

EXAMPLE

Array begins:

==============================================

n\k | 0 1 2 3 4 5 6 7

----+-----------------------------------------

0 | 1 1 1 1 1 1 1 1 ...

1 | 1 1 1 1 1 1 1 1 ...

2 | 1 2 3 4 5 6 7 8 ...

3 | 1 2 5 8 14 20 30 40 ...

4 | 1 3 10 26 61 128 254 467 ...