A055327 -id:A055327 - cp's OEIS frontend

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 18, 14, 5, 1, 0, 1, 12, 35, 39, 21, 6, 1, 0, 1, 16, 62, 97, 72, 30, 7, 1, 0, 1, 20, 103, 212, 214, 120, 40, 8, 1, 0, 1, 25, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0

Offset: 1

Christian G. Bower, May 09 2000

Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014

			From _Joerg Arndt_, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1    0
03: 1    1    0
04: 1    2    1    0
05: 1    4    3    1    0
06: 1    6    8    4    1    0
07: 1    9   18   14    5    1    0
08: 1   12   35   39   21    6    1    0
09: 1   16   62   97   72   30    7    1    0
10: 1   20  103  212  214  120   40    8    1    0
11: 1   25  161  429  563  416  185   52    9    1    0
12: 1   30  241  804 1344 1268  732  270   65   10    1    0
13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 2 3 4 ]   1
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]   2
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]   2
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]   2
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]   3
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]   3
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]   2
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]   3
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]   4
:  O--o
:  .--o
:  .--o
:  .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).

F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Row sums give A000081.
Columns 2 through 12: A002620(n-1), A055278-A055287.
Cf. A055288, A055289, A055290.
Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* Gus Wiseman, Mar 19 2018 *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

A301342 Regular triangle where T(n,k) is the number of rooted identity trees with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 0, 0, 0, 1, 4, 1, 0, 0, 0, 1, 6, 5, 0, 0, 0, 0, 1, 9, 13, 2, 0, 0, 0, 0, 1, 12, 28, 11, 0, 0, 0, 0, 0, 1, 16, 53, 40, 3, 0, 0, 0, 0, 0, 1, 20, 91, 109, 26, 0, 0, 0, 0, 0, 0, 1, 25, 146, 254, 116, 6, 0, 0, 0, 0, 0, 0, 1, 30, 223, 524, 387, 61, 0, 0, 0, 0, 0, 0, 0, 1, 36

Offset: 1

Gus Wiseman, Mar 19 2018

			Triangle begins:
1
1   0
1   0   0
1   1   0   0
1   2   0   0   0
1   4   1   0   0   0
1   6   5   0   0   0   0
1   9  13   2   0   0   0   0
1  12  28  11   0   0   0   0   0
1  16  53  40   3   0   0   0   0   0
1  20  91 109  26   0   0   0   0   0   0
1  25 146 254 116   6   0   0   0   0   0   0
1  30 223 524 387  61   0   0   0   0   0   0   0
The T(6,2) = 4 rooted identity trees: (((o(o)))), ((o((o)))), (o(((o)))), ((o)((o))).

A version with the zeroes removed is A055327.

Cf. A000081, A001190, A003238, A004111, A032305, A055277, A273873, A276625, A277098, A290689, A298118, A298422, A298426, A301343, A301344, A301345.

irut[n_]:=irut[n]=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[irut/@c]],UnsameQ@@#&]]/@IntegerPartitions[n-1]];
Table[Length[Select[irut[n],Count[#,{},{-2}]===k&]],{n,8},{k,n}]

A318227 Number of inequivalent leaf-colorings of rooted identity trees with n nodes.

Original entry on oeis.org

1, 1, 1, 3, 5, 14, 38, 114, 330, 1054, 3483, 11841, 41543, 149520, 552356, 2084896, 8046146, 31649992, 127031001, 518434863, 2153133594, 9081863859, 38909868272, 169096646271, 745348155211, 3329032020048, 15063018195100, 68998386313333, 319872246921326, 1500013368166112

Offset: 1

Gus Wiseman, Aug 21 2018

nonn

In a rooted identity tree, all branches directly under any given branch are different.

The leaves are colored after selection of the tree. Since all trees are asymmetric, the symmetry group of the leaves will be the identity group and a tree with k leaves will have Bell(k) inequivalent leaf-colorings. - Andrew Howroyd, Dec 10 2020

			Inequivalent representatives of the a(6) = 14 leaf-colorings:
  (1(1(1)))  ((1)((1)))  (1(((1))))  ((1((1))))  (((1(1))))  (((((1)))))
  (1(1(2)))  ((1)((2)))  (1(((2))))  ((1((2))))  (((1(2))))
  (1(2(1)))
  (1(2(2)))
  (1(2(3)))

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

Cf. A000081, A001190, A001678, A003238, A004111, A290689, A318185, A304486.
Cf. A318226, A318228, A318229, A318230, A318231, A318234.
Cf. A000110 (Bell numbers), A055327, A301342.

idt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[idt/@c]],UnsameQ@@#&],{c,IntegerPartitions[n-1]}]];
Table[Sum[BellB[Count[tree,{},{0,Infinity}]],{tree,idt[n]}],{n,16}]

\\ bell(n) is A000110(n).
WeighMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, (-1)^(i-1)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
bell(n)={sum(k=1, n, stirling(n,k,2))}
seq(n)={my(v=[y], b=vector(n,k,bell(k))); for(n=2, n, v=concat(v[1], WeighMT(v))); vector(n, k, sum(i=1, k, polcoef(v[k],i)*b[i]))} \\ Andrew Howroyd, Dec 10 2020

a(n) = Sum_{k=1..n} A055327(n,k) * A000110(k). - Andrew Howroyd, Dec 10 2020

Terms a(17) and beyond from Andrew Howroyd, Dec 10 2020

A055334 Number of asymmetric (identity) trees with n nodes and k leaves.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 3, 3, 0, 0, 0, 4, 8, 3, 0, 0, 5, 14, 10, 0, 0, 0, 7, 25, 29, 6, 0, 0, 8, 40, 65, 25, 1, 0, 0, 10, 62, 135, 90, 13, 0, 0, 12, 89, 252, 244, 69, 1, 0, 0, 14, 127, 445, 591, 276, 27, 0, 0, 16, 173, 739, 1273, 868, 172, 3, 0, 0, 19

Offset: 1

Christian G. Bower, May 12 2000

A pair of zeros marks the next row.

			1; 0; 0; 0; 0; 0; 0,0,1; 0,0,1; 0,0,2,1; 0,0,3,3; 0,0,4,8,3; ...

Index entries for sequences related to trees

Row sums give A000220. Columns 3 through 8: A001399(n-7), A055335-A055339.

G.f.: A(x, y)=(1-x+x*y)*B(x, y)-(1/2)*(B(x, y)^2+B(x^2, y^2)). B(x, y): g.f. of A055327.

A055328 Number of rooted identity trees with n nodes and 3 leaves.

Original entry on oeis.org

1, 5, 13, 28, 53, 91, 146, 223, 326, 461, 634, 851, 1119, 1446, 1839, 2307, 2859, 3504, 4252, 5114, 6100, 7222, 8492, 9922, 11525, 13315, 15305, 17510, 19945, 22625, 25566, 28785, 32298, 36123, 40278, 44781, 49651, 54908, 60571, 66661

Offset: 6

Christian G. Bower, May 12 2000

			Illustration for a(7)=5 from _N. J. A. Sloane_, Mar 21 2016:
The five 7-node rooted identity trees with 3 leaves are:
(O denotes the root)
o
|
o o o
|/ /
o o
|/
O
..........
o
|
o   o
|  /
o o o
|//
O
..........
o
|
o
|
o o
|/
o o
|/
O
..............
o
|
o o
|/
o
|
o o
|/
O
..............
o
|
o o
|/
o o
|/
o
|
O
..............

Andrew Howroyd, Table of n, a(n) for n = 6..1000
Index entries for sequences related to rooted trees
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,0,1,2,-3,1).

Column 3 of A055327.

[(9*(1-(-1)^n) -272*n +216*n^2 -64*n^3 +6*n^4 +96*Floor((n+2)/3))/288: n in [6..46]]; // G. C. Greubel, Nov 09 2023

LinearRecurrence[{3,-2,-1,0,1,2,-3,1}, {1,5,13,28,53,91,146,223}, 40] (* Jean-François Alcover, Sep 06 2019 *)

Vec((2*x+1)/((1-x^2)*(1-x^3)*(1-x)^3) + O(x^40)) \\ Andrew Howroyd, Aug 28 2018

[(9*(n%2) -136*n +108*n^2 -32*n^3 +3*n^4 +48*((n+2)//3))/144 for n in range(6,47)] # G. C. Greubel, Nov 09 2023

G.f.: x^6*(1+2*x)/((1-x^2)*(1-x^3)*(1-x)^3).
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-5) + 2*a(n-6) - 3*a(n-7) + a(n-8) for n>13. - Colin Barker, Sep 06 2019
a(n) = (1/288)*(41 - 240*n + 216*n^2 - 64*n^3 + 6*n^4 - 9*(-1)^n - 32*ChebyshevU(n, -1/2)). - G. C. Greubel, Nov 09 2023

A317580 Number of unlabeled rooted identity trees with n nodes and a distinguished leaf.

Original entry on oeis.org

1, 1, 1, 3, 5, 12, 28, 66, 153, 367, 880, 2121, 5127, 12441, 30248, 73746, 180077, 440571, 1079438, 2648511, 6506170, 16001256, 39393173, 97074140, 239419963, 590972968, 1459808862, 3608483107, 8925476591, 22090139751, 54702648393, 135533335933, 335967782916

Offset: 1

Gus Wiseman, Jul 31 2018

nonn

Total number of leaves in all rooted identity trees with n nodes. - Andrew Howroyd, Aug 28 2018

			The a(6) = 12 rooted identity trees with a distinguished leaf:
(((((O))))),
(((O(o)))), (((o(O)))),
((O((o)))), ((o((O)))),
(O(((o)))), (o(((O)))),
((O)((o))), ((o)((O))),
(O(o(o))), (o(O(o))), (o(o(O))).

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

Cf. A000081, A001678, A003227, A003238, A004111, A038046, A055327, A067824, A301342, A316784.

urit[n_]:=Join@@Table[Select[Union[Sort/@Tuples[urit/@ptn]],UnsameQ@@#&],{ptn,IntegerPartitions[n-1]}];
Table[Sum[Length[Flatten[{t/.{}->1}]],{t,urit[n]}],{n,10}]

WeighMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, (-1)^(i-1)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
seq(n)={my(v=[y]); for(n=2, n, v=concat([y], WeighMT(v))); apply(p -> subst(deriv(p), y, 1), v)} \\ Andrew Howroyd, Aug 28 2018

a(n) = Sum_{k=1, n} k*A055327(n, k). - Andrew Howroyd, Aug 28 2018

Terms a(26) and beyond from Andrew Howroyd, Aug 28 2018

A055329 Number of rooted identity trees with n nodes and 4 leaves.

Original entry on oeis.org

2, 11, 40, 109, 254, 524, 998, 1774, 2995, 4833, 7525, 11346, 16659, 23877, 33528, 46203, 62637, 83643, 110213, 143432, 184600, 235129, 296687, 371072, 460382, 566866, 693121, 841917, 1016422, 1220001, 1456473, 1729878, 2044767, 2405940

Offset: 8

Christian G. Bower, May 12 2000

Andrew Howroyd, Table of n, a(n) for n = 8..1000
Index entries for sequences related to rooted trees
Index entries for linear recurrences with constant coefficients, signature (3,-1,-4,3,-1,3,0,-3,1,-3,4,1,-3,1).

Column 4 of A055327.

R:=PowerSeriesRing(Integers(), 50); Coefficients(R!( x^8*(2+5*x+9*x^2+8*x^3+5*x^4+x^6)/((1-x)^3*(1-x^2)^2*(1-x^3)*(1-x^4)) )); // G. C. Greubel, Nov 09 2023

Drop[CoefficientList[Series[x^8*(2+5*x+9*x^2+8*x^3+5*x^4+x^6)/((1-x)^3*(1-x^2)^2*(1-x^3)*(1-x^4)), {x,0,50}], x], 8] (* G. C. Greubel, Nov 09 2023 *)

Vec((2 + 5*x + 9*x^2 + 8*x^3 + 5*x^4 + x^6)/((1 - x)^7*(1 + x)^3*(1 + x^2)*(1 + x + x^2)) + O(x^40)) \\ Andrew Howroyd, Aug 28 2018

def A055329_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x^8*(2+5*x+9*x^2+8*x^3+5*x^4+x^6)/((1-x)^3*(1-x^2)^2*(1-x^3)*(1-x^4)) ).list()
a=A055329_list(50); a[8:] # G. C. Greubel, Nov 09 2023

G.f.: x^8*(2+5*x+9*x^2+8*x^3+5*x^4+x^6)/((1-x)^7*(1+x)^3*(1+x^2)*(1+x+x^2)) - Colin Barker, Nov 07 2012

a(n) = -[n=0] + (60*n^6 -1236*n^5 +9450*n^4 -33520*n^3 +59940*n^2 -66294*n +48065)/69120 +(-1)^n*(4*n^2 -38*n +89)/512 +(3/32)*(-1)^floor((n+1)/2) + ChebyshevU(n, -1/2)/27. - G. C. Greubel, Nov 09 2023

A055330 Number of rooted identity trees with n nodes and 5 leaves.

Original entry on oeis.org

3, 26, 116, 387, 1068, 2587, 5678, 11540, 22034, 39957, 69366, 116009, 187823, 295574, 453582, 680625, 1000952, 1445516, 2053343, 2873165, 3965216, 5403347, 7277330, 9695538, 12787847, 16708973, 21642067, 27802808, 35443793, 44859494, 56391551, 70434706

Offset: 10

Christian G. Bower, May 12 2000

Andrew Howroyd, Table of n, a(n) for n = 10..1000
Index entries for sequences related to rooted trees
Index entries for linear recurrences with constant coefficients, signature (4,-4,-3,7,-3,0,1,0,-3,0,3,0,-1,0,3,-7,3,4,-4,1).

Column 5 of A055327.

Cf. A061347, A257145.

R:=PowerSeriesRing(Integers(), 50); Coefficients(R!( x^10*(3 + 14*x+24*x^2+36*x^3+41*x^4+38*x^5+29*x^6+16*x^7+6*x^8+3*x^9)/((1-x)^3*(&*[1-x^j: j in [1..5]])) )); // G. C. Greubel, Nov 09 2023

Drop[CoefficientList[Series[x^10*(3+14*x+24*x^2+36*x^3+41*x^4+38*x^5+29*x^6 +16*x^7+6*x^8+3*x^9)/((1-x)^3*Product[1-x^j, {j,5}]), {x,0,40}], x], 10] (* G. C. Greubel, Nov 09 2023 *)

def p(x): return 3 +14*x +24*x^2 +36*x^3 +41*x^4 +38*x^5 +29*x^6 +16*x^7 +6*x^8 +3*x^9
def A055330_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x^10*p(x)/((1-x)^3*product(1-x^j for j in range(1,6))) ).list()
a=A055330_list(50); a[10:] # G. C. Greubel, Nov 09 2023

G.f.: x^10*(3 +14*x +24*x^2 +36*x^3 +41*x^4 +38*x^5 +29*x^6 +16*x^7 +6*x^8 +3*x^9)/((1-x)^9*(1+x)^3*(1+x^2)*(1+x+x^2)*(1+x+x^2+x^3+x^4)). - Colin Barker, Nov 07 2012

a(n) = (1/(8*10!))*(5303207 -25330590*n +28099260*n^2 -18286800*n^3 +7777980*n^4 -1990044*n^5 +286440*n^6 -21240*n^7 +630*n^8) -(-1)^n*(89 - 34*n +4*n^2)/2048 -(3/64)*(-1)^binomial(n+1,2) -A061347(n+1)/81 +A257145(n+2)/25. - G. C. Greubel, Nov 09 2023

A055331 Number of rooted identity trees with n nodes and 6 leaves.

Original entry on oeis.org

6, 61, 329, 1289, 4133, 11462, 28536, 65194, 138956, 279457, 535131, 982224, 1737756, 2976311, 4953198, 8033628, 12731680, 19758178, 30083086, 45010674, 66275305, 96155116, 137614204, 194469039, 271593493, 375156018, 512907786

Offset: 12

Christian G. Bower, May 12 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 12..500
Index entries for sequences related to rooted trees

Column 6 of A055327.

A055332 Number of rooted identity trees with n nodes and 7 leaves.

Original entry on oeis.org

12, 145, 911, 4121, 15029, 47022, 130895, 332175, 781542, 1726194, 3612937, 7218784, 13849864, 25637680, 45969845, 80105273, 136036089, 225677767, 366486971, 583634189, 912883787, 1404372594, 2127513223, 3177300763

Offset: 14

Christian G. Bower, May 12 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 14..500
Index entries for sequences related to rooted trees

Column 7 of A055327.

cp's OEIS Frontend

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A301342 Regular triangle where T(n,k) is the number of rooted identity trees with n nodes and k leaves.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A318227 Number of inequivalent leaf-colorings of rooted identity trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A055334 Number of asymmetric (identity) trees with n nodes and k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A055328 Number of rooted identity trees with n nodes and 3 leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A317580 Number of unlabeled rooted identity trees with n nodes and a distinguished leaf.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A055329 Number of rooted identity trees with n nodes and 4 leaves.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI