A059441 -id:A059441 - cp's OEIS frontend

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.

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

A324163 Triangle read by rows: T(n,k) is the number of connected k-regular simple graphs on n labeled vertices, (0 <= k < n).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 3, 1, 0, 0, 12, 0, 1, 0, 0, 60, 70, 15, 1, 0, 0, 360, 0, 465, 0, 1, 0, 0, 2520, 19320, 19355, 3507, 105, 1, 0, 0, 20160, 0, 1024380, 0, 30016, 0, 1, 0, 0, 181440, 11166120, 66462480, 66462606, 11180820, 286884, 945, 1

Offset: 1

Andrew Howroyd, Sep 02 2019

			Triangle begins:
  1;
  0, 1;
  0, 0,     1;
  0, 0,     3,     1;
  0, 0,    12,     0,       1;
  0, 0,    60,    70,      15,    1;
  0, 0,   360,     0,     465,    0,     1;
  0, 0,  2520, 19320,   19355, 3507,   105, 1;
  0, 0, 20160,     0, 1024380,    0, 30016, 0, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..210

Column k=2 is A001710(n-1) for n >= 3.
Column k=3 is aerated A004109.
Column k=4 is A272905.
Row sums are A322659.
Cf. A059441 (not necessarily connected), A068934 (unlabeled).

Column k is the logarithmic transform of column k of A059441.

A322659 Number of connected regular simple graphs on n labeled vertices.

Original entry on oeis.org

1, 1, 1, 4, 13, 146, 826, 44808, 1074557, 155741296, 10381741786, 6939251270348, 2203360264480750, 4186526735251514044, 3747344007864300197810, 35041787059621536192399824, 156277111373298355107598128061, 4142122641757597729416733678931968

Offset: 1

Gus Wiseman, Dec 22 2018

nonn

A graph is regular if all vertices have the same degree.

Gus Wiseman, The a(5) = 13 connected regular simple graphs.
Gus Wiseman, The a(6) = 146 connected regular simple graphs.

Row sums of A324163.

