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

A331991 Number of semi-lone-child-avoiding achiral rooted trees with n vertices.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 4, 1, 5, 1, 5, 4, 4, 1, 7, 1, 7, 5, 6, 1, 7, 3, 7, 5, 7, 1, 13, 1, 8, 6, 6, 6, 10, 1, 9, 7, 9, 1, 15, 1, 12, 12, 8, 1, 12, 4, 13, 6, 11, 1, 15, 7, 13, 9, 9, 1, 17, 1, 15, 15, 9, 8, 21, 1, 13, 8, 16, 1, 18, 1, 12, 16, 11, 8, 21, 1

Offset: 1

Gus Wiseman, Feb 06 2020

nonn

A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless that child is an endpoint/leaf.

In an achiral rooted tree, the branches of any given vertex are all equal.

			The a(n) trees for n = 2, 3, 5, 7, 11, 13:
  (o)  (oo)  (oooo)    (oooooo)     (oooooooooo)        (oooooooooooo)
             ((o)(o))  ((oo)(oo))   ((oooo)(oooo))      ((ooooo)(ooooo))
                       ((o)(o)(o))  ((o)(o)(o)(o)(o))   ((ooo)(ooo)(ooo))
                                    (((o)(o))((o)(o)))  ((oo)(oo)(oo)(oo))
                                                        ((o)(o)(o)(o)(o)(o))

Seiichi Manyama, Table of n, a(n) for n = 1..10000
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Matula-Goebel numbers of these trees are A331992.
The fully lone-child-avoiding case is A167865.
The semi-achiral version is A331933.
Not requiring achirality gives A331934.
The identity tree version is A331964.
The semi-identity tree version is A331993.
Achiral rooted trees are counted by A003238.
Lone-child-avoiding semi-achiral trees are A320268.
Cf. A000081, A004111, A050381, A001678, A214577, A289079, A320222, A331912, A331935, A331936, A331963, A331967, A331994.

ab[n_]:=If[n<=2,1,Sum[ab[d],{d,Most[Divisors[n-1]]}]];
Array[ab,100]

