A333330 -id:A333330 - cp's OEIS frontend

A328682 Array read by antidiagonals: T(n,r) is the number of connected r-regular loopless multigraphs on n unlabeled nodes.

1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0, 1, 0, 3, 0, 1, 0, 0, 1, 0, 1, 1, 4, 6, 6, 1, 0, 0, 1, 0, 1, 0, 6, 0, 19, 0, 1, 0, 0, 1, 0, 1, 1, 7, 15, 49, 50, 20, 1, 0, 0, 1, 0, 1, 0, 9, 0, 120, 0, 204, 0, 1, 0, 0, 1, 0, 1, 1, 11, 36, 263, 933, 1689, 832, 91, 1, 0, 0, 1, 0, 1, 0, 13, 0, 571, 0, 13303, 0, 4330, 0, 1, 0, 0, 1, 0, 1, 1, 15, 72, 1149, 12465, 90614, 252207, 187392, 25227, 509, 1, 0, 0

Offset: 0

Natan Arie Consigli, Dec 17 2019

Initial terms computed using 'Nauty and Traces' (see the link).
T(0,r) = 1 because the "nodeless" graph has zero (therefore in this case all) nodes of degree r (for any r).
T(1,0) = 1 because only the empty graph on one node is 0-regular on 1 node.
T(1,r) = 0, for r>0: there's only one node and loops aren't allowed.
T(2,r) = 1, for r>0 since the only edges that are allowed are between the only two nodes.
T(3,r) = parity of r, for r>0. There are no such graphs of odd degree and for an even degree the only multigraph satisfying that condition is the regular triangular multigraph.
T(n,0) = 0, for n>1 because graphs having more than a node of degree zero are disconnected.
T(n,1) = 0, for n>2 since any connected graph with more than two nodes must have a node of degree greater than two.
T(n,2) = 1, for n>1: the only graphs satisfying that condition are the cyclic graphs of order n.
This sequence may be derived from A333330 by inverse Euler transform. - Andrew Howroyd, Mar 15 2020

			Square matrix T(n,r) begins:
========================================================
n\r | 0     1     2     3     4     5      6      7
----+---------------------------------------------------
  0 | 1,    1,    1,    1,    1,    1,     1,     1, ...
  1 | 1,    0,    0,    0,    0,    0,     0,     0, ...
  2 | 0,    1,    1,    1,    1,    1,     1,     1, ...
  3 | 0,    0,    1,    0,    1,    0,     1,     0, ...
  4 | 0,    0,    1,    2,    3,    4,     6,     7, ...
  5 | 0,    0,    1,    0,    6,    0,    15,     0, ...
  6 | 0,    0,    1,    6,   19,   49,   120,   263, ...
  7 | 0,    0,    1,    0,   50,    0,   933,     0, ...
  8 | 0,    0,    1,   20,  204, 1689, 13303, 90614, ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..350
Brendan McKay and Adolfo Piperno, Nauty and Traces

Rows n=3..9 are: A000035, A253186, A324221, A324218, A324217, A325474, A327604.
Columns r=3..8 are: A000421, A129417, A129419, A129421, A129423, A129425.
Cf. A289986 (main diagonal), A333330 (not necessarily connected), A333397.

# This program will execute the "else echo" line if the graph is nontrivial (first three columns, first two rows or both row and column indices are odd)
for ((i=0; i<16; i++)); do
n=0
r=${i}
while ((n<=i)); do
if( (((r==0)) && ((n==0)) ) || ( ((r==0)) && ((n==1)) ) || ( ((r==1)) && ((n==2)) ) || ( ((r==2)) && !((n==1)) ) ); then
echo 1
elif( ((n==0)) || ((n==1)) || ((r==0)) || ((r==1)) || (! ((${r}%2 == 0)) && ! ((${n}%2 == 0)) || ( ((r==2)) && ((n==1)) )) ); then
echo 0
else echo $(./geng -c -d1 ${n} -q | ./multig -m${r} -r${r} -u 2>&1 | cut -d ' ' -f 7 | grep -v '^$');  fi;
((n++))
((r--))
done
done

Column r is the inverse Euler transform of column r of A333330. - Andrew Howroyd, Mar 15 2020

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.

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

Original entry on oeis.org

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

Jason Kimberley, Nov 07 2009

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

			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 ...
  ...

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.

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).

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

A129416 Number of isomorphism classes of 3-regular loopless multigraphs of order 2n.

Original entry on oeis.org

1, 3, 9, 32, 135, 709, 4637, 38374, 391473, 4764778, 66913591, 1056886475, 18446472265, 351482430368, 7247888726269, 160671989129665, 3808499268504548, 96094161981827499, 2570930535917564366, 72688753062897675445

Offset: 1

Brendan McKay, Apr 15 2007

nonn

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

L. Travis, Graphical Enumeration: A Species-Theoretic Approach, arXiv:math/9811127 [math.CO], 1998.; Ph.D. thesis, Brandeis University, 1999, Section 4.3.

Column k=3 of A333330.

Cf. A000421 (connected, inv. Eul. trans.), A129427, A129418, A129420, A129422, A129424, A129426.

Euler transform of A000421.

a(13)-a(20) from Andrew Howroyd, Mar 19 2020

A129426 Number of isomorphism classes of 8-regular loopless multigraphs of order n.

Original entry on oeis.org

