A059167 -id:A059167 - cp's OEIS frontend

A277074 Number of n-node labeled graphs with three endpoints.

0, 0, 0, 4, 80, 1860, 64680, 3666600, 354093264, 59372032440, 17572209206640, 9347625940951980, 9099961952914672840, 16480899322963497105684, 56311549004017312945310280, 367105988116570172056739960080

Offset: 1

Marko Riedel, Sep 27 2016

nonn

F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 31, problem 1.16(a).

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marko R. Riedel, Geoffrey Critzer, Math.Stackexchange.com, Proof of the closed form of the e.g.f. by combinatorial species.

Column k=3 of A327369.

Cf. A059167, A277072, A277073.

MX := 16:
XGF := exp(z^2/2)*add((z/exp(z))^n*2^binomial(n,2)/n!, n=0..MX+5):
K1 := 1/6*z^4/(1-z)^3*XGF:
K2 := 1/2*z^4/(1-z)^2*(diff(XGF,z)-XGF):
K3 := 1/6*z^6/(1-z)^3*(diff(XGF, z$3)-3*diff(XGF, z$2)+3*diff(XGF,z)-XGF):
K4 := 1/2*z^5/(1-z)^4*(diff(XGF, z$2)-2*diff(XGF,z)+XGF):
K5 := 1/6*z^4/(1-z)^4*(diff(XGF,z)-XGF):
K6 := 1/2*z^5/(1-z)^5*(diff(XGF,z)-XGF):
XS := series(K1+K2+K3+K4+K5+K6, z=0, MX+1):
seq(n!*coeff(XS, z, n), n=1..MX);

m = 16;
A[z_] := Exp[1/2*z^2]*Sum[2^Binomial[n, 2]*(z/Exp[z])^n/n!, {n, 0, m+1}];
egf = (1/6)*(z^4/(1-z)^3)*A[z] + (1/2)*(z^4/(1-z)^2)*(A'[z] - A[z]) + (1/6)*(z^6/(1-z)^3)*(A'''[z] - 3*A''[z] + 3*A'[z] - A[z]) + (1/2)*(z^5/(1 - z)^4)*(A''[z] - 2*A'[z] + A[z]) + (1/6)*(z^4/(1-z)^4)*(A'[z] - A[z]) + (1/2)*(z^5/(1-z)^5)*(A'[z] - A[z]); s = egf + O[z]^(m+1);
a[n_] := n!*SeriesCoefficient[s, n];
Array[a, m] (* Jean-François Alcover, Feb 23 2019 *)

E.g.f.: (1/6)*(z^4/(1-z)^3)*A(z) + (1/2)*(z^4/(1-z)^2)*(A'(z)-A(z)) + (1/6)*(z^6/(1-z)^3)*(A'''(z)-3*A''(z)+3*A'(z)-A(z)) + (1/2)*(z^5/(1-z)^4)*(A''(z)-2*A'(z)+A(z)) + (1/6)*(z^4/(1-z)^4)*(A'(z)-A(z)) + (1/2)*(z^5/(1-z)^5)*(A'(z)-A(z)) where A(z) = exp(1/2*z^2) * Sum_{n>=0} 2^binomial(n, 2)*(z/exp(z))^n/n!.

A088974 Number of (nonisomorphic) connected bipartite graphs with minimum degree at least 2 and with n vertices.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 9, 45, 160, 1018, 6956, 67704, 830392, 13539344, 288643968, 8112651795, 300974046019, 14796399706863, 967194378235406, 84374194347669628, 9856131011755992817, 1546820212559671605395

Offset: 1

Felix Goldberg (felixg(AT)tx.technion.ac.il), Oct 30 2003

nonn

The terms were computed using the program Nauty.

As shown in the Hardt et al. reference, this sequence (for n >= 3) also enumerates the connected point-determining bipartite graphs. - Justin M. Troyka, Nov 27 2013

			Consider n = 4.  There is one connected bipartite graph with minimum degree at least 2: the square graph.  Also there is one connected point-determining bipartite graph: the graph *--*--*--*. - _Justin M. Troyka_, Nov 27 2013

Brendan McKay, Nauty
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO].

Cf. A006024, A004110 (labeled and unlabeled point-determining graphs [the latter is also unlabeled graphs w/ min. degree >= 2]).
Cf. A059167 (labeled graphs w/ min. degree >= 2).
Cf. A092430, A004108 (labeled and unlabeled connected point-determining graphs [the latter is also unlabeled connected graphs w/ min. degree >= 2]).
Cf. A059166 (labeled connected graphs w/ min. degree >= 2).
Cf. A232699, A218090 (labeled and unlabeled point-determining bipartite graphs).
Cf. A232700 (labeled connected point-determining bipartite graphs).