a(1) = a(2) = 1; a(n + 1) = Sum_{d|n, d 1.

G.f. A(x) satisfies: A(x) = x * (1 + (1/(1 + x)) * Sum_{k>=1} A(x^k)). - Ilya Gutkovskiy, Feb 25 2020

A300648 Number of orderless same-trees of weight n in which all outdegrees are odd.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 1, 6, 2, 2, 2, 2, 2, 12, 1, 2, 6, 2, 2, 14, 2, 2, 2, 8, 2, 68, 2, 2, 12, 2, 1, 18, 2, 16, 6, 2, 2, 20, 2, 2, 14, 2, 2, 644, 2, 2, 2, 10, 8, 24, 2, 2, 68, 20, 2, 26, 2, 2, 12, 2, 2, 1386, 1, 22, 18, 2, 2, 30, 16, 2, 6, 2, 2, 4532, 2, 22, 20

Offset: 1

Gus Wiseman, Mar 10 2018

An orderless same-tree of weight n > 0 is either a single node of weight n, or a finite multiset of two or more orderless same-trees whose weights are all equal and sum to n.

			The a(9) = 6 odd orderless same-trees: 9, (333), (33(111)), (3(111)(111)), ((111)(111)(111)), (111111111).

Antti Karttunen, Table of n, a(n) for n = 1..8192

Cf. A003238, A006241, A063834, A069283, A273873, A281145, A289078, A289079, A289501, A298118, A300436, A300439, A300574, A300647, A300649, A300650.

a[n_]:=1+Sum[Binomial[a[n/d]+d-1,d],{d,Select[Rest[Divisors[n]],OddQ]}];
Array[a,80]

a(n) = if (n==1, 1, 1 + sumdiv(n, d, if ((d > 1) && (d % 2), binomial(a(n/d) + d - 1, d)))); \\ Michel Marcus, Mar 10 2018

a(n) = 1 + Sum_d binomial(a(n/d) + d - 1, d) where the sum is over odd divisors of n greater than 1.

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

A300649 Number of same-trees of weight 2n + 1 in which all outdegrees are odd and all leaves greater than 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 3, 1, 2, 10, 1, 1, 3, 3, 1, 3, 1, 1, 62, 1, 2, 3, 1, 3, 3, 1, 1, 158, 3, 1, 3, 1, 1, 254, 3, 1, 1514, 1, 3, 3, 1, 3, 3, 3, 1, 2078, 1, 1, 2461, 1, 1, 3, 1, 3, 8222, 3, 2, 3, 34, 1, 3, 1, 3, 390782, 1, 1, 3, 3, 3, 2198, 1, 1

Offset: 0

Gus Wiseman, Mar 10 2018

nonn

A same-tree of weight n > 0 is either a single node of weight n, or a finite sequence of two or more same-trees whose weights are all equal and sum to n.

			The a(13) = 10 odd same-trees with all leaves greater than 1:
27,
(999),
(99(333)), (9(333)9), ((333)99),
(9(333)(333)), ((333)9(333)), ((333)(333)9),
((333)(333)(333)), (333333333).

Cf. A003238, A006241, A063834, A069283, A273873, A281145, A289078, A289079, A289501, A298118, A300436, A300439, A300574, A300647, A300648, A300650.

a[n_]:=If[n===1,1,Sum[a[n/d]^d,{d,Select[Rest[Divisors[n]],OddQ]}]];
Table[a[n],{n,1,100,2}]

f(n) = if (n==1, 1, sumdiv(n, d, if ((d > 1) && (d % 2), f(n/d)^d)));
a(n) = f(2*n+1); \\ Michel Marcus, Mar 10 2018

a(1) = 1; a(n > 1) = Sum_d a(n/d)^d where the sum is over odd divisors of n greater than 1.

A300650 Number of orderless same-trees of weight 2n + 1 in which all outdegrees are odd and all leaves greater than 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 3, 1, 2, 6, 1, 1, 3, 3, 1, 3, 1, 1, 19, 1, 2, 3, 1, 3, 3, 1, 1, 21, 3, 1, 3, 1, 1, 28, 3, 1, 68, 1, 3, 3, 1, 3, 3, 3, 1, 25, 1, 1, 71, 1, 1, 3, 1, 3, 27, 3, 2, 3, 8, 1, 3, 1, 3, 1656, 1, 1, 3, 3, 3, 43, 1, 1, 31, 3, 1, 3, 3, 1

Offset: 0

Gus Wiseman, Mar 10 2018

nonn

An orderless same-tree of weight n > 0 is either a single node of weight n, or a finite multiset of two or more orderless same-trees whose weights are all equal and sum to n.

			The a(13) = 6 orderless same-trees: 27, (999), (99(333)), (9(333)(333)), ((333)(333)(333)), (333333333).

Cf. A003238, A006241, A063834, A069283, A273873, A281145, A289078, A289079, A289501, A298118, A300436, A300439, A300574, A300647, A300648, A300649.

a[n_]:=If[n===1,1,Sum[Binomial[a[n/d]+d-1,d],{d,Select[Rest[Divisors[n]],OddQ]}]];
Table[a[n],{n,1,100,2}]

f(n) = if (n==1, 1, sumdiv(n, d, if ((d > 1) && (d % 2), binomial(f(n/d)+d-1, d))));
a(n) = f(2*n+1); \\ Michel Marcus, Mar 10 2018

a(1) = 1; a(n > 1) = Sum_d binomial(a(n/d) + d - 1, d) where the sum is over odd divisors of n greater than 1.

A301367 Regular triangle where T(n,k) is the number of orderless same-trees of weight n with k leaves.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 0, 0, 0, 1, 1, 1, 1, 2, 1, 3, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 4, 4, 3, 5, 1, 0, 1, 0, 1, 0, 1, 0, 2, 1, 1, 0, 0, 1, 2, 1, 1, 1, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 4, 5, 10, 11, 14, 12, 14, 7, 13, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Mar 19 2018

An orderless same-tree of weight n > 0 is either a single node of weight n, or a finite multiset of two or more orderless same-trees whose weights are all the same and sum to n.

			Triangle begins:
1
1   1
1   0   1
1   1   1   2
1   0   0   0   1
1   1   1   2   1   3
1   0   0   0   0   0   1
1   1   1   3   4   4   3   5
1   0   1   0   1   0   1   0   2
1   1   0   0   1   2   1   1   1   3
1   0   0   0   0   0   0   0   0   0   1
1   1   2   4   5  10  11  14  12  14   7  13
1   0   0   0   0   0   0   0   0   0   0   0   1
1   1   0   0   0   0   1   2   1   1   1   1   1   3
The T(8,5) = 4 orderless same-trees: (4((11)(11))), (4(1111)), ((22)(2(11))), (222(11)).

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

Last entries of each row give A289079. Row sums are A289078.

Cf. A003238, A006241, A008284, A055277, A063834, A273873, A281145, A289501, A294080, A298422, A298426, A299201, A299203, A301343, A301364-A301368.

olstrees[n_]:=Prepend[Join@@Table[Select[Tuples[olstrees/@ptn],OrderedQ],{ptn,Select[IntegerPartitions[n],Length[#]>1&&SameQ@@#&]}],n];
Table[Length[Select[olstrees[n],Count[#,_Integer,{-1}]===k&]],{n,14},{k,n}]

S(g, k)={polcoef(exp(sum(i=1, k, x^i*subst(g, y, y^i)/i) + O(x*x^k)), k)}
A(n)={my(v=vector(n)); for(n=1, n, v[n] = y + sumdiv(n, d, S(v[n/d], d))); apply(p -> Vecrev(p/y), v)}
{ my(v=A(16)); for(n=1, #v, print(v[n])) } \\ Andrew Howroyd, Aug 20 2018

A305572 a(n) = (-1)^(n-1) + Sum_{d|n, d>1} a(n/d)^d.

Original entry on oeis.org

1, 0, 2, 0, 2, 4, 2, 0, 10, 4, 2, 32, 2, 4, 42, 0, 2, 228, 2, 32, 138, 4, 2, 1536, 34, 4, 1514, 32, 2, 3940, 2, 0, 2058, 4, 162, 102944, 2, 4, 8202, 1536, 2, 51940, 2, 32, 207370, 4, 2, 3538944, 130, 3204, 131082, 32, 2, 15668836, 2082, 1536, 524298, 4, 2, 54327840

Offset: 1

Gus Wiseman, Jun 05 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..6911

Cf. A196545, A273873, A281145, A289078, A289079, A289501, A290261, A290971, A291441, A300862-A300866.

a[n_]:=a[n]=(-1)^(n-1)+Sum[a[n/y]^y,{y,Divisors[n]//Rest}];
Array[a,40]

A305572(n) = ((-1)^(n-1) + sumdiv(n,d,if(d==1,0,A305572(n/d)^d))); \\ Antti Karttunen, Dec 05 2021

a(n) = Sum_t (-1)^(n-k) where the sum is over all same-trees of weight n (see A281145 for definition) and k is the number of leaves.

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

Original entry on oeis.org

1, 0, 2, 0, 2, 3, 2, 0, 6, 3, 2, 11, 2, 3, 12, 0, 2, 38, 2, 11, 14, 3, 2, 90, 8, 3, 68, 11, 2, 127, 2, 0, 18, 3, 16, 1194, 2, 3, 20, 90, 2, 173, 2, 11, 644, 3, 2, 5158, 10, 68, 24, 11, 2, 12762, 20, 90, 26, 3, 2, 12910, 2, 3, 1386, 0, 22, 289, 2, 11, 30, 219, 2

Offset: 1

Gus Wiseman, Jun 06 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A063834, A196545, A220418, A273866, A273873, A275870, A281145, A281146, A289078, A289079, A289501, A290261, A290971, A291441, A300862-A300866.

a[n_]:=a[n]=(-1)^(n-1)+Sum[Binomial[a[n/d]+d-1,d],{d,Divisors[n]//Rest}];
Array[a,40]

A305610(n) = ((-1)^(n-1) + sumdiv(n,d,if(d==1,0,binomial(A305610(n/d)+d-1, d)))); \\ Antti Karttunen, Dec 05 2021

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

A331991 Number of semi-lone-child-avoiding achiral rooted trees with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A300648 Number of orderless same-trees of weight n in which all outdegrees are odd.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A300649 Number of same-trees of weight 2n + 1 in which all outdegrees are odd and all leaves greater than 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A300650 Number of orderless same-trees of weight 2n + 1 in which all outdegrees are odd and all leaves greater than 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A301367 Regular triangle where T(n,k) is the number of orderless same-trees of weight n with k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A305572 a(n) = (-1)^(n-1) + Sum_{d|n, d>1} a(n/d)^d.

Views

Author