A294783 -id:A294783 - 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

A321304 Triangle T(n,f): the number of bicolored connected cubic graphs on 2n vertices with f vertices of the first color.

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 5, 5, 5, 2, 2, 5, 10, 31, 46, 63, 46, 31, 10, 5, 19, 64, 248, 542, 931, 1052, 931, 542, 248, 64, 19, 85, 490, 2382, 7011, 15199, 23405, 27336, 23405, 15199, 7011, 2382, 490, 85, 509, 4595, 27233, 101002, 268675, 523246, 776657, 882321, 776657, 523246, 268675, 101002, 27233, 4595, 509

Offset: 0

R. J. Mathar, Nov 03 2018

These are connected, undirected, simple cubic graphs where each vertex has either the first or the second color. Row n has 2n+1 entries, 0<=f<=2n. The column f=0 (1, 0, 2, 5,...) counts the cubic graphs (A002851). The column f=1 (0, 1, 2, 10, 64, 490...) counts the rooted cubic graphs.

			The triangle starts:
0 vertices:   1;
2 vertices:   0,  0,   0;
4 vertices:   1,  1,   1,   1,   1;
6 vertices:   2,  2,   5,   5,   5,    2,   2;
8 vertices:   5, 10,  31,  46,  63,   46,  31,  10,   5;
10 vertices: 19, 64, 248, 542, 931, 1052, 931, 542, 248, 64, 19;

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

Columns f=0, 1, 2 are A002851, A361407, A361408.
Row sums are A361403.
Central coefficients are A361406.
Cf. A294783 (bicolored trees), A321305 (signed edges), A361361 (not necessarily connected).

T(n,f) = T(n,2n-f).

Terms a(49) and beyond from Andrew Howroyd, Mar 11 2023

A038056 Number of trees with n 2-colored nodes.

Original entry on oeis.org

2, 3, 6, 18, 54, 189, 700, 2778, 11486, 49377, 217936, 984818, 4533004, 21198962, 100471862, 481754806, 2333465628, 11404047817, 56177574628, 278710061814, 1391617108600, 6988781174376, 35283390923324, 178990052273558, 912019786448570, 4665994686718118

Offset: 1

Christian G. Bower, Jan 04 1999

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for sequences related to trees

Cf. A000055, A038055-A038062. Row sums of A294783.

G.f.: B(x) - B^2(x)/2 + B(x^2)/2, where B(x) is g.f. for A038055.

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

A304489 Triangle read by rows: T(n,k) = number of rooted signed trees with n nodes and k positive edges (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 4, 9, 9, 4, 9, 26, 37, 26, 9, 20, 75, 134, 134, 75, 20, 48, 214, 469, 596, 469, 214, 48, 115, 612, 1577, 2445, 2445, 1577, 612, 115, 286, 1747, 5204, 9480, 11513, 9480, 5204, 1747, 286, 719, 4995, 16865, 35357, 50363, 50363, 35357, 16865, 4995, 719

Offset: 1

Andrew Howroyd, May 13 2018

Equivalently, the number of rooted trees with 2-colored non-root nodes, n nodes and k nodes of the first color.

			Triangle begins:
    1;
    1,    1;
    2,    3,    2;
    4,    9,    9,    4;
    9,   26,   37,   26,     9;
   20,   75,  134,  134,    75,   20;
   48,  214,  469,  596,   469,  214,   48;
  115,  612, 1577, 2445,  2445, 1577,  612,  115;
  286, 1747, 5204, 9480, 11513, 9480, 5204, 1747, 286;
  ...

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

Row sums are A000151.
Columns k=0..1 are A000081, A000243.
Cf. A294783, A302939, A331114.

R(n, y)={my(v=vector(n)); v[1]=1; for(k=1, n-1, my(p=(1+y)*v[k]); my(q=Vec(prod(j=0, poldegree(p, y), (1/(1-x*y^j) + O(x*x^(n\k)))^polcoeff(p, j)))); v=vector(n, j, v[j] + sum(i=1, (j-1)\k, v[j-i*k] * q[i+1]))); v; }
{ my(A=R(10,y)); for(n=1, #A, print(Vecrev(A[n]))) }

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
R(n, y)={my(v=[1]); for(k=2,n,v=concat([1], EulerMT(v*(1+y)))); v}
{ my(A=R(10,y)); for(n=1, #A, print(Vecrev(A[n]))) }

A303843 The number of unlabeled trees with n nodes rooted at 3 indistinguishable roots.

Original entry on oeis.org

0, 0, 1, 4, 15, 51, 175, 573, 1866, 5978, 19000, 59859, 187503, 584012, 1811212, 5595239, 17228943, 52898764, 162013452, 495100454, 1510029296, 4597430832, 13975327501, 42422033217, 128606150706, 389423872694, 1177925775148, 3559477190797, 10746362772325

Offset: 1

R. J. Mathar, May 01 2018

nonn

A unique path exists between any two of the roots. These will intersect at a single vertex which might coincide with one of the original roots. This intersecting vertex can be chosen as a root to which the other trees are attached. - Andrew Howroyd, May 03 2018

			a(3)=1 (all nodes are roots). a(4)=4: the linear tree has the non-root node either at a leaf or not, and the star tree has the non-root node either at the center or at a leaf.

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

4th column of A294783.

Cf. A000081 (1-rooted), A303833 (2-rooted).

m = 30; T[_] = 0;
Do[T[x_] = x Exp[Sum[T[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, m}];
g[x_] = T[x]/(1 - T[x]) + O[x]^m // Normal;
g[x]((g[x]^3 + 3g[x]g[x^2] + 2g[x^3] + 3g[x]^2 + 3g[x^2])/(6(1 + g[x]))) + O[x]^m // CoefficientList[#, x]& // Rest (* Jean-François Alcover, Feb 16 2020, after Andrew Howroyd *)

\\ here TreeGf is gf of A000081
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)); my(g=T/(1-T)); T*(g^3 + 3*subst(g,x,x^2)*g + 2*subst(g,x,x^3) + 3*g^2 + 3*subst(g,x,x^2))/6}
concat([0,0], Vec(seq(30))) \\ Andrew Howroyd, May 03 2018

G.f.: g(x)*(g(x)^3 + 3*g(x)*g(x^2) + 2*g(x^3) + 3*g(x)^2 + 3*g(x^2))/(6*(1 + g(x))) where g(x) = T(x)/(1-T(x)) and T(x) is the g.f. of A000081. - Andrew Howroyd, May 03 2018

Terms a(11) and beyond from Andrew Howroyd, May 03 2018

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

A321304 Triangle T(n,f): the number of bicolored connected cubic graphs on 2n vertices with f vertices of the first color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A038056 Number of trees with n 2-colored nodes.

Views

Author

Keywords

Links

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

A304489 Triangle read by rows: T(n,k) = number of rooted signed trees with n nodes and k positive edges (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

A303843 The number of unlabeled trees with n nodes rooted at 3 indistinguishable roots.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions