A032305 -id:A032305 - cp's OEIS frontend

A298535 Number of unlabeled rooted trees with n vertices such that every branch of the root has a different number of leaves.

1, 1, 1, 2, 5, 13, 32, 80, 200, 511, 1323, 3471, 9183, 24491, 65715, 177363, 481135, 1311340, 3589023, 9860254, 27181835, 75165194, 208439742, 579522977, 1615093755, 4511122964, 12625881944, 35405197065, 99459085125, 279861792874, 788712430532, 2226015529592

Offset: 1

Gus Wiseman, Jan 20 2018

nonn

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

Cf. A000081, A003238, A004111, A032305, A289079, A290689, A291443, A297791, A298422, A298533, A298536.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],UnsameQ@@(Count[#,{},{0,Infinity}]&/@#)&]],{n,15}]

\\ here R is A055277 as vector of polynomials
R(n) = {my(A = O(x)); 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) ) ))); Vec(A)};
seq(n) = {my(M=Mat(apply(p->Colrev(p,n), R(n-1)))); Vec(prod(i=2, #M, 1 + x*Ser(M[i,])))} \\ Andrew Howroyd, May 20 2018

Terms a(19) and beyond from Andrew Howroyd, May 20 2018

A300440 Number of odd strict trees of weight n (all outdegrees are odd).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 3, 5, 7, 11, 18, 27, 45, 75, 125, 207, 353, 591, 1013, 1731, 2984, 5122, 8905, 15369, 26839, 46732, 81850, 142932, 251693, 441062, 778730, 1370591, 2425823, 4281620, 7601359, 13447298, 23919512, 42444497, 75632126, 134454505, 240100289

Offset: 1

Gus Wiseman, Mar 05 2018

nonn

An odd strict tree of weight n is either a single node of weight n, or a finite odd-length sequence of at least 3 odd strict trees with strictly decreasing weights summing to n.

			The a(10) = 7 odd strict trees: 10, (721), (631), (541), (532), ((421)21), ((321)31).

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

Cf. A000009, A000992, A032305, A063834, A078408, A089259, A196545, A273873, A279785, A289501, A298118, A300301, A300352, A300353, A300436, A300439.

g[n_]:=g[n]=1+Sum[Times@@g/@y,{y,Select[IntegerPartitions[n],Length[#]>1&&OddQ[Length[#]]&&UnsameQ@@#&]}];
Array[g,20]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(prod(k=1, n-1, 1 + v[k]*x^k + O(x*x^n)) - prod(k=1, n-1, 1 - v[k]*x^k + O(x*x^n)), n)/2); v} \\ Andrew Howroyd, Aug 25 2018

A093635 G.f.: A(x) = Product_{n>=0} (1+a(n)x^(n+1))^2 = Sum_{n>=0} a(n)x^n.

Original entry on oeis.org

1, 2, 5, 18, 64, 258, 1061, 4572, 19809, 88972, 400600, 1844602, 8511540, 39919338, 187389085, 891158688, 4238242129, 20365627200, 97881057229, 474301930632, 2297986873946, 11213069093460, 54697034675149, 268399278895406

Offset: 0

Paul D. Hanna, Apr 07 2004

nonn

Equals the self-convolution of A093636.

			( (1+x)(1+2x^2)(1+5x^3)(1+18x^4) )^2 = 1+2x+5x^2+18x^3+...

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A032305, A093636.

A:= proc(n) option remember; local i, p, q; if n=0 then 1 else
      p, q:= A(n-1), 1; for i from 0 to n-1 do q:= convert(
        series(q*(1+coeff(p, x, i)*x^(i+1))^2, x, n+1), polynom)
      od: q fi
    end:
a:= n-> coeff(A(n), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 01 2013

a[n_] := a[n] = SeriesCoefficient[Product[(1+a[i]*x^(i+1))^2, {i, 0, n-1}], {x, 0, n}];
a /@ Range[0, 30] (* Jean-François Alcover, Nov 02 2020, after PARI *)

a(n) =polcoeff(prod(i=0,n-1,(1+a(i)*x^(i+1))^2)+x*O(x^n),n)

A124973 a(n) = Sum_{k=0..(n-2)/2} a(k)a*(n-1-k), with a(0) = a(1) = 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 11, 22, 42, 87, 174, 365, 745, 1587, 3303, 7103, 14974, 32477, 69284, 151172, 325077, 713400, 1545719, 3406989, 7423648, 16429555, 35992438, 79912474, 175785514, 391488688, 864591621, 1930333822, 4276537000

Offset: 0

Franklin T. Adams-Watters, Nov 14 2006

Number of unordered rooted trees with all outdegrees <= 2 and, if a node has two subtrees, they have a different number of nodes (equivalently, ordered rooted trees where the left subtree has more nodes than the right subtree).

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A000108, A000992, A001190, A032305.

a:= proc(n) option remember;
      if n<2 then 1
    else add(a(j)*a(n-j-1), j=0..floor((n-2)/2))
      fi
    end:
seq(a(n), n=0..40); # G. C. Greubel, Nov 19 2019

a[n_]:= a[n]= If[n<2, 1, Sum[a[j]*a[n-j-1], {j, 0, (n-2)/2}]]; Table[a[n], {n, 0, 40}] (* G. C. Greubel, Nov 19 2019 *)

a(n) = if(n<2, 1, sum(j=0, (n-2)\2, a(j)*a(n-j-1))); \\ G. C. Greubel, Nov 19 2019

@CachedFunction
def a(n):
    if (n<2): return 1
    else: return sum(a(j)*a(n-j-1) for j in (0..floor((n-2)/2)))
[a(n) for n in (0..40)] # G. C. Greubel, Nov 19 2019

Lim_{n->infinity} a(n)^(1/n) = 2.327833478... - Vaclav Kotesovec, Nov 20 2019

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 2, 3, 5, 9, 15, 27, 47, 87, 155, 288, 524, 983, 1813, 3434, 6396, 12174, 22891, 43810, 82925, 159432, 303559, 585966, 1121446, 2171341, 4172932, 8106485, 15635332, 30445899, 58925280, 115014681, 223210718, 436603718, 849480835, 1664740873

Offset: 0

Gus Wiseman, Mar 21 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..3266

Cf. A032305, A055277, A093637, A127524, A196545, A220418, A273866, A273873, A289501, A290261, A290971, A301342-A301345, A301364-A301368, A301422, A301462, A301467, A301469.

b:= proc(n, i) option remember; `if`(n=0, 1,
     `if`(i<1, 0, b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
    end:
a:= n-> `if`(n<2, 1-n, b(n-2$2)+b(n-1, n-2)):
seq(a(n), n=0..45);  # Alois P. Heinz, Jun 23 2018

a[n_]:=a[n]=(-1)^n+Sum[Times@@a/@y,{y,IntegerPartitions[n-1]}];
Array[a,30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1,
     If[i < 1, 0, b[n, i - 1] + a[i] b[n - i, Min[n - i, i]]]];
a[n_] := If[n < 2, 1 - n, b[n - 2, n - 2] + b[n - 1, n - 2]];
a /@ Range[0, 45] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

O.g.f.: 1/(1 + x) + x Product_{i > 0} 1/(1 - a(i) x^i).

a(n) = Sum_t (-1)^w(t) where the sum is over all enriched r-trees of size n and w(t) is the sum of leaves of t.

A298478 Number of unlabeled rooted trees with n nodes in which all positive outdegrees are different.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 13, 15, 23, 34, 95, 106, 176, 241, 374, 942, 1129, 1760, 2515, 3711, 5136, 12857, 14911, 23814, 33002, 49141, 65798, 97056, 209707, 255042, 389725, 545290, 790344, 1071010, 1525919, 2043953, 4272124, 5110583, 7772247, 10611491, 15447864, 20496809

Offset: 1

Gus Wiseman, Jan 19 2018

nonn

a(n) is the number of labeled trees with sum of the labels equal to n-1 and the outdegree of every node less than or equal to the value of its label. - Andrew Howroyd, Feb 02 2021

			The a(7) = 13 trees: ((o(ooo))), ((oo(oo))), ((ooooo)), (o((ooo))), (o(oo(o))), (o(oooo)), ((o)(ooo)), (oo((oo))), (oo(o(o))), (o(o)(oo)), (ooo(oo)), (oooo(o)), (oooooo).

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

Cf. A000081, A001190, A001678, A004111, A032305, A124343, A290689, A295461, A298118, A298304, A298422, A298479.

krut[n_]:=krut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[krut/@c]]]/@IntegerPartitions[n-1],UnsameQ@@Length/@Cases[#,{},{0,Infinity}]&]];
Table[krut[n]//Length,{n,15}]

relabel(b)={my(w=hammingweight(b)); b = bitand((1<Andrew Howroyd, Feb 02 2021

a(27)-a(34) from Robert G. Wilson v, Jan 19 2018

Terms a(35) and beyond from Andrew Howroyd, Feb 02 2021

A298537 Number of unlabeled rooted trees with n nodes such that every branch of the root has the same number of nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 25, 49, 127, 291, 766, 1843, 5003, 12487, 34151, 87983, 242088, 634848, 1763749, 4688677, 13085621, 35241441, 98752586, 268282856, 755353825, 2067175933, 5837592853, 16087674276, 45550942142, 126186554309, 358344530763, 997171512999

Offset: 1

Gus Wiseman, Jan 20 2018

nonn

			The a(5) = 6 trees: ((((o)))), (((oo))), ((o(o))), ((ooo)), ((o)(o)), (oooo).

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A000081, A003238, A004111, A032305, A289078, A289079, A290689, A291443, A297791, A298422, A298533, A298535, A298538, A298539.

r[n_]:=r[n]=If[n===1,1,Sum[Product[Binomial[r[x]+Count[ptn,x]-1,Count[ptn,x]],{x,Union[ptn]}],{ptn,IntegerPartitions[n-1]}]];
Table[If[n===1,1,Sum[Binomial[r[(n-1)/d]+d-1,d],{d,Divisors[n-1]}]],{n,40}]

a(n + 1) = Sum_{d|n} binomial(A000081(n/d) + d - 1, d).

A298539 Number of unlabeled rooted trees with n vertices such that every branch of the root has a different number of nodes.

Original entry on oeis.org

1, 1, 1, 3, 6, 15, 35, 89, 218, 571, 1446, 3834, 10003, 26864, 71120, 193602, 519409, 1423539, 3865590, 10666555, 29185905, 81078369, 223367624, 623192655, 1727907182, 4840616872, 13482957335, 37923616139, 106070402639, 299214369115, 840217034149

Offset: 1

Gus Wiseman, Jan 21 2018

nonn

			The a(5) = 6 trees: ((((o)))), (((oo))), ((o(o))), ((ooo)), (o((o))), (o(oo)).

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A000081, A004111, A032305, A290689, A298422, A298533, A298535, A298537, A298539.

nn=20;
r[n_]:=r[n]=If[n===1,1,Sum[Product[Binomial[r[x]+Count[ptn,x]-1,Count[ptn,x]],{x,Union[ptn]}],{ptn,IntegerPartitions[n-1]}]];
Table[SeriesCoefficient[Product[1+r[n]x^n,{n,nn}],{x,0,n}],{n,0,nn}]

G.f.: Product_{n>0} (1 + A000081(n) x^n).

A300797 Number of strict trees of weight 2n + 1 in which all outdegrees and all leaves are odd.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 17, 34, 59, 118, 213, 424, 799, 1606, 3072, 6216, 12172, 24650, 48710, 99333, 198237, 405526, 815267, 1673127, 3387165, 6974702, 14179418, 29285048, 59841630, 123848399, 253927322, 526936694, 1084022437, 2253778793, 4649778115

Offset: 0

Gus Wiseman, Mar 13 2018

nonn

A strict tree of weight n > 0 is either a single node of weight n, or a sequence of two or more strict trees with strictly decreasing weights summing to n.

			The a(7) = 6 strict trees: 15, (11 3 1), (9 5 1), (7 5 3), ((7 3 1) 3 1), ((5 3 1) 5 1).

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

Cf. A000009, A000992, A032305, A063834, A078408, A089259, A196545, A273873, A279785, A289501, A298118, A300301, A300352, A300353, A300436, A300439, A300440, A300652.

a[n_]:=a[n]=If[OddQ[n],1,0]+Sum[Times@@a/@ptn,{ptn,Select[IntegerPartitions[n],Length[#]>1&&OddQ[Length[#]]&&UnsameQ@@#&]}];
Table[a[n],{n,1,60,2}]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(prod(k=1, n-1, 1 + v[k]*x^(2*k-1) + O(x^(2*n))) - prod(k=1, n-1, 1 - v[k]*x^(2*k-1) + O(x^(2*n))), 2*n-1)/2); v} \\ Andrew Howroyd, Aug 26 2018

a(30)-a(37) from Alois P. Heinz, Mar 13 2018

A301469 Signed recurrence over enriched r-trees: a(n) = 2 * (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Original entry on oeis.org

2, -1, 1, 0, 0, 1, 0, 1, 1, 1, 2, 3, 3, 6, 7, 11, 17, 23, 35, 53, 75, 119, 173, 264, 398, 603, 911, 1411, 2114, 3279, 4977, 7696, 11760, 18253, 27909, 43451, 66675, 103945, 160096, 249904, 385876, 603107, 933474, 1461967, 2266384, 3553167, 5521053, 8664117, 13485744

Offset: 0

Gus Wiseman, Mar 21 2018

sign

Cf. A032305, A055277, A093637, A127524, A196545, A220418, A273866, A273873, A289501, A290261, A290973, A301342-A301345, A301364-A301368, A301422, A301462, A301467, A301470.

a[n_]:=a[n]=2(-1)^n+Sum[Times@@a/@y,{y,IntegerPartitions[n-1]}];
Array[a,30]

O.g.f.: 2/(1 + x) + x Product_{i > 0} 1/(1 - a(i) x^i).

a(n) = Sum_t 2^k * (-1)^w where the sum is over all enriched r-trees of size n, k is the number of leaves, and w is the sum of leaves.

cp's OEIS Frontend

A298535 Number of unlabeled rooted trees with n vertices such that every branch of the root has a different number of leaves.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A300440 Number of odd strict trees of weight n (all outdegrees are odd).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A093635 G.f.: A(x) = Product_{n>=0} (1+a(n)*x^(n+1))^2 = Sum_{n>=0} a(n)*x^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A124973 a(n) = Sum_{k=0..(n-2)/2} a(k)a*(n-1-k), with a(0) = a(1) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A298478 Number of unlabeled rooted trees with n nodes in which all positive outdegrees are different.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A298537 Number of unlabeled rooted trees with n nodes such that every branch of the root has the same number of nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A298539 Number of unlabeled rooted trees with n vertices such that every branch of the root has a different number of nodes.

A093635 G.f.: A(x) = Product_{n>=0} (1+a(n)x^(n+1))^2 = Sum_{n>=0} a(n)x^n.