A322635 -id:A322635 - cp's OEIS frontend

A322661 Number of graphs with loops spanning n labeled vertices.

1, 1, 5, 45, 809, 28217, 1914733, 254409765, 66628946641, 34575388318705, 35680013894626133, 73392583417010454429, 301348381381966079690489, 2471956814761996896091805993, 40530184362443281653842556898237, 1328619783326799871943604598592805525

Offset: 0

Gus Wiseman, Dec 22 2018

nonn

The span of a graph is the union of its edges.

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

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

Cf. A000666, A006125, A006129 (loops not allowed), A054921, A062740, A116539, A320461, A322635, A048291 (for directed edgs).

Table[Sum[(-1)^(n-k)*Binomial[n,k]*2^Binomial[k+1,2],{k,0,n}],{n,10}]
(* second program *)
Table[Select[Expand[Product[1+x[i]*x[j],{j,n},{i,j}]],And@@Table[!FreeQ[#,x[i]],{i,n}]&]/.x[_]->1,{n,7}]

a(n) = sum(k=0, n, (-1)^(n-k)*binomial(n,k)*2^binomial(k+1,2)) \\ Andrew Howroyd, Jan 06 2024

Exponential transform of A062740, if we assume A062740(1) = 1.

Inverse binomial transform of A006125(n+1) = 2^binomial(n+1,2).

A322700 Number of unlabeled graphs with loops spanning n vertices.

Original entry on oeis.org

1, 1, 4, 14, 70, 454, 4552, 74168, 2129348, 111535148, 10812483376, 1945437208224, 650378721156736, 404749938336404704, 470163239887698967104, 1022592854829028311090816, 4177826139658552046627175072, 32163829440870460348768023969632

Offset: 0

Gus Wiseman, Dec 23 2018

nonn

The span of a graph is the union of its edges. The not necessarily spanning case is A000666.

Andrew Howroyd, Table of n, a(n) for n = 0..80
Gus Wiseman, Non-isomorphic representatives of the a(4) = 70 spanning graphs with loops.

Cf. A000666, A006125, A006129, A054921, A062740, A320461, A322635, A322661.

Table[Sum[2^PermutationCycles[Ordering[Map[Sort,Select[Tuples[Range[n],2],OrderedQ]/.Rule@@@Table[{i,prm[[i]]},{i,n}],{1}]],Length],{prm,Permutations[Range[n]]}]/n!,{n,0,8}]//Differences (* Mathematica 8.0+ *)

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A322700(n): return int(sum(Fraction(1<>1)+1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))-sum(Fraction(1<>1)+1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n-1))) if n else 1 # Chai Wah Wu, Jul 14 2024

First differences of A000666.

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.

Original entry on oeis.org

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

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

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

A370165 Number of labeled loop-graphs covering n vertices without a non-loop edge with loops at both ends.

Original entry on oeis.org

1, 1, 4, 29, 400, 10289, 496548, 45455677, 7983420736, 2716094133313, 1803251169342820, 2348787270663723581, 6024912118926389490448, 30516957491540079828757553, 305811332460677494410532494660, 6071677788061208810793717466942237

Offset: 0

Gus Wiseman, Feb 12 2024

nonn

Number of ways to choose a stable vertex set of a simple graph with n vertices.

			The a(3) = 29 loop-graphs (loops shown as singletons):
  {1,23}   {1,2,3}     {1,2,13,23}
  {2,13}   {1,2,13}    {1,3,12,23}
  {3,12}   {1,2,23}    {2,3,12,13}
  {12,13}  {1,3,12}    {1,12,13,23}
  {12,23}  {1,3,23}    {2,12,13,23}
  {13,23}  {2,3,12}    {3,12,13,23}
           {2,3,13}
           {1,12,13}
           {1,12,23}
           {1,13,23}
           {2,12,13}
           {2,12,23}
           {2,13,23}
           {3,12,13}
           {3,12,23}
           {3,13,23}
           {12,13,23}

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

Without loops we have A006129, connected A001187.
The non-covering version is A079491.
The unlabeled version is A370166, non-covering A339832.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 counts labeled loop-graphs (shifted left), covering A322661.
Cf. A048291, A062740, A116539, A320461, A322635.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Union@@#==Range[n]&&!MatchQ[#, {_,{x_},_,{y_},_,{x_,y_},_}]&]],{n,0,5}]

seq(n)={Vec(serlaplace(sum(k=0, n, exp((2^k-1)*x + O(x*x^n))*2^(k*(k-1)/2)*x^k/k!)))} \\ Andrew Howroyd, Feb 20 2024

Inverse binomial transform of A079491.

E.g.f.: Sum_{k >= 0} exp((2^k-1)*x)*2^(k*(k-1)/2)*x^k/k!. - Andrew Howroyd, Feb 20 2024

cp's OEIS Frontend

A322661 Number of graphs with loops spanning n labeled vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A322700 Number of unlabeled graphs with loops spanning n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

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

A370165 Number of labeled loop-graphs covering n vertices without a non-loop edge with loops at both ends.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula