A167625 -id:A167625 - cp's OEIS frontend

A129427 Number of isomorphism classes of 3-regular multigraphs of order 2n, loops allowed.

1, 2, 8, 31, 140, 722, 4439, 32654, 289519, 3054067, 37584620, 527968286, 8308434931, 144345554051, 2738280739075, 56245013793246, 1242596591479816, 29366532494796900, 739033832149588904, 19726887762569763453

Offset: 0

Brendan McKay, Apr 15 2007

nonn

a(1)..a(11) computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

P. A. Morris, Letter to N. J. A. Sloane, Mar 02 1971.

R. de Mello Koch, S. Ramgoolam, Strings from Feynman graph counting: Without large N, Phys. Rev. D 85 (2012) 026007
P. A. Morris, Letter to N. J. A. Sloane, Mar 02 1971.
R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436. - _Jason Kimberley_, Sep 17 2009

Column k=3 of A167625.

Cf. A005967 (connected, inv. Euler trans.), A129416, A129429, A129431, A129433, A129435, A129437, A005638.

h = SymmetricFunctions(QQ).homogeneous()
def A129427(n):
    X = h([2*n]).plethysm(h([3]))
    Y = h([3*n]).plethysm(h([2]))
    return X.scalar(Y)
# Bruce Westbury, Aug 16 2013

a(n)=N\{S_{2n}[S_3] * S_{3n}[S_2]\}. - Jason Kimberley, Sep 17 2009

Using equation (5.8) of Read 1959, new terms a(12) and a(13) were computed in MAGMA by Jason Kimberley, Sep 17 2009
Further terms a(14)-a(16) also computed by Jason Kimberley, announced Nov 09 2009
Formula corrected from n vertices to 2n vertices by Jason Kimberley, Nov 09 2009
Added a(0). - N. J. A. Sloane, Aug 26 2013
a(17)-a(19) from Sean A. Irvine, Oct 29 2016

A129429 Number of isomorphism classes of 4-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 3, 7, 20, 56, 187, 654, 2705, 12587, 67902, 417065, 2897432, 22382255, 189930004, 1750561160, 17380043136, 184653542135, 2088649831822, 25046462480066, 317295911519901, 4233450347175663, 59329632953577985, 871281036897298464

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Equation (5.8) of Read's paper tells us a(n) = N {S_n[S_4] * S_{2n}[S_2]}, where we are working with cycle index polynomials. - Jason Kimberley, Oct 05 2009

Andrew Howroyd, Table of n, a(n) for n = 1..40
R. de Mello Koch and S. Ramgoolam, Strings from Feynman graph counting: Without large N, Phys. Rev. D 85 (2012) 026007
R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436.

Column k=4 of A167625.

Cf. A085549 (connected), A129418, A129427, A129431, A129433, A129435, A129437.

Euler transform of A085549. - Andrew Howroyd, Mar 15 2020

Using equation (5.8) of Read's paper, new terms a(17)-a(19) were computed in MAGMA by Jason Kimberley, Oct 05 2009

Four more terms a(20)-a(23) also computed by Jason Kimberley, Nov 09 2009

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

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 2, 0, 1, 1, 0, 1, 1, 3, 2, 1, 1, 1, 0, 1, 0, 4, 0, 4, 0, 1, 1, 0, 1, 1, 5, 7, 9, 4, 1, 1, 1, 0, 1, 0, 7, 0, 24, 0, 7, 0, 1, 1, 0, 1, 1, 8, 16, 54, 60, 32, 8, 1, 1, 1, 0, 1, 0, 10, 0, 128, 0, 240, 0, 12, 0, 1, 1, 0, 1, 1, 12, 37, 271, 955, 1753, 930, 135, 14, 1, 1

Offset: 0

Andrew Howroyd, Mar 15 2020

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 A333351. Burnside's lemma can be used to extend this method to the unlabeled case.

			Array begins:
=================================================
n\k | 0 1 2  3   4    5      6     7        8
----+--------------------------------------------
  0 | 1 1 1  1   1    1      1     1        1 ...
  1 | 1 0 0  0   0    0      0     0        0 ...
  2 | 1 1 1  1   1    1      1     1        1 ...
  3 | 1 0 1  0   1    0      1     0        1 ...
  4 | 1 1 2  3   4    5      7     8       10 ...
  5 | 1 0 2  0   7    0     16     0       37 ...
  6 | 1 1 4  9  24   54    128   271      582 ...
  7 | 1 0 4  0  60    0    955     0    12511 ...
  8 | 1 1 7 32 240 1753  13467 90913   543779 ...
  9 | 1 0 8  0 930    0 253373     0 35255015 ...
  ...

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

Columns k=0..8 are (with interspersed 0's for odd k): A000012, A000012, A002865, A129416, A129418, A129420, A129422, A129424, A129426.
Row n=4 is A001399.
Cf. A051031 (simple graphs), A167625 (with loops), A192517 (not necessarily regular), A328682 (connected), A333351 (labeled nodes).

A333733 Array read by antidiagonals: T(n,k) is the number of non-isomorphic n X n nonnegative integer matrices with all row and column sums equal to k up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 3, 5, 5, 1, 1, 1, 1, 3, 9, 12, 7, 1, 1, 1, 1, 4, 13, 43, 31, 11, 1, 1, 1, 1, 4, 22, 106, 264, 103, 15, 1, 1, 1, 1, 5, 30, 321, 1856, 2804, 383, 22, 1, 1, 1, 1, 5, 45, 787, 12703, 65481, 44524, 1731, 30, 1, 1

Offset: 0

Andrew Howroyd, Apr 04 2020

Terms may be computed without generating each matrix by enumerating the number of matrices by column sum sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A257493. Burnside's lemma can be used to extend this method to the unlabeled case.

			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 1  2   2     3       3         4          4 ...
  3 | 1 1  3   5     9      13        22         30 ...
  4 | 1 1  5  12    43     106       321        787 ...
  5 | 1 1  7  31   264    1856     12703      71457 ...
  6 | 1 1 11 103  2804   65481   1217727   16925049 ...
  7 | 1 1 15 383 44524 3925518 224549073 8597641912 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..275 (first 23 antidiagonals)

Rows n=0..5 are A000012, A000012, A008619, A052282, A052280, A333735.
Columns k=0..5 are A000012, A000012, A000041, A232215, A232216, A333736.
Main diagonal is A333734.
Cf. A133687, A167625, A257493, A333330, A377060.

A129437 Number of isomorphism classes of 8-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 5, 22, 181, 2183, 47773, 1689841, 90972682, 6948008975, 721121538707, 98626660242232, 17361164959413148, 3857920886847174328, 1064590883337392451345, 359664321908847682542521, 146924560811224485478212220, 71778969194383385732028947007, 41528817306107485906955040499799

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436. [From _Jason Kimberley_, Nov 09 2009]

Column k=8 of A167625.

Cf. A129436, A129426, A129427, A129429, A129431, A129433, A129435.

a(n)=N\{S_n[S_8] * S_{4n}[S_2]\}. - Jason Kimberley, Nov 09 2009

Euler transform of A129436. - Andrew Howroyd, Mar 15 2020

Using equation (5.8) of Read 1959, McKay's terms verified by, and new term a(11) was computed by Jason Kimberley, Nov 09 2009
a(12)=N{S_12[S_8]*S_48[S_2]} was computed in MAGMA, on one processor of ARCSgrid at UNcle, using 17 GB virtual memory, over 49 real days, with 36 days processor time, by Jason Kimberley, Nov 29 2009
a(13)-a(18) from Andrew Howroyd, Mar 21 2020

A333397 Array read by antidiagonals: T(n,k) is the number of connected k-regular multigraphs on n unlabeled nodes, loops allowed, n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 2, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 1, 1, 3, 4, 5, 1, 0, 0, 1, 0, 3, 0, 10, 0, 1, 0, 0, 1, 1, 4, 9, 26, 28, 17, 1, 0, 0, 1, 0, 4, 0, 47, 0, 97, 0, 1, 0, 0, 1, 1, 5, 17, 91, 291, 639, 359, 71, 1, 0, 0, 1, 0, 5, 0, 149, 0, 2789, 0, 1635, 0, 1, 0, 0

Offset: 0

Andrew Howroyd, Mar 18 2020

This sequence can be derived from A167625 by inverse Euler transform.

			Array begins:
=========================================================
n\k | 0 1 2  3    4     5        6       7          8
----+----------------------------------------------------
  0 | 1 1 1  1    1     1        1       1          1 ...
  1 | 1 0 1  0    1     0        1       0          1 ...
  2 | 0 1 1  2    2     3        3       4          4 ...
  3 | 0 0 1  0    4     0        9       0         17 ...
  4 | 0 0 1  5   10    26       47      91        149 ...
  5 | 0 0 1  0   28     0      291       0       1934 ...
  6 | 0 0 1 17   97   639     2789   12398      44821 ...
  7 | 0 0 1  0  359     0    35646       0    1631629 ...
  8 | 0 0 1 71 1635 40264   622457 8530044   89057367 ...
  9 | 0 0 1  0 8296     0 14019433       0 6849428873 ...
  ...

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

Columns k=3..8 (with interspersed 0's for odd k) are: A005967, A085549, A129430, A129432, A129434, A129436.

Cf. A167625 (not necessarily connected), A322115 (not necessarily regular), A328682 (loopless), A333330.

Column k is the inverse Euler transform of column k of A167625.

A129431 Number of isomorphism classes of 5-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

3, 32, 727, 42703, 5988679, 1639714425, 757559332934, 541249158493444, 564262722366313620, 822164422526588575949, 1618567795242262158194706, 4188563149202582371775198174, 13926836449718334345103644635724, 58360974360850795591633858610837541

Offset: 1

Brendan McKay, Apr 15 2007

nonn

First seven terms were computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436. [From _Jason Kimberley_, Oct 05 2009]

Column k=5 of A167625.

Cf. A129430, A129420, A129427, A129429, A129433, A129435, A129437.

a(n) = N\{S_{2n}[S_5] * S_{5n}[S_2]\}. - Jason Kimberley, Oct 05 2009

Euler transform of A129430. - Andrew Howroyd, Mar 15 2020

Using equation (5.8) of Read 1959, new terms a(8)-a(10) were computed in MAGMA during 2009 by Jason Kimberley, Dec 22 2010

a(11)-a(14) from Andrew Howroyd, Mar 21 2020

A129433 Number of isomorphism classes of 6-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 4, 13, 66, 384, 3369, 40365, 675368, 14843787, 412444439, 14024069358, 570883006810, 27368160642418, 1525274952640101, 97766102550401217, 7141331463919539567, 589726897233157151109, 54669618693986578729541, 5653861386413841612952683, 648651469510725736002532451

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436. [From _Jason Kimberley_, Oct 05 2009]

Column k=6 of A167625.

Cf. A129432, A129422, A129427, A129429, A129431, A129435, A129437.

a(n) = N\{S_n[S_6] * S_{3n}[S_2]\}. [Equation (5.8) of Read 1959]

Euler transform of A129432. - Andrew Howroyd, Mar 15 2020

Using the formula, new terms a(13), Oct 05 2009, and a(14)-a(16), Nov 09 2009, were computed in MAGMA by Jason Kimberley

a(17)-a(20) from Andrew Howroyd, Mar 21 2020

A129435 Number of isomorphism classes of 7-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

4, 101, 12782, 8584767, 20104116089, 122644465172798, 1658339657066189475, 44564623565972592394826, 2193250056291167380214634054, 185389574171283940222059091478222

Offset: 1

Brendan McKay, Apr 15 2007

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

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

Column k=7 of A167625.

Cf. A129434, A129424, A129427, A129429, A129431, A129433, A129437.

a(n) = N\{S_{2n}[S_7] * S_{7n}[S_2]\}.

Euler transform of A129434. - Andrew Howroyd, Mar 15 2020

Using equation (5.8) of Read 1959, McKay's terms were verified by, and new term a(6) was computed by Jason Kimberley, Nov 09 2009

a(7)-a(10) from Andrew Howroyd, Mar 21 2020

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

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 1, 2, 5, 3, 1, 1, 0, 3, 0, 17, 0, 1, 1, 1, 3, 15, 47, 73, 15, 1, 1, 0, 4, 0, 138, 0, 388, 0, 1, 1, 1, 4, 34, 306, 2021, 4720, 2461, 105, 1, 1, 0, 5, 0, 670, 0, 43581, 0, 18155, 0, 1, 1, 1, 5, 65, 1270, 25050, 291001, 1295493, 1256395, 152531, 945, 1

Offset: 0

Andrew Howroyd, Mar 23 2020

			Array begins:
=============================================================
n\k | 0   1     2       3        4          5           6
----+--------------------------------------------------------
  0 | 1   1     1       1        1          1           1 ...
  1 | 1   0     1       0        1          0           1 ...
  2 | 1   1     2       2        3          3           4 ...
  3 | 1   0     5       0       15          0          34 ...
  4 | 1   3    17      47      138        306         670 ...
  5 | 1   0    73       0     2021          0       25050 ...
  6 | 1  15   388    4720    43581     291001     1594340 ...
  7 | 1   0  2461       0  1295493          0   159207201 ...
  8 | 1 105 18155 1256395 50752145 1296334697 23544232991 ...
  ...

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

Rows n=0..3 are A000012, A059841, A008619, A006003.
Columns k=0..4 are A000012, A123023, A002135, A005814, A005816.
Cf. A059441 (graphs), A167625 (unlabeled nodes), A333351 (without loops).

b:= proc(l, i) option remember; (n-> `if`(n=0, 1,
     `if`(l[n]=0, b(sort(subsop(n=[][], l)), n-1),
     `if`(i<1, 0, b(l, i-1)+`if`(i=n, `if`(l[n]>1,
      b(subsop(n=l[n]-2, l), i), 0), `if`(l[i]>0,
      b(subsop(i=l[i]-1, n=l[n]-1, l), i), 0))))))(nops(l))
    end:
A:= (n, k)-> b([k$n], n):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Mar 23 2020

b[l_, i_] := b[l, i] = Function[n, If[n == 0, 1, If[l[[n]] == 0, b[Sort[ ReplacePart[l, n -> Nothing]], n-1], If[i < 1, 0, b[l, i-1] + If[i == n, If[l[[n]] > 1, b[ReplacePart[l, n -> l[[n]]-2], i], 0], If[l[[i]] > 0, b[ReplacePart[l, {i -> l[[i]]-1, n -> l[[n]]-1}], i], 0]]]]]][Length[l]];
A[n_, k_] := b[Table[k, {n}], n];
Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Apr 07 2020, after Alois P. Heinz *)

MultigraphsWLByDegreeSeq(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], forstep(e=0, limit, 2, recurse(n-r, limit, src[i, 1], 0, src[i, 2], e)))); Mat(M);
}
T(n, k)={if(n%2&&k%2, 0, vecsum(MultigraphsWLByDegreeSeq(n, k, (p, r)->subst(deriv(p), x, 1)>=(n-2*r)*k)[, 2]))}
{ for(n=0, 8, for(k=0, 6, print1(T(n, k), ", ")); print) }

cp's OEIS Frontend

A129427 Number of isomorphism classes of 3-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Sage

Formula

Extensions

A129429 Number of isomorphism classes of 4-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A333733 Array read by antidiagonals: T(n,k) is the number of non-isomorphic n X n nonnegative integer matrices with all row and column sums equal to k up to permutations of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A129437 Number of isomorphism classes of 8-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A333397 Array read by antidiagonals: T(n,k) is the number of connected k-regular multigraphs on n unlabeled nodes, loops allowed, n >= 0, k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129431 Number of isomorphism classes of 5-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A129433 Number of isomorphism classes of 6-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A129435 Number of isomorphism classes of 7-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

Links