A303831 -id:A303831 - cp's OEIS frontend

A303833 Birooted trees: number of unlabeled trees with n nodes rooted at 2 indistinguishable roots.

0, 1, 2, 6, 15, 43, 116, 329, 918, 2609, 7391, 21099, 60248, 172683, 495509, 1424937, 4102693, 11830006, 34148859, 98686001, 285459772, 826473782, 2394774727, 6944343654, 20151175658, 58513084011, 170007600051, 494230862633

Offset: 1

R. J. Mathar, Brendan McKay, May 01 2018

nonn

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

Subsets of graphs in A303831. Cf. A000243 (distinguishable roots), A000055 (not rooted).
Third column of A294783.
Cf. A000081, A000107, A027852, A303840, A304067, A339303.

a000081 := [1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847, 1721159, 4688676, 12826228, 35221832, 97055181, 268282855, 743724984, 2067174645, 5759636510, 16083734329, 45007066269, 126186554308, 354426847597] ;
g81 := add( op(i,a000081)*x^i,i=1..nops(a000081) ) ;
g := 0 ;
nmax := nops(a000081) ;
for m from 0 to nmax do
    mhalf := floor(m/2) ;
    ghalf := g81^(mhalf+1) ;
    gcyc := (ghalf^2+subs(x=x^2,ghalf))/2 ;
    if type(m,odd) then
        gcyc := gcyc*g81 ;
    end if;
    g := g+gcyc ;
end do:
taylor(g,x=0,nmax) ;
gfun[seriestolist](%) ; # R. J. Mathar, May 01 2018

TreeGf is A000081 as g.f.
TreeGf(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n), t2=subst(t,x,x^2)+O(x*x^n)); Vec((2*t^2-1)/(1-t) + (1+t)/(1-t2), -n)/2} \\ Andrew Howroyd, Dec 04 2020

G.f.: [g81(x)^2/{1-g81(x)} +(1+g81(x))*g81(x^2)/{1-g81(x^2)}] /2 = [ g243(x) +(1+g81(x))*g107(x^2)]/2, where g81 is the g.f. of A000081, g243 the g.f. of A000243 and g107 the g.f. of A000107. - R. J. Mathar, May 02 2018
a(n) = A027852(n) + A304067(n). - Brendan McKay, May 05 2018
a(n) = A303840(n+2) - A000081(n). - Andrew Howroyd, Dec 04 2020

A304074 Number of simple connected graphs with n nodes rooted at a pair of distinguished vertices.

Original entry on oeis.org

0, 1, 4, 23, 162, 1549, 21090, 446061, 15673518, 961338288, 105752617892, 21155707801451, 7757777336382702, 5245054939576054088, 6571185585793205495484, 15325133281701584879975433, 66813349775478836190531605234, 546646811841381587823502759339055

Offset: 1

Brendan McKay, May 05 2018

nonn

			a(3)=4: one choice to mark two roots in the triangular graph; one choice to mark the two leaves in the linear graph; two choices to mark the center node and a leave (1st root in the center or 2nd root in the center) in the linear graph.

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

Cf. A001349 (not rooted), A303831 (vertices not distinguished), A304070 (not necessarily connected).