More terms from Andy Hardt, Oct 31 2012

A100548 Number of n-node labeled digraphs without endpoints.

Original entry on oeis.org

1, 1, 1, 28, 2539, 847126, 987474781, 4267529230672, 71328353711113801, 4706871807383903992060, 1236666872833000506726110479, 1297665884376581511952494336126664, 5444003907104081585974782986977125743035, 91341304409373044577470623665964376840167100920

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 02 2005

nonn

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

Cf. A059167, A101388 (labeled case).

m:=30;
f:= func< x | Exp(3*x^2/2)*(&+[ 2^(n*(n-1))*(x*Exp(-3*x))^n/Factorial(n) : n in [0..m+2]]) >;
R:=PowerSeriesRing(Rationals(), m);
Coefficients(R!(Laplace( f(x) ))); // G. C. Greubel, Mar 27 2023

m = 11;
egf = Exp[3x^2/2]*Sum[2^(n(n-1))*(x/Exp[3 x])^n/n!, {n, 0, m}];
a[n_] := SeriesCoefficient[egf, {x, 0, n}]*n!;
Table[a[n], {n, 0, m}] (* Jean-François Alcover, Feb 23 2019 *)

seq(n)={my(g=x/exp(3*x + O(x*x^n))); Vec(serlaplace(exp(3*x^2/2 + O(x*x^n))*sum(k=0, n, 2^(k*(k-1))*g^k/k!)))} \\ Andrew Howroyd, Jan 08 2020

m = 30
def f(x): return exp(3*x^2/2)*sum( 2^(n*(n-1))*(x*exp(-3*x))^n/factorial(n) for n in range(m+2) )
def A100548_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( f(x) ).egf_to_ogf().list()
A100548_list(m) # G. C. Greubel, Mar 27 2023

E.g.f.: exp(3/2*x^2)*(Sum_{n>=0} 2^(n*(n-1))*(x/exp(3*x))^n/n!).

Terms a(12) and beyond from Andrew Howroyd, Jan 08 2020

A101388 Number of n-vertex unlabeled digraphs without endpoints.

Original entry on oeis.org

1, 1, 1, 8, 137, 7704, 1413982, 855543836, 1775124241697, 12985137979651848, 340909258684048264585, 32512676857544231506934756, 11365672344040389664750137465767, 14668676509227095069116619104786898732, 70315084528883620836175544247562749711989951

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 14 2005

nonn

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

Cf. A100548 (labeled case), A004110, A004108, A059166, A059167, A101389.

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
seq(n)=Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^3 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2)) \\ Andrew Howroyd, Jan 22 2021

a(0)=1 prepended and terms a(7) and beyond from Andrew Howroyd, Jan 22 2021

A369928 Triangle read by rows: T(n,k) is the number of simple graphs on n labeled vertices with k edges and without endpoints, n >= 0, 0 <= k <= n*(n-1)/2.

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 4, 3, 6, 1, 1, 0, 0, 10, 15, 42, 90, 100, 45, 10, 1, 1, 0, 0, 20, 45, 162, 595, 1590, 3075, 3655, 2703, 1335, 455, 105, 15, 1, 1, 0, 0, 35, 105, 462, 2310, 9495, 32130, 85365, 166341, 231861, 237125, 184380, 111870, 53634, 20307, 5985, 1330, 210, 21, 1

Offset: 0

Andrew Howroyd, Feb 07 2024

			Triangle begins:
[0] 1;
[1] 1;
[2] 1, 0;
[3] 1, 0, 0,  1;
[4] 1, 0, 0,  4,  3,  6,    1;
[5] 1, 0, 0, 10, 15,  42,  90,  100,   45,   10,    1;
[6] 1, 0, 0, 20, 45, 162, 595, 1590, 3075, 3655, 2703, 1335, 455, 105, 15, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)

Row sums are A059167.

Cf. A084546, A123551 (unlabeled), A245796 (with endpoints).

\\ row(n) gives n-th row as vector.
row(n)={my(A=x/exp(x*y + O(x*x^n))); Vecrev(polcoef(serlaplace(exp(y*x^2/2 + O(x*x^n)) * sum(k=0, n, (1 + y)^binomial(k, 2)*A^k/k!)), n), 1 + binomial(n,2))}
{ for(n=0, 6, print(row(n))) }

T(n,k) = A084546(n,k) - A245796(n,k).

E.g.f.: exp(y*x^2/2) * Sum_{k>=0} (1 + y)^binomial(k, 2)*(x/exp(y*x))^k/k!.

A100569 Number of labeled n-node oriented graphs without endpoints.

Original entry on oeis.org