Cf. A054921, A059441, A062740, A295193, A299353, A305078, A319190, A319612, A319729, A322635.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[If[n==1,1,Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],SameQ@@Length/@Split[Sort[Join@@#]],Length[csm[#]]==1]&]]],{n,6}]

a(8)-a(15) from Andrew Howroyd, Dec 23 2018

a(16)-a(18) from Andrew Howroyd, Sep 02 2019

A322704 Number of regular hypergraphs on n labeled vertices with no singletons.

Original entry on oeis.org

1, 1, 2, 4, 80, 209944

Offset: 0

Gus Wiseman, Dec 23 2018

We define a hypergraph to be any finite set of finite nonempty sets. A hypergraph is regular if all vertices have the same degree.

			The a(3) = 4 edge-sets:
  {}
  {{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Cf. A058891, A059441, A295193, A306021, A319189, A319190, A319612, A319729, A322698.

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s,{s,Subsets[Range[n],{2,n}]}],Sequence@@Table[{x[i],0,k},{i,n}]],{k,0,2^n-n-1}],{n,1,5}]

A339847 The number of labeled 6-regular graphs on n nodes.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 105, 30016, 11180820, 5188453830, 2977635137862, 2099132870973600, 1803595358964773088, 1872726690127181663775, 2329676580698022197516875, 3443086402825299720403673760, 5997229769947050271535917422040, 12218901113752712984458458475480428

Offset: 0

Atabey Kaygun, Dec 21 2020

nonn

Marni Mishna, Table of n, a(n) for n = 0..195 (terms 0..36 from Andrew Howroyd, terms 37..40 from Atabey Kaygun)
Frédéric Chyzak and Marni Mishna Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction-based approach, arXiv:2406.04753 [math.CO], 2024.
Atabey Kaygun, Counting Graphs with a Prescribed Degree Sequence.
Atabey Kaygun, Common LISP program that generates the sequence.
Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.
Marni Mishna, Maple code to generate terms.

Column k=6 of A059441.

Cf. A165627 (unlabeled case), A295193.

\\ Needs GraphsByDegreeSeq from links in A295193.
a(n)={my(M=GraphsByDegreeSeq(n, 6, (p,r)->6-valuation(p,x) <= r)); if(n>=7, vecsum(M[,2]), n==0)} \\ Andrew Howroyd, Dec 26 2020

Terms a(14) and beyond from Andrew Howroyd, Dec 26 2020

A351263 Triangle read by rows: T(n,k) is the number of oriented graphs on n labeled nodes whose underlying graph is k-regular, k = 0..n-1.

Original entry on oeis.org

1, 1, 2, 1, 0, 8, 1, 12, 48, 64, 1, 0, 384, 0, 1024, 1, 120, 4480, 35840, 61440, 32768, 1, 0, 59520, 0, 7618560, 0, 2097152, 1, 1680, 897792, 79278080, 1268449280, 3677356032, 1761607680, 268435456, 1, 0, 15368192, 0, 268535070720, 0, 4028679323648, 0, 68719476736

Offset: 1

Andrew Howroyd, Feb 05 2022

The sum of the in-degree and out-degree at each node is k.

			Triangle begins:
  1;
  1,   2;
  1,   0,     8;
  1,  12,    48,    64;
  1,   0,   384,     0,    1024;
  1, 120,  4480, 35840,   61440, 32768;
  1,   0, 59520,     0, 7618560,     0, 2097152;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..300 (rows 1..24)

Row sums are A351264.
Main diagonal is A006125.
The unlabeled version is A350912.
Cf. A059441 (graphs).

T(n,k) = A059441(n,k)*2^(n*k/2). - Pontus von Brömssen, Apr 04 2022

A322705 Number of k-uniform k-regular hypergraphs spanning n vertices, for some 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 5, 26, 472, 23342

Offset: 0

Gus Wiseman, Dec 23 2018

We define a hypergraph to be any finite set of finite nonempty sets. A hypergraph is k-uniform if all edges contain exactly k vertices, and k-regular if all vertices belong to exactly k edges. The span of a hypergraph is the union of its edges.

			The a(3) = 2 hypergraphs:
  {{1},{2},{3}}
  {{1,2},{1,3},{2,3}}
The a(4) = 5 hypergraphs:
  {{1},{2},{3},{4}}
  {{1,2},{1,3},{2,4},{3,4}}
  {{1,2},{1,4},{2,3},{3,4}}
  {{1,3},{1,4},{2,3},{2,4}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
The a(5) = 26 hypergraphs:
  {{1},{2},{3},{4},{5}}
  {{1,2},{1,3},{2,4},{3,5},{4,5}}
  {{1,2},{1,3},{2,5},{3,4},{4,5}}
  {{1,2},{1,4},{2,3},{3,5},{4,5}}
  {{1,2},{1,4},{2,5},{3,4},{3,5}}
  {{1,2},{1,5},{2,3},{3,4},{4,5}}
  {{1,2},{1,5},{2,4},{3,4},{3,5}}
  {{1,3},{1,4},{2,3},{2,5},{4,5}}
  {{1,3},{1,4},{2,4},{2,5},{3,5}}
  {{1,3},{1,5},{2,3},{2,4},{4,5}}
  {{1,3},{1,5},{2,4},{2,5},{3,4}}
  {{1,4},{1,5},{2,3},{2,4},{3,5}}
  {{1,4},{1,5},{2,3},{2,5},{3,4}}
  {{1,2,3},{1,2,4},{1,3,5},{2,4,5},{3,4,5}}
  {{1,2,3},{1,2,4},{1,4,5},{2,3,5},{3,4,5}}
  {{1,2,3},{1,2,5},{1,3,4},{2,4,5},{3,4,5}}
  {{1,2,3},{1,2,5},{1,4,5},{2,3,4},{3,4,5}}
  {{1,2,3},{1,3,4},{1,4,5},{2,3,5},{2,4,5}}
  {{1,2,3},{1,3,5},{1,4,5},{2,3,4},{2,4,5}}
  {{1,2,4},{1,2,5},{1,3,4},{2,3,5},{3,4,5}}
  {{1,2,4},{1,2,5},{1,3,5},{2,3,4},{3,4,5}}
  {{1,2,4},{1,3,4},{1,3,5},{2,3,5},{2,4,5}}
  {{1,2,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5}}
  {{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,4,5}}
  {{1,2,5},{1,3,4},{1,4,5},{2,3,4},{2,3,5}}
  {{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}

Row sums of A322706.

Cf. A005176, A058891, A059441, A116539, A295193, A299353, A306021, A319056, A319189, A319190, A319612, A321721, A322704.

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s,{s,Subsets[Range[n],{k}]}],Sequence@@Table[{x[i],0,k},{i,n}]],{k,1,n}],{n,1,6}]