Cf. A000088, A000666.

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]\2)}
cross(u, v) = {sum(i=1, #u, sum(j=1, #v, gcd(u[i], v[j])))}
S(n, r)={my(t=#r+1); vector(n+1, n, if(nAndrew Howroyd, Sep 07 2019

a(n) = A304072(n) + A304073(n).

G.f.: 2*B(x)/G(x) - (x*C(x)/G(x))^2, where B(x) is the g.f. of A304069, C(x) is the g.f. of A000666 and G(x) is the g.f. of A000088. - Andrew Howroyd, Sep 07 2019

Terms a(13) and beyond from Andrew Howroyd, Sep 07 2019

A126100 Number of rooted connected unlabeled graphs on n nodes.

Original entry on oeis.org

0, 1, 1, 3, 11, 58, 407, 4306, 72489, 2111013, 111172234, 10798144310, 1944301471861, 650202565436890, 404697467417019634, 470133531223369393920, 1022561022228933341815171, 4177761667636803276899047351, 32163582481439081597751699343141, 468019937132164016636736323752098741

Offset: 0

David Applegate and N. J. A. Sloane, Mar 05 2007

Let G run through all connected unlabeled graphs on n nodes. Add up the numbers of inequivalent nodes (under Aut(G)) for each G.
"Pointed" connected graphs. This has the same relation to A001349 as A000081 does to A000055.
a(0) = 0 because the empty graph cannot be rooted.

			For 3 nodes G is either a path (2 kinds of nodes) or a triangle (one kind of node), for a total of a(3) = 3.
For the 5-vertex graphs we have 2 * 1 orbit, 6 * 2 orbits, 8 * 3 orbits, 5 * 4 orbits for a total of 2 + 12 + 24 + 20 = 58.

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..23 from David Applegate and N. J. A. Sloane)

Cf. A001349, A126101, A000666, A000088, A126201, A303831 (birooted), A304311.

Cf. A000081, A000055.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
g[n_, r_] := (s = 0; Do[s += permcount[p]*(2^(r*Length[p] + edges[p])), {p, IntegerPartitions[n]}]; s/n!);
seq[m_] := Sum[g[n-1, 1] x^(n-1), {n, 0, m}]/Sum[g[n-1, 0] x^(n-1), {n, 0, m}] + O[x]^m // CoefficientList[#, x]& // Prepend[#, 0]&;
seq[20] (* Jean-François Alcover, Jul 09 2018, after Andrew Howroyd *)

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]\2)}
g(n,r) = {my(s=0); forpart(p=n, s+=permcount(p)*(2^(r*#p+edges(p)))); s/n!}
seq(n)={concat([0], Vec(Ser(vector(n, n, g(n-1,1)))/Ser(vector(n, n, g(n-1,0)))))} \\ Andrew Howroyd, May 03 2018

The g.f. A(x) = x+x^2+3*x^3+11*x^4+... satisfies f(x) = 1 + A(x)*g(x), where f(x) = 1+x+2*x^2+6*x^3+20*x^4+... is the g.f. for A000666 and g(x) = 1+x+2*x^2+4*x^3+11*x^4+... is the g.f. for A000088. - Brendan McKay

a(5)-a(9) computed by Gordon F. Royle, Mar 05 2007
a(10) and a(11) computed by Brendan McKay, Mar 05 2007
a(12) onwards computed from the generating function, A000088 and A000666 by David Applegate and N. J. A. Sloane, Mar 06 2007

A339041 Number of unlabeled connected simple graphs with n edges rooted at two indistinguishable vertices.

Original entry on oeis.org

1, 2, 7, 21, 73, 255, 946, 3618, 14376, 58957, 249555, 1087828, 4878939, 22488282, 106432530, 516783762, 2572324160, 13116137104, 68461594211, 365559412868, 1995532789212, 11129600885183, 63381069498524, 368338847181336, 2183239817036378

Offset: 1

Andrew Howroyd, Nov 20 2020

nonn

Cf. A000664, A002905, A303831, A303832, A339039, A339040, A339043, A339044, A339063, A339064.

\\ See A339063 for G.
seq(n)={my(A=O(x*x^n), g=G(2*n, x+A, []), gr=G(2*n, x+A, [1])/g); Vec(G(2*n, x+A, [1, 1])/g - gr^2 + G(2*n, x+A, [2])/g - subst(gr, x, x^2))/2}

G.f.: f(x)/g(x) - (r(x)^2 + r(x^2))/2 where f(x), g(x) and r(x) are the g.f.'s of A339064, A000664 and A339039.

A103904 a(n) = n(n-1)/2 2^(n*(n-1)/2).

Original entry on oeis.org

0, 2, 24, 384, 10240, 491520, 44040192, 7516192768, 2473901162496, 1583296743997440, 1981583836043018240, 4869940435459321626624, 23574053482485268906770432, 225305087149939210031640608768

Offset: 1

Ralf Stephan, Feb 21 2005

nonn

a(n) is the number of birooted graphs on n labeled nodes. - Andrew Howroyd, Nov 23 2020

Old (incorrect) name was: "Number of perfect matchings of an n X (n+1) Aztec rectangle with the third vertex in the topmost row removed". See Mathematics Stack Exchange for the discussion. - Andrey Zabolotskiy, Jun 05 2022

M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97, doi:10.1006/jcta.1996.2725.
N. Elkies, G. Kuperberg, M. Larsen and J. Propp, Alternating sign matrices and domino tilings, Journal of Algebraic Combinatorics 1 (1992), 111-132 (Part I), 219-234 (Part II); arXiv:math/9201305 [math.CO], 1992.
H. Helfgott and I. M. Gessel, Enumeration of tilings of diamonds and hexagons with defects, arXiv:math/9810143 [math.CO], 1998.
C. Krattenthaler, Schur function identities and the number of perfect matchings of Aztec holey rectangles, arXiv:math/9712204 [math.CO], 1997.
Mathematics Stack Exchange, Mistake in OEIS A103904?, 2021.

Cf. A000217, A006125, A038094, A095340, A095351, A134401, A036289, A303831.

a(n)={binomial(n,2)*2^binomial(n,2)} \\ Andrew Howroyd, Nov 23 2020

a(n) = A000217(n-1) * A006125(n).
a(n) = 2*A095351(n). - Andrew Howroyd, Nov 23 2020
a(n) = A036289(n*(n-1)/2). - Michael Somos, Feb 28 2021

Name replaced by a formula, a(1) changed from 1 to 0, and entry edited by Andrey Zabolotskiy, Jun 05 2022

A303829 Birooted graphs: number of unlabeled graphs with n nodes rooted at 2 indistinguishable roots.

Original entry on oeis.org

0, 2, 6, 28, 148, 1144, 13128, 250240, 8295664, 494367376, 53628829952, 10655018252544, 3893626388008448, 2627758027841688960, 3289042848785452985600, 7666804477507744021487616, 33416397343695235205887366144, 273365202164844511328577434284160

Offset: 1

Brendan McKay, May 01 2018

nonn

Cf. A303831 (connected), A303833 (trees), A126122.

a(n) = 2 * A126122(n). - Alois P. Heinz, May 01 2018

A304311 Triangle T(n,k) read by rows: number of bicolored connected graphs with n nodes and k nodes of the first color.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 6, 11, 16, 11, 6, 21, 58, 98, 98, 58, 21, 112, 407, 879, 1087, 879, 407, 112, 853, 4306, 11260, 17578, 17578, 11260, 4306, 853, 11117, 72489, 230505, 436371, 537272, 436371, 230505, 72489, 11117

Offset: 0

R. J. Mathar, May 10 2018

			Triangle begins
      1;
      1,     1;
      1,     1,      1;
      2,     3,      3,      2;
      6,    11,     16,     11,      6;
     21,    58,     98,     98,     58,     21;
    112,   407,    879,   1087,    879,    407,    112;
    853,  4306,  11260,  17578,  17578,  11260,   4306,   853;
  11117, 72489, 230505, 436371, 537272, 436371, 230505, 72489, 11117;

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

Cf. A054921 (row sums), A001349 (1st column), A126100 (2nd column), A303831 (3rd column), A294783 (trees).

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]\2)}
S(n,y)={my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)*prod(i=1,#p,1+y^p[i])); s/n!}
InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i) )}
{my(A=InvEulerMT(vector(10, n, S(n,y)))); for(n=0, #A, for(k=0, n, print1(polcoeff(if(n,A[n],1), k), ", ")); print)} \\ Andrew Howroyd, May 13 2018

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

A304071 Number of simple connected graphs with n nodes rooted at one non-edge.

Original entry on oeis.org

0, 0, 1, 6, 42, 402, 5381, 112776, 3935471, 240684836, 26449057257, 5289513580458, 1939502108505917, 1311274498490104492, 1642800188822966309834, 3831285832174735713684706, 16703340559932677463553709189, 136661710199022168890320488632600, 2105815888079982128884579271408161673, 61310553163194788144046000967760340771668

Offset: 1

Brendan McKay, May 05 2018

nonn

			a(3)=1: the non-edge joins the two leaves. a(4)=6: quadrangle: the non-edge is a diagonal; triangle with protruding edge: the non-edge joins the leaf with a node of degree 2; quadrangle with diagonal: the non-edge is the other diagonal; tetrahedron: no contribution; linear chain: the non-edge either joins the two leaves or a leaf with a node at distance 2; star graph: the non-edge joins two leaves.

Jean-François Alcover, Table of n, a(n) for n = 1..40

Cf. A001349 (not rooted), A126122 (not necessarily connected)

A303830 = Import["https://oeis.org/A303830/b303830.txt", "Table"][[All, 2]];
A303831 = Import["https://oeis.org/A303831/b303831.txt", "Table"][[All, 2]];
a[n_] := A303831[[n]] - A303830[[n]];
a /@ Range[1, 40] (* Jean-François Alcover, Sep 21 2019 *)

a(n) + A303830(n) = A303831(n).

A340029 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of indistinguishable vertices.

Original entry on oeis.org

0, 1, 1, 6, 37, 388, 6004, 148759, 5974184, 404509191, 47552739892, 9923861406343, 3735194287263442, 2565376853616300801, 3244070698095148283628, 7607050619214875184974489, 33269229977451262849539412860, 272689940536978851416633440863567

Offset: 1

Andrew Howroyd, Jan 02 2021

nonn

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

Cf. A002218, A004115, A241768, A303829, A303831, A340028.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
blockGraphs(n)={my(gc=sLog(graphsSeries(n)), gcr=sPoint(gc)); intformal(x*sSolve( sLog( gcr/(x*sv(1)) ), gcr ), sv(1)) + sSolve(subst(gc, sv(1), 0), gcr)}
cycleIndexSeries(n)={sCartProd(blockGraphs(n), x^2 * symGroupCycleIndex(2) * symGroupSeries(n-2))}
{ my(N=15); Vec(OgfSeries(cycleIndexSeries(N)), -N) }

cp's OEIS Frontend

A303833 Birooted trees: number of unlabeled trees with n nodes rooted at 2 indistinguishable roots.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A304074 Number of simple connected graphs with n nodes rooted at a pair of distinguished vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A126100 Number of rooted connected unlabeled graphs on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A339041 Number of unlabeled connected simple graphs with n edges rooted at two indistinguishable vertices.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A103904 a(n) = n*(n-1)/2 * 2^(n*(n-1)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A303829 Birooted graphs: number of unlabeled graphs with n nodes rooted at 2 indistinguishable roots.

Views

Author

Keywords

Crossrefs

Formula

A304311 Triangle T(n,k) read by rows: number of bicolored connected graphs with n nodes and k nodes of the first color.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A304071 Number of simple connected graphs with n nodes rooted at one non-edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A103904 a(n) = n(n-1)/2 2^(n*(n-1)/2).