login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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 * A107261 A265336 A219782

Adjacent sequences:  A167622 A167623 A167624 * A167626 A167627 A167628

KEYWORD

nonn,tabl

AUTHOR

Jason Kimberley, Nov 07 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 8 11:31 EDT 2020. Contains 336298 sequences. (Running on oeis4.)