A333158 Irregular triangle read by rows: T(n,k) is the number of k-regular graphs on n labeled nodes with loops allowed, n >= 1, 0 <= k <= n + 1.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 3, 8, 8, 3, 1, 1, 0, 38, 0, 38, 0, 1, 1, 15, 208, 730, 730, 208, 15, 1, 1, 0, 1348, 0, 20670, 0, 1348, 0, 1, 1, 105, 10126, 188790, 781578, 781578, 188790, 10126, 105, 1, 1, 0, 86174, 0, 37885204, 0, 37885204, 0, 86174, 0, 1

Offset: 1

Andrew Howroyd, Mar 09 2020

A loop adds 2 to the degree of its vertex.

			Triangle begins:
  1,   0,     1;
  1,   1,     1,      1;
  1,   0,     2,      0,      1;
  1,   3,     8,      8,      3,      1;
  1,   0,    38,      0,     38,      0,      1;
  1,  15,   208,    730,    730,    208,     15,     1;
  1,   0,  1348,      0,  20670,      0,   1348,     0,   1;
  1, 105, 10126, 188790, 781578, 781578, 188790, 10126, 105, 1;
  ...

Row sums are A322635.
Columns k=0..4 are A000012, A123023, A108246, A110039 (with interspersed zeros), A228697.
Cf. A059441, A333157.

T(n,k) = T(n, n+1-k).

A338978 Number of labeled 5-regular graphs on 2n nodes.

Original entry on oeis.org

1, 0, 0, 1, 3507, 66462606, 2977635137862, 283097260184159421, 52469332407700365320163, 17647883828569858659972268092, 10148613081040117624319536901932188, 9494356410654311931931879706070629989407, 13859154719468565627065764000731047706917194485

Offset: 0

Atabey Kaygun, Dec 18 2020

nonn

Marni Mishna, Table of n, a(n) for n = 0..110 (first 51 terms from Brendan Mackay)
Frédéric Chyzak and Marni Mishna, Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction based approach, arXiv:2406.04753 [math.CO], 2024.
Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 9.
Atabey Kaygun, Counting Graphs with a Prescribed Degree Sequence.
Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.

With interspersed zeros, column k=5 of A059441.

Cf. A001205, A002829, A005815, A165626 (unlabeled case).

A322555 Number of labeled simple graphs on n vertices where all non-isolated vertices have the same degree.

Original entry on oeis.org

1, 1, 2, 5, 18, 69, 390, 2703, 59474, 1548349, 168926258, 12165065351, 7074423247562, 2294426405580191, 4218009215702391954, 3810376434461484994317, 35102248193591661086921250, 156873334244228518638713087133, 4144940994226400702145709978234154

Offset: 0

Gus Wiseman, Dec 15 2018

nonn

Such graphs may be said to have regular support.

			The a(4) = 18 edge sets:
  {}
  {{1,2}}
  {{1,3}}
  {{1,4}}
  {{2,3}}
  {{2,4}}
  {{3,4}}
  {{1,2},{3,4}}
  {{1,3},{2,4}}
  {{1,4},{2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,4},{2,4}}
  {{1,3},{1,4},{3,4}}
  {{2,3},{2,4},{3,4}}
  {{1,2},{1,3},{2,4},{3,4}}
  {{1,2},{1,4},{2,3},{3,4}}
  {{1,3},{1,4},{2,3},{2,4}}
  {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

Cf. A000569, A005176, A038041, A059441, A295193, A306017, A306019, A319169, A320458.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],SameQ@@Length/@Split[Sort[Join@@#]]&]],{n,6}]

a(n) = 1 + Sum_{k=1..n} binomial(n, k)*(A295193(k) - 1). - Andrew Howroyd, Dec 17 2018

a(8)-a(15) from Andrew Howroyd, Dec 17 2018

a(16)-a(18) from Andrew Howroyd, May 21 2020

cp's OEIS Frontend

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

A324163 Triangle read by rows: T(n,k) is the number of connected k-regular simple graphs on n labeled vertices, (0 <= k < n).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A322659 Number of connected regular simple graphs on n labeled vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A322704 Number of regular hypergraphs on n labeled vertices with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A339847 The number of labeled 6-regular graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A351263 Triangle read by rows: T(n,k) is the number of oriented graphs on n labeled nodes whose underlying graph is k-regular, k = 0..n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A322705 Number of k-uniform k-regular hypergraphs spanning n vertices, for some 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A333158 Irregular triangle read by rows: T(n,k) is the number of k-regular graphs on n labeled nodes with loops allowed, n >= 1, 0 <= k <= n + 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A338978 Number of labeled 5-regular graphs on 2n nodes.

Views

Author

Keywords

Links

Crossrefs