A333351 -id:A333351 - cp's OEIS frontend

A059441 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) giving number of regular labeled graphs with n nodes and degree k, read by rows.

1, 1, 1, 1, 0, 1, 1, 3, 3, 1, 1, 0, 12, 0, 1, 1, 15, 70, 70, 15, 1, 1, 0, 465, 0, 465, 0, 1, 1, 105, 3507, 19355, 19355, 3507, 105, 1, 1, 0, 30016, 0, 1024380, 0, 30016, 0, 1, 1, 945, 286884, 11180820, 66462606, 66462606, 11180820, 286884, 945, 1

Offset: 1

N. J. A. Sloane, Feb 01 2001

			1;
1,   1;
1,   0,       1;
1,   3,       3,        1;
1,   0,      12,        0,          1;
1,  15,      70,       70,         15,    1;
1,   0,     465,        0,        465,    0,   1;
1, 105,    3507,    19355,      19355, 3507, 105, 1;
1,   0,   30016,        0,    1024380, ...;
1, 945,  286884, 11180820,   66462606, ...;
1,   0, 3026655,        0, 5188453830, ...;

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 279.

Andrew Howroyd, Table of n, a(n) for n = 1..300 (rows 1..24)
Denis S. Krotov, [[2,10],[6,6]]-equitable partitions of the 12-cube, arXiv:2012.00038 [math.CO], 2020.
Brendan D. McKay, Applications of a technique for labeled enumeration, Congress. Numerantium, 40 (1983), 207-221. See page 216.
Wikipedia, Regular graph

Row sums are A295193.
Columns: A123023 (k=1), A001205 (k=2), A002829 (k=3, with alternating zeros), A005815 (k=4), A338978 (k=5, with alternating zeros), A339847 (k=6).
Cf. A051031 (unlabeled case), A324163 (connected case), A333351 (multigraphs).
Cf. A001147, A058891, A319189, A319190, A319612, A319729, A322635, A322659, A322698, A322704.

Table[SeriesCoefficient[Product[1+Times@@x/@s,{s,Subsets[Range[n],{2}]}],Sequence@@Table[{x[i],0,k},{i,n}]],{n,9},{k,0,n-1}] (* Gus Wiseman, Dec 24 2018 *)

for(n=1, 10, print(A059441(n))) \\ See A295193 for script, Andrew Howroyd, Aug 28 2019

a(37)-a(55) from Andrew Howroyd, Aug 25 2017

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

A002137 Number of n X n symmetric matrices with nonnegative integer entries, trace 0 and all row sums 2.

Original entry on oeis.org

1, 0, 1, 1, 6, 22, 130, 822, 6202, 52552, 499194, 5238370, 60222844, 752587764, 10157945044, 147267180508, 2282355168060, 37655004171808, 658906772228668, 12188911634495388, 237669544014377896, 4871976826254018760, 104742902332392298296

Offset: 0

N. J. A. Sloane

The definition implies that the matrices are symmetric, have entries 0, 1 or 2, have 0's on the diagonal, and the entries in each row or column sum to 2.
From Victor S. Miller, Apr 26 2013: (Start)
A002137 also is the number of monomials in the determinant of a generic n X n symmetric matrix with 0's on the diagonal (see the paper of Aitken).
It is also the number of monomials in the determinant of the Cayley-Menger matrix.  Even though this matrix is symmetric with 0's on the diagonal, it has 1's in the first row and column and so requires an extra argument. (End) [See the MathOverflow link for details of these bijections. - N. J. A. Sloane, Apr 27 2013]
From Bruce Westbury, Jan 22 2013: (Start)
It follows from the respective exponential generating functions that A002135 is the binomial transform of A002137:
A002135(n) = Sum_{k=0..n} C(n,k) * A002137(k),
2 = 1*1 + 2*0 + 1*1,
5 = 1*1 + 3*0 + 3*1 + 1*1,
17 = 1*1 + 4*0 + 6*1 + 4*1 + 1*6, ...
A002137 arises from looking at the dimension of the space of invariant tensors of the r-th tensor power of the adjoint representation of the symplectic group Sp(2n) (for n large compared to r). (End)
Also the number of subgraphs of a labeled K_n made up of cycles and isolated edges (but no isolated vertices). - Kellen Myers, Oct 17 2014

			a(2)=1 from
  02
  20
