A303833 -id:A303833 - cp's OEIS frontend

A294783 Number of trees with n bicolored nodes and f nodes of the first color. Triangle T(n,f) read by rows, 0<=f<=n.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 4, 6, 4, 2, 3, 9, 15, 15, 9, 3, 6, 20, 43, 51, 43, 20, 6, 11, 48, 116, 175, 175, 116, 48, 11, 23, 115, 329, 573, 698, 573, 329, 115, 23, 47, 286, 918, 1866, 2626, 2626, 1866, 918, 286, 47, 106, 719, 2609, 5978, 9656, 11241, 9656, 5978, 2609, 719, 106, 235, 1842

Offset: 0

R. J. Mathar, Apr 16 2018

			The triangle starts
    1;
    1,   1;
    1,   1,   1;
    1,   2,   2,    1;
    2,   4,   6,    4,    2;
    3,   9,  15,   15,    9,    3;
    6,  20,  43,   51,   43,   20,    6;
   11,  48, 116,  175,  175,  116,   48,  11;
   23, 115, 329,  573,  698,  573,  329, 115,  23;
   47, 286, 918, 1866, 2626, 2626, 1866, 918, 286, 47;
  106, 719,2609, 5978, 9656,11241, 9656,5978,2609,719,106;
  235,1842,

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

Cf. A038056 (row sums), A000055 (diagonal and 1st column), A000081 (subdiagonal and 2nd column), A303833 (3rd column), A303843 (4th column), A304311 (connected graphs), A304489 (rooted).

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;}
M(n)={my(B=(1+y)*x*Ser(R(n,y))); 1 + B - (B^2 - substvec(B, [x,y], [x^2,y^2]))/2}
{ my(A=M(10)); for(n=0, #A-1, print(Vecrev(polcoeff(A, n)))) } \\ Andrew Howroyd, May 12 2018

T(n,f) = T(n,n-f), flipping all node colors.

Row 10 completed. - R. J. Mathar, Apr 29 2018

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

A339303 Triangle read by rows: T(n,k) is the number of unoriented linear forests with n nodes and k rooted trees.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 3, 2, 1, 9, 6, 6, 2, 1, 20, 16, 15, 8, 3, 1, 48, 37, 41, 22, 12, 3, 1, 115, 96, 106, 69, 38, 15, 4, 1, 286, 239, 284, 194, 124, 52, 20, 4, 1, 719, 622, 750, 564, 377, 189, 77, 24, 5, 1, 1842, 1607, 2010, 1584, 1144, 618, 292, 100, 30, 5, 1

Offset: 1

Andrew Howroyd, Dec 04 2020

Linear forests (A339067) are considered up to reversal of the linear order.

T(n,k) is the number of unlabeled trees on n nodes rooted at two indistinguishable nodes at distance k-1 from each other.

			Triangle read by rows:
    1;
    1,   1;
    2,   1,   1;
    4,   3,   2,   1;
    9,   6,   6,   2,   1;
   20,  16,  15,   8,   3,   1;
   48,  37,  41,  22,  12,   3,  1;
  115,  96, 106,  69,  38,  15,  4,  1;
  286, 239, 284, 194, 124,  52, 20,  4, 1;
  719, 622, 750, 564, 377, 189, 77, 24, 5, 1;
  ...

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

Columns 1..4 are A000081, A027852, A280788(n-3), A339302.
Row sums are A303840(n+2).
Row sums excluding the first column are A303833.
Cf. A339067.

\\ 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)}
ColSeq(n,k)={my(r=TreeGf(max(0,n+1-k))); Vec(r^k + r^(k%2)*subst(r, x, x^2)^(k\2), -n)/2}
M(n, m=n)=Mat(vector(m, k, ColSeq(n,k)~))
{ my(T=M(12)); for(n=1, #T~, print(T[n,1..n])) }

G.f of column k: (r(x)^k + r(x)^(k mod 2)*r(x^2)^floor(k/2))/2 where r(x) is the g.f. of A000081.

A303840 Unlabeled trees with n nodes rooted at 2 indistinguishable roots that are leaves.

Original entry on oeis.org

0, 1, 1, 2, 4, 10, 24, 63, 164, 444, 1204, 3328, 9233, 25865, 72734, 205656, 583320, 1660318, 4737540, 13551165, 38837535, 111512229, 320681604, 923528963, 2663057582, 7688068638, 22218350303, 64272720521, 186091334380, 539237928902, 1563731491958, 4537823968645, 13176960639940, 38286514506439, 111306880581963

Offset: 1

R. J. Mathar, May 01 2018

nonn

			a(2)=a(3)=1, because the two roots must be (all) the leaves. a(4)=2 (one pattern from the linear tree, one from the star tree). a(6)=10: 1 pattern from n-Hexane. 2 patterns from 2-Methyl-Pentane. 2 patterns from (2,3)-Bimethyl-Butane. 1 pattern from the star graph. 2 patterns from 3-Methyl-Pentane. 2 patterns from (2,2)-Bimethyl-Butane.

Cf. A303833 (roots need not be leaves), A055290 (cardinality of candidates).

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,
997171512998, 2809934352700, 7929819784355, 22409533673568, 63411730258053, 179655930440464, 509588049810620, 1447023384581029,
4113254119923150, 11703780079612453, 33333125878283632] ;
g81 := add( op(i,a000081)*x^i,i=1..nops(a000081) ) ;
g81fin := x ;
g := 0 ;
nmax := nops(a000081) ;
for m from 0 to nmax do
    mhalf := floor(m/2) ;
    ghalf := g81^mhalf*g81fin ;
    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](%) ;

A303842 Triangle read by rows: T(s,n) (s>=1 and 2<=n<=s+1) = number of trees with n nodes and positive integer edge labels with label sum s.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 3, 3, 1, 2, 6, 6, 6, 1, 3, 9, 15, 16, 11, 1, 3, 13, 26, 43, 37, 23, 1, 4, 17, 46, 88, 116, 96, 47, 1, 4, 23, 68, 169, 273, 329, 239, 106, 1, 5, 28, 103, 287, 585, 869, 918, 622, 235, 1, 5, 35, 141, 467, 1104, 2031, 2695, 2609, 1607, 551

Offset: 1

R. J. Mathar, May 01 2018

			The triangle starts
1;
1   1;
1   1   2;
1   2   3    3;
1   2   6    6    6;
1   3   9    15   16    11;
1   3   13   26   43    37     23;
1   4   17   46   88    116    96    47;
1   4   23   68   169   273    329   239  106;
1   5   28   103  287   585    869   918  622    235;
1   5   35   141  467   1104   2031  2695 2609   1607   551;
1   6   42   195  711   1972   4211  6882 8399   ...    4235  1301;
1   6   50   253  1051  3270   8108 15513 23152  ...    ... ;
1   7   58   330  1489  5222  14552 32191 56291  ...    ... ;
1   7   68   412  2063  7958  24846 62014 124958  ...    ... ;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
R. J. Mathar, Labeled Trees with fixed node label sum, vixra:1805.0205 (2018).

Cf. A303841 (labeled nodes), A000055 (diagonal), A027852 (subdiagonal), A303833 (subdiagonal), A304914 (row sums).

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)}
b(n)={my(v=[1]); for(i=1, n, v=concat([1], v + EulerMT(y*v))); Ser(v)*y*(1-x)}
seq(n)={my(g=b(n)); Vec(g + (substvec(g, [x,y], [x^2,y^2]) - g^2)*x/(2*(1-x)) - y)}
{my(A=seq(15)); for(n=1, #A, print(Vecrev(A[n]/y^2)))} \\ Andrew Howroyd, May 20 2018

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

A304067 Number of trees with n vertices rooted at a non-edge.

Original entry on oeis.org

0, 0, 1, 3, 9, 27, 79, 233, 679, 1987, 5784, 16864, 49063, 142821, 415439, 1208761, 3516475, 10232428, 29778138, 86682119, 252382445, 735040515, 2141319946, 6239913801, 18188637903, 53033228465, 154674931182, 451247206423

Offset: 1

Brendan McKay, May 05 2018

nonn

			a(3)=1: the non-edge joins two leaves. a(4)=3: The non-edge joins two leaves of the star graph; or the non-edge joins the two leaves of the linear graph; or the non-edge joins a leaf with the node at distance 2.

Cf. A000055 (not rooted), A027852 (rooted at an edge), A304068 (rooted at an oriented non-edge).

a(n) + A027852(n) = A303833(n).

cp's OEIS Frontend

A294783 Number of trees with n bicolored nodes and f nodes of the first color. Triangle T(n,f) read by rows, 0<=f<=n.

Views

Author

Keywords

Examples

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

A339303 Triangle read by rows: T(n,k) is the number of unoriented linear forests with n nodes and k rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303840 Unlabeled trees with n nodes rooted at 2 indistinguishable roots that are leaves.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A303842 Triangle read by rows: T(s,n) (s>=1 and 2<=n<=s+1) = number of trees with n nodes and positive integer edge labels with label sum s.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

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

A304067 Number of trees with n vertices rooted at a non-edge.

Views

Author

Keywords

Examples

Crossrefs

Formula