1, 1, 1, 9, 337, 37889, 11410545, 9368733289, 21760617258977, 146872848650637249, 2927557787922534645793, 173801937725990883065857673, 30857177979379449393077427767217, 16413568090264759380752395628891885377, 26177914283033566658965502231213434987939601

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 02 2005

nonn

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

Cf. A059167.

m = 14;
egf = Exp[x^2]*Sum[3^(n (n - 1)/2)*(x/Exp[2 x])^n/n!, {n, 0, m}];
a[n_] := SeriesCoefficient[egf, {x, 0, n}]*n!;
Table[a[n], {n, 0, m}] (* Jean-François Alcover, Feb 23 2019 *)

seq(n)={my(A=x/exp(2*x+O(x^n))); Vec(serlaplace(exp(x^2 + O(x*x^n)) * sum(k=0, n, 3^binomial(k, 2)*A^k/k!)))} \\ Andrew Howroyd, Sep 09 2018

E.g.f.: exp(x^2)*(Sum_{n >= 0} 3^(n*(n-1)/2)*(x/exp(2*x))^n/n!).

Terms a(13) and beyond from Andrew Howroyd, Sep 09 2018

A101389 Number of n-vertex unlabeled oriented graphs without endpoints.

Original entry on oeis.org

1, 1, 1, 3, 21, 369, 16929, 1913682, 546626268, 406959998851, 808598348346150, 4358157210587930509, 64443771774627635711718, 2636248889492487709302815665, 300297332862557660078111708007894, 95764277032243987785712142452776403618, 85885545190811866954428990373255822969983915

Offset: 0

Goran Kilibarda, Vladeta Jovovic, Jan 14 2005

nonn

			a(3) = 3 because there are 2 distinct orientations of the triangle K_3 plus the empty graph on 3 vertices.

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

Cf. A100569 (labeled case), A100548, A101388, A004110, A004108, A059166, A059167, A001174.

\\ See links in A339645 for combinatorial species functions.
oedges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
ographsCycleIndex(n)={my(s=0); forpart(p=n, s+=permcount(p) * 3^oedges(p) * sMonomial(p)); s/n!}
ographs(n)={sum(k=0, n, ographsCycleIndex(k)*x^k) + O(x*x^n)}
trees(n,k)={sRevert(x*sv(1)/sExp(k*x*sv(1) + O(x^n)))}
cycleIndexSeries(n)={my(g=ographs(n), tr=trees(n,2), tu=tr-tr^2); sSolve( g/sExp(tu), tr )*symGroupSeries(n)}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 27 2020

\\ faster stand-alone version
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
seq(n)={Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 3^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^2 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2))} \\ Andrew Howroyd, Jan 22 2021

a(0)=1 prepended and terms a(9) and beyond from Andrew Howroyd, Dec 27 2020

A327379 Number of labeled non-mating-type graphs with n vertices.

Original entry on oeis.org

0, 1, 4, 32, 436, 11292, 545784, 49826744, 8647819328, 2876819527744, 1848998498567936, 2312324942899031040, 5659406410382924819712, 27230994319259100289485568, 258465217554621196991878652416, 4851552662579126853087143276476928

Offset: 1

Gus Wiseman, Sep 05 2019

nonn

A mating-type graph has all different rows in its adjacency matrix.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
Gus Wiseman, The a(4) = 32 non-mating-type graphs.

The unlabeled version is A141580.

Cf. A006024, A006125, A028242, A059167, A245797, A327369, A327370.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!UnsameQ@@AdjacencyMatrix[Graph[Range[n],#]]&]],{n,5}]

a(n) = {2^binomial(n,2) - sum(k=0, n, stirling(n, k, 1)*2^binomial(k,2))} \\ Andrew Howroyd, Sep 11 2019

a(n) = A006125(n) - A006024(n). - Andrew Howroyd, Sep 11 2019

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019

A101390 Number of n-vertex unlabeled mating graphs (cf. A006024) without endpoints.

Original entry on oeis.org

1, 0, 1, 2, 7, 41, 347, 5447, 158097, 8456025

Offset: 1

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 14 2005

Cf. A006024, A004108, A004110, A059167.

cp's OEIS Frontend

A277074 Number of n-node labeled graphs with three endpoints.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A088974 Number of (nonisomorphic) connected bipartite graphs with minimum degree at least 2 and with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A100548 Number of n-node labeled digraphs without endpoints.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A101388 Number of n-vertex unlabeled digraphs without endpoints.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A369928 Triangle read by rows: T(n,k) is the number of simple graphs on n labeled vertices with k edges and without endpoints, n >= 0, 0 <= k <= n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A100569 Number of labeled n-node oriented graphs without endpoints.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A101389 Number of n-vertex unlabeled oriented graphs without endpoints.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Extensions

A327379 Number of labeled non-mating-type graphs with n vertices.

Views

Author

Keywords

Comments