a(3)=1 from
  011
  101
  011
s(4)=6 from
  0200 0110
  2000 1001
  0002 1001
  0020 0110
  x3   x3

N. J. Calkin, J. E. Janoski, matrices of row and column sum 2, Congr. Numerantium 192 (2008) 19-32
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.8.

T. D. Noe, Table of n, a(n) for n = 0..100
A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 1-5.
A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 1-5. [Annotated scanned copy]
Jacob L. Bourjaily, Michael Plesser, and Cristian Vergu, The Many Colours of Amplitudes, arXiv:2412.21189 [hep-th], 2024. See pp. 17, 52.
Mark Colarusso, William Q. Erickson, and Jeb F. Willenbring, Contingency tables and the generalized Littlewood-Richardson coefficients, arXiv:2012.06928 [math.RT], 2020.
Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From _N. J. A. Sloane_, May 01 2012
I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.
Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
P. A. MacMahon, Combinations derived from m identical sets of n different letters and their connexion with general magic squares, Proc. London Math. Soc., 17 (1917), 25-41.
Victor S. Miller, The Cayley Menger Theorem and integer matrices with row sum 2 (on MathOverflow)
T. Muir, The Theory of Determinants in the Historical Order of Development, 4 vols., Macmillan, NY, 1906-1923. [Annotated scans of selected pages] See Vol. 3, p. 122.
Marko R. Riedel, Number of ways to derange n numbers ignoring direction, counted by Analytic Combinatorics (2024)

Column k=2 of A333351.
A diagonal of A260340.
Cf. A000985, A000986, A002135.

nxt[{n_,a_,b_,c_}]:={n+1,b,c,n(b+c)-n(n-1) a/2}; Drop[Transpose[ NestList[ nxt,{0,1,0,1},30]][[2]],2] (* Harvey P. Dale, Jun 12 2013 *)

x='x+O('x^66); Vec( serlaplace( (1-x)^(-1/2)*exp(-x/2+x^2/4) ) ) \\ Joerg Arndt, Apr 27 2013

E.g.f.: (1-x)^(-1/2)*exp(-x/2+x^2/4).
a(n) = (n-1)*(a(n-1)+a(n-2)) - (n-1)*(n-2)*a(n-3)/2.
a(n) ~ sqrt(2) * n^n / exp(n+1/4). - Vaclav Kotesovec, Feb 25 2014

A108243 a(n) = number of 3-regular (trivalent) multi-graphs without loops on 2n vertices; a(n) = number of symmetric 2n X 2n matrices with {0,1,2,3}-entries with row sum equal to 3 for each row and trace 0.

Original entry on oeis.org

1, 1, 10, 760, 190050, 103050570, 102359800620, 168076482974400, 424343374430075100, 1560473478516337885500, 8014685021084051980870200, 55595731825871742484530751200, 506777617936508379069463525671000, 5933390819918520195635187162608235000, 87521940468361373047495526366554342050000

Offset: 0

Marni Mishna, Jun 17 2005

nonn

			a(1)=1 is the graph on 1, 2 with three copies of the edge (1,2).
a(2)=10 are relabelings of the graphs on 1,2,3,4:
  K_4 x 1
  + {(1,2), (1,2), (1,3), (3,4), (3,4), (2,4)} x 6 relabelings
  + {(1,2), (1,2), (1,2), (3,4), (3,4), (3,4)} x 3 relabelings.

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

Even bisection of column k=3 of A333351.

Linear differential equation satisfied by exponential generating function: {D(F)(0) = 1, (41580*t^5-3780*t^4+120*t^2+33*t-3)*F(t) + (498960*t^6-162540*t^5-11340*t^4+3+1350*t^3-60*t+132*t^2)*(d/dt)F(t) + (831600*t^7-466200*t^6-30240*t^5+7410*t^4+44*t^3-81*t^2)*(d^2/dt^2)F(t) + (443520*t^8-352800*t^7-18144*t^6+7372*t^5-18*t^3)*(d^3/dt^3)F(t) + (95040*t^9-97920*t^8-3456*t^7+1992*t^6)*(d^4/dt^4)F(t) + (8448*t^10-10688*t^9-192*t^8+144*t^7)*(d^5/dt^5)F(t) + (256*t^11-384*t^10)*(d^6/dt^6)F(t),
with F(0) = 1, `@@`(D, 5)(F)(0) = 103050570, `@@`(D, 2)(F)(0) = 10, `@@`(D, 3)(F)(0) = 760, `@@`(D, 4)(F)(0) = 190050}
Linear recurrence satisfied by a(n): {(4989600 + 5718768*n^7 + 1045440*n^8 + 123200*n^9 + 8448*n^10 + 256*n^11 + 30135960*n + 75458988*n^2 + 105258076*n^3 + 91991460*n^4 + 53358140*n^5 + 21100464*n^6)*a(n) + (-19958400 - 1534368*n^7 - 182592*n^8 - 12608*n^9 - 384*n^10 - 75637440*n - 125414712*n^2 - 119890252*n^3 - 73239888*n^4 - 29906772*n^5 - 8276184*n^6)*a(n + 1) + (-4989600 - 5760*n^7 - 192*n^8 - 11840760*n - 12084468*n^2 - 6932520*n^3 - 2446668*n^4 - 544320*n^5 - 74592*n^6)*a(n + 2) + (1857240 + 144*n^7 + 3447358*n + 2724762*n^2 + 1186966*n^3 + 307470*n^4 + 47332*n^5 + 4008*n^6)*a(n + 3) + (5445 + 3289*n + 660*n^2 + 44*n^3)*a(n + 4) + (-3003 - 1635*n - 297*n^2 - 18*n^3)*a(n + 5) + 3*a(n + 6),
with a(0) = 1, a(1) = 1, a(2) = 10, a(3) = 760, a(4) = 190050, a(5) = 103050570}
a(n) ~ 2^(n + 1/2) * 3^n * n^(3*n) / exp(3*n). - Vaclav Kotesovec, Oct 24 2023

Definition corrected by Brendan McKay, Apr 02 2007

Terms a(13) and beyond from Andrew Howroyd, Mar 25 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) }

A244868 Number of symmetric 5 X 5 matrices of nonnegative integers with zeros on the main diagonal and every row and column adding to n.

Original entry on oeis.org

1, 22, 158, 654, 1980, 4906, 10577, 20588, 37059, 62710, 100936, 155882, 232518, 336714, 475315, 656216, 888437, 1182198, 1548994, 2001670, 2554496, 3223242, 4025253, 4979524, 6106775, 7429526, 8972172, 10761058, 12824554, 15193130, 17899431, 20978352, 24467113, 28405334, 32835110, 37801086

Offset: 0

N. J. A. Sloane, Jul 07 2014

Colin Barker, Table of n, a(n) for n = 0..1000
R. P. Stanley, Examples of Magic Labelings, Unpublished Notes, 1973 [Cached copy, with permission]
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Even bisection of row n=5 of A333351.

Cf. A053494.

Vec((1 + 16*x + 41*x^2 + 16*x^3 + x^4) / (1 - x)^6 + O(x^40)) \\ Colin Barker, Jan 11 2017

G.f.: (1 + 16*x + 41*x^2 + 16*x^3 + x^4) / (1 - x)^6.
From Colin Barker, Jan 11 2017: (Start)
a(n) = (24 + 94*n + 165*n^2 + 155*n^3 + 75*n^4 + 15*n^5) / 24.
a(n) = 6*a(n-1) - 15*a(n-2) + 20*a(n-3) - 15*a(n-4) + 6*a(n-5) - a(n-6) for n>5.
(End)