0, 1, 1, 10, 37, 582, 12511, 543779, 35255015, 3230979297, 397550237967, 63834143947661, 13080849749829233, 3358751856150607392, 1063851391062768324862, 410060430118305494628648, 190065946515113295597969794, 104826174445642584491349328181

Offset: 1

Brendan McKay, Apr 15 2007

nonn

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

Column k=8 of A333330.

Cf. A129425, A129437, A129416, A129418, A129420, A129422, A129424.

Euler transform of A129425. - Andrew Howroyd, Mar 17 2020

a(1)=0 prepended and a(12)-a(18) from Andrew Howroyd, Mar 17 2020

A333351 Array read by antidiagonals: T(n,k) is the number of k-regular loopless multigraphs on n labeled 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, 3, 1, 1, 0, 1, 0, 6, 0, 1, 1, 0, 1, 1, 10, 22, 15, 1, 1, 0, 1, 0, 15, 0, 130, 0, 1, 1, 0, 1, 1, 21, 158, 760, 822, 105, 1, 1, 0, 1, 0, 28, 0, 3355, 0, 6202, 0, 1, 1, 0, 1, 1, 36, 654, 12043, 93708, 190050, 52552, 945, 1, 1, 0, 1, 0, 45, 0, 36935, 0, 3535448, 0, 499194, 0, 1

Offset: 0

Andrew Howroyd, Mar 15 2020

			Array begins:
=================================================================
n\k | 0   1    2      3       4        5         6          7
----+------------------------------------------------------------
  0 | 1   1    1      1       1        1         1          1 ...
  1 | 1   0    0      0       0        0         0          0 ...
  2 | 1   1    1      1       1        1         1          1 ...
  3 | 1   0    1      0       1        0         1          0 ...
  4 | 1   3    6     10      15       21        28         36 ...
  5 | 1   0   22      0     158        0       654          0 ...
  6 | 1  15  130    760    3355    12043     36935     100135 ...
  7 | 1   0  822      0   93708        0   3226107          0 ...
  8 | 1 105 6202 190050 3535448 45163496 431400774 3270643750 ...
  ...

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

Rows n=4..6 are A000217(n+1), A244868 (with interspersed zeros), A244878.
Columns k=0..4 are A000012, A123023, A002137, A108243 (with interspersed zeros), A367497.
Cf. A059441 (graphs), A333157, A333330 (unlabeled nodes), A333467 (with loops).

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

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.

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

Original entry on oeis.org

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

Offset: 0

Andrew Howroyd, Apr 08 2020

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.

			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 ...
  5 | 1 3 16  60  243   800   2518    6999 ...
  6 | 1 4 29 184 1228  7252  38194  175369 ...
  7 | 1 4 45 488 6684 78063 772243 6254652 ...
  ...

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

Rows n=0..4 are A000012, A000012, A000027(n+1), A006918(n+1), A333897.
Columns k=0..5 are A000012, A008619, A000990, A333894, A333895, A333896.
Cf. A188403, A192517, A263293, A333161, A333330, A333737, A334546.

A129418 Number of isomorphism classes of 4-regular loopless multigraphs of order n.

Original entry on oeis.org

1, 0, 1, 1, 4, 7, 24, 60, 240, 930, 4701, 26637, 178569, 1339529, 11187064, 101871881, 1002594996, 10574095327, 118850827173, 1417140114336, 17860018997346, 237160827107408, 3309078044759285, 48396906463199522, 740331404753448181, 11821525310570525197

Offset: 0

Brendan McKay, Apr 15 2007

nonn

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

Also number of carbon allotropes satisfying the octet rule, excluding stereoisomers. - Natan Arie Consigli, Jun 06 2017

Column k=4 of A333330.

Cf. A129417, A129429, A129416, A129420, A129422, A129424, A129426.

geng -d1 ${n} -q | multig -r4 -u # Natan Arie Consigli, Jun 06 2017

Euler transform of A129417. - Andrew Howroyd, Mar 14 2020

a(0)-a(1) by Natan Arie Consigli, Jun 06 2017

a(18)-a(25) from Andrew Howroyd, Mar 17 2020

A129420 Number of isomorphism classes of 5-regular loopless multigraphs of order 2n.

Original entry on oeis.org

1, 5, 54, 1753, 189341, 46935710, 20494522535, 14041749098602, 14155266802426836, 20061744131278672638, 38587417589460488631726, 97900485588988429336271590, 320012505326477694925887757141, 1321269556386383657509085883067690, 6775074159053505093089897813890701467

Offset: 1

Brendan McKay, Apr 15 2007

nonn

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

Column k=5 of A333330.

Cf. A129419, A129431, A129416, A129418, A129422, A129424, A129426.

Euler transform of A129419. - Andrew Howroyd, Mar 17 2020

a(8)-a(15) from Andrew Howroyd, Mar 21 2020

cp's OEIS Frontend

A328682 Array read by antidiagonals: T(n,r) is the number of connected r-regular loopless multigraphs on n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

Formula

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129416 Number of isomorphism classes of 3-regular loopless multigraphs of order 2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A129426 Number of isomorphism classes of 8-regular loopless multigraphs of order n.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A129418 Number of isomorphism classes of 4-regular loopless multigraphs of order n.

Views

Author

Keywords

Comments

Crossrefs

Programs

nauty