A244878 Number of 6 X 6 traceless symmetric magic squares with magic sum n.

Original entry on oeis.org

1, 15, 130, 760, 3355, 12043, 36935, 100135, 245870, 556580, 1177295, 2351165, 4469610, 8141210, 14284170, 24247962, 39970575, 64178685, 100639000, 154470030, 232524589, 343854445, 500269705, 717006745, 1013519780, 1414412506, 1950527645, 2660213675, 3590789540, 4800229700

Offset: 0

N. J. A. Sloane, Jul 08 2014

Colin Barker, Table of n, a(n) for n = 0..1000
R. P. Stanley, Examples of Magic Labelings, Unpublished Notes, 1973 [Cached copy, with permission]
Index entries for linear recurrences with constant coefficients, signature (9,-35,75,-90,42,42,-90,75,-35,9,-1).

Row n=6 of A333351.

LinearRecurrence[{9,-35,75,-90,42,42,-90,75,-35,9,-1},{1,15,130,760,3355,12043,36935,100135,245870,556580,1177295},30] (* Harvey P. Dale, Jul 18 2024 *)

Vec((1 + 6*x + 30*x^2 + 40*x^3 + 30*x^4 + 6*x^5 + x^6) / ((1 - x)^10*(1 + x)) + O(x^30)) \\ Colin Barker, Jan 12 2017

G.f.: (1 + 6*x + 30*x^2 + 40*x^3 + 30*x^4 + 6*x^5 + x^6) / ((1 - x)^10*(1 + x)).

a(n) = (945*(507+5*(-1)^n) + 1480896*n + 2062800*n^2 + 1747040*n^3 + 989100*n^4 + 383628*n^5 + 100800*n^6 + 17160*n^7 + 1710*n^8 + 76*n^9) / 483840. - Colin Barker, Jan 12 2017

A367497 Number of 4-regular loopless multigraphs on n vertices.

Original entry on oeis.org

1, 0, 1, 1, 15, 158, 3355, 93708, 3535448, 170816680, 10307577384, 759439940230, 67095584693434, 7001532238614324, 851997581131397870, 119582892039683711842, 19176016845387328919910, 3484133398830462852182192, 712017802878894004029129622, 162597177988359237252433594350

Offset: 0

Arick Grootveld, Nov 20 2023

nonn

Also this is the number of unique polynomials that can be created from products of differences between n terms, such that the polynomial expansion includes each term to the 4th power.

			For n=2, the only polynomial is: (x_1 - x_2)^4.
Which corresponds to the following adjacency matrix:
 [0,4
  4,0].
For n=3, the only polynomial is: (x_1 - x_2)^2 * (x_1 - x_3)^2 * (x_2 - x_3)^2.
Which corresponds to the following adjacency matrix:
 [0, 2, 2
  2, 0, 2
  2, 2, 0].
For n=4, an example of a polynomial would be (x_1 - x_3)^3 * (x_1 - x_4)^1 * (x_2 - x_3)^1 * (x_2 - x_4)^3 = (x_1^4 * x_2^4) + (x_3^4 * x_4^4) + ... + {other polynomial terms}.
And this corresponds to the following adjacency matrix:
 [0, 0, 3, 1
  0, 0, 1, 3
  3, 1, 0, 0
  1, 3, 0, 0].

Column k=4 of A333351.

Cf. A000217.

cp's OEIS Frontend

A059441 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) giving number of regular labeled graphs with n nodes and degree k, read by rows.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

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

A002137 Number of n X n symmetric matrices with nonnegative integer entries, trace 0 and all row sums 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A108243 a(n) = number of 3-regular (trivalent) multi-graphs without loops on 2n vertices; a(n) = number of symmetric 2n X 2n matrices with {0,1,2,3}-entries with row sum equal to 3 for each row and trace 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A244868 Number of symmetric 5 X 5 matrices of nonnegative integers with zeros on the main diagonal and every row and column adding to n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A244878 Number of 6 X 6 traceless symmetric magic squares with magic sum n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A367497 Number of 4-regular loopless multigraphs on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs