A289079 -id:A289079 - cp's OEIS frontend

A167865 Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.

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

Offset: 0

Max Alekseyev, Nov 13 2009

Number of lone-child-avoiding achiral rooted trees with n + 1 vertices, where a rooted tree is lone-child-avoiding if all terminal subtrees have at least two branches, and achiral if all branches directly under any given vertex are equal. The Matula-Goebel numbers of these trees are given by A331967. - Gus Wiseman, Feb 07 2020

			a(12) = 4: [12], [10,2], [9,3], [8,4].
a(14) = 3: [14], [12,2], [8,4,2].
a(18) = 5: [18], [16,2], [15,3], [12,6], [12,4,2].
From _Gus Wiseman_, Jul 13 2018: (Start)
The a(36) = 8 lone-child-avoiding achiral rooted trees with 37 vertices:
  (oooooooooooooooooooooooooooooooooooo)
  ((oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo))
  ((ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo))
  ((ooooo)(ooooo)(ooooo)(ooooo)(ooooo)(ooooo))
  ((oooooooo)(oooooooo)(oooooooo)(oooooooo))
  (((ooo)(ooo))((ooo)(ooo))((ooo)(ooo))((ooo)(ooo)))
  ((ooooooooooo)(ooooooooooo)(ooooooooooo))
  ((ooooooooooooooooo)(ooooooooooooooooo))
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A001678, A067824, A122651, A167439, A167865, A167866, A184998, A316782.
The semi-achiral version is A320268.
Matula-Goebel numbers of these trees are A331967.
The semi-lone-child-avoiding version is A331991.
Achiral rooted trees are counted by A003238.
Cf. A000081, A000669, A289079, A320222, A331912, A331933, A331936, A331992.

with(numtheory):
a:= proc(n) option remember;
      `if`(n=0, 1, add(a((n-d)/d), d=divisors(n) minus{1}))
    end:
seq(a(n), n=0..200);  # Alois P. Heinz, Mar 28 2011

a[0] = 1; a[n_] := a[n] = DivisorSum[n, a[(n-#)/#]&, #>1&]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 07 2015 *)

{ A167865(n) = if(n==0,return(1)); sumdiv(n,d, if(d>1, A167865((n-d)\d) ) ) }

a(0) = 1 and for n>=1, a(n) = Sum_{d|n, d>1} a((n-d)/d).

G.f. A(x) satisfies: A(x) = 1 + x^2*A(x^2) + x^3*A(x^3) + x^4*A(x^4) + ... - Ilya Gutkovskiy, May 09 2019

A300273 Sorted list of Heinz numbers of collapsible integer partitions.

Original entry on oeis.org

2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 36, 37, 40, 41, 43, 47, 48, 49, 53, 59, 61, 63, 64, 67, 71, 73, 79, 81, 83, 84, 89, 97, 101, 103, 107, 108, 109, 112, 113, 121, 125, 127, 128, 131, 137, 139, 144, 149, 151, 157, 163, 167, 169

Offset: 1

Gus Wiseman, Mar 01 2018

nonn

A positive integer is in this sequence iff it can be reduced to a prime number by a sequence of collapses, where a collapse is a replacement of prime(n)^k with prime(n*k) in a number's prime factorization (k > 1).

			A sequence of collapses is 84 -> 63 -> 49 -> 19 corresponding to the sequence of partitions (4211) -> (422) -> (44) -> (8). Hence 84 is in the sequence.

Cf. A000041, A001222, A002577, A005117, A018818, A056239, A094457, A112798, A145515, A215366, A275870, A289078, A289079, A291441, A296150, A299202.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
repcaps[q_]:=Union[{q},If[SquareFreeQ[q],{},Union@@repcaps/@Union[Times[q/#,Prime[Plus@@primeMS[#]]]&/@Select[Rest[Divisors[q]],!PrimeQ[#]&&PrimePowerQ[#]&]]]];
Select[Range[200],MemberQ[repcaps[#],_?PrimeQ]&]

A298422 Number of rooted trees with n nodes in which all positive outdegrees are the same.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 2, 20, 2, 26, 12, 53, 2, 120, 2, 223, 43, 454, 2, 1100, 11, 2182, 215, 4902, 2, 11446, 2, 24744, 1242, 56014, 58, 131258, 2, 293550, 7643, 676928, 2, 1582686, 2, 3627780, 49155, 8436382, 2, 19809464, 50, 46027323, 321202

Offset: 1

Gus Wiseman, Jan 19 2018

nonn

Row sums of A298426.

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

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

Cf. A000005, A000081, A000598, A001190, A001678, A003238, A004111, A008864, A032305, A067538, A111299, A124343, A143773, A289078, A289079, A295461, A298118, A298204, A298423, A298424, A298426.

srut[n_]:=srut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[srut/@c]]]/@Select[IntegerPartitions[n-1],Function[ptn,And@@(Divisible[#-1,Length[ptn]]&/@ptn)]],SameQ@@Length/@Cases[#,{},{0,Infinity}]&]];
Table[srut[n]//Length,{n,20}]

a(n) = 2 <=> n in {A008864}. - Alois P. Heinz, Jan 20 2018

a(44)-a(52) from Alois P. Heinz, Jan 20 2018

A289078 Number of orderless same-trees of weight n.

Original entry on oeis.org

1, 2, 2, 5, 2, 9, 2, 22, 6, 11, 2, 94, 2, 13, 12, 334, 2, 205, 2, 210, 14, 17, 2, 7218, 8, 19, 68, 443, 2, 1687, 2, 69109, 18, 23, 16, 167873, 2, 25, 20, 89969, 2, 7041, 2, 1548, 644, 29, 2, 36094795, 10, 3078, 24, 2604, 2, 1484102, 20, 1287306, 26, 35, 2

Offset: 1

Gus Wiseman, Jun 23 2017

nonn

An orderless same-tree t is either: (case 1) a positive integer, or (case 2) a finite multiset of two or more orderless same-trees, all having the same weight. The weight of t in case 1 is the number itself, and in case 2 it is the sum of weights of the branches. For example {{{3,{1,1,1}},{2,{1,1},{1,1}}},{{{1,1,1},{1,1,1}},{{1,1},{1,1},{1,1}}}} is an orderless same-tree of weight 24 with 2 branches.

			The a(6)=9 orderless same-trees are: 6, (33), (3(111)), (222), (22(11)), (2(11)(11)), ((11)(11)(11)), ((111)(111)), (111111).

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

Cf. A196545, A273873, A275870, A281145, A281146, A289079.

with(numtheory):
a:= proc(n) option remember; 1 + add(
      binomial(a(n/d)+d-1, d), d=divisors(n) minus {1})
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, Jul 05 2017

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

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sumdiv(n, d, binomial(v[n/d]+d-1, d))); v} \\ Andrew Howroyd, Aug 20 2018

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

A298426 Regular triangle where T(n,k) is number of k-ary rooted trees with n nodes.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 3, 0, 1, 0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 6, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 11, 4, 2, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 23, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Jan 19 2018

Row sums are A298422.

			Triangle begins:
1
0  1
0  1  1
0  1  0  1
0  1  1  0  1
0  1  0  0  0  1
0  1  2  1  0  0  1
0  1  0  0  0  0  0  1
0  1  3  0  1  0  0  0  1
0  1  0  2  0  0  0  0  0  1
0  1  6  0  0  1  0  0  0  0  1
0  1  0  0  0  0  0  0  0  0  0  1
0  1  11 4  2  0  1  0  0  0  0  0  1
0  1  0  0  0  0  0  0  0  0  0  0  0  1
0  1  23 0  0  0  0  1  0  0  0  0  0  0  1
0  1  0  8  0  2  0  0  0  0  0  0  0  0  0  1

Alois P. Heinz, Rows n = 1..200, flattened

Cf. A000005, A000081, A000598, A001190, A001678, A003238, A004111, A067538, A143773, A289078, A289079, A295461, A298118, A298422, A298423, A298424.

nn=16;
arut[n_,k_]:=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[arut[#,k]&/@c]]]/@Select[IntegerPartitions[n-1],Length[#]===k&]]
Table[arut[n,k]//Length,{n,nn},{k,0,n-1}]

A291441 Matula-Goebel numbers of orderless same-trees with all leaves equal to 1.

Original entry on oeis.org

1, 4, 8, 16, 32, 49, 64, 128, 256, 343, 361, 512, 1024, 2048, 2401, 2809, 4096, 6859, 8192, 12031, 16384, 16807, 17161, 32768, 51529, 65536, 96721, 117649, 130321, 131072, 148877, 262144, 516961, 524288, 637643, 718099, 757907, 823543, 1048576, 2097152, 2248091

Offset: 1

Gus Wiseman, Aug 23 2017

nonn

See A289078 for the definition of orderless same-tree.

			a(20)=12031 corresponds to the following same-tree: {{1,1,1,1},{{1,1},{1,1}}}.

Cf. A007097, A109129, A214577, A280994, A289078, A289079, A291442, A291443.

nn=200000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
leafcount[n_]:=If[n===1,1,With[{m=primeMS[n]},If[Length[m]===1,leafcount[First[m]],Total[leafcount/@m]]]];
sameQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]>1,SameQ@@leafcount/@m,And@@sameQ/@m]]];
Select[Range[nn],sameQ]

More terms from Jinyuan Wang, Jun 21 2020

A297791 Number of series-reduced leaf-balanced rooted trees with n nodes. Number of orderless same-trees with n nodes and all leaves equal to 1.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 5, 1, 3, 3, 4, 3, 5, 3, 6, 4, 6, 3, 12, 3, 10, 7, 9, 6, 12, 9, 13, 16, 14, 22, 22, 24, 21, 24, 28, 14, 32, 15, 42, 20, 60, 27, 84, 44, 100, 59, 113, 74, 116, 85, 110, 97, 96, 113, 106, 149, 147, 234, 235, 377, 380, 580, 576, 838

Offset: 1

Gus Wiseman, Jan 06 2018

nonn

An unlabeled rooted tree is leaf-balanced if all branches from the same root have the same number of leaves. It is series-reduced if all positive out-degrees are greater than one.

			The a(13) = 5 trees: (((oo)(oo))(oooo)), ((ooooo)(ooooo)), ((ooo)(ooo)(ooo)), ((oo)(oo)(oo)(oo)), (oooooooooooo).

Robert G. Wilson v, Table of n, a(n) for n = 1..84

Cf. A000081, A001190, A001678, A006241, A032305, A289078, A289079, A291441, A291443.

alltim[n_]:=alltim[n]=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[alltim/@c]],And[SameQ@@(Count[#,{},{0,Infinity}]&/@#),FreeQ[#,{_}]]&]]/@IntegerPartitions[n-1]];
Table[Length[alltim[n]],{n,20}]

lista(nn) = my(k, r, t, u, w=vector(nn, i, vector(i))); w[1][1]=1; for(s=2, nn, fordiv(s, d, if(dw[i][d], [d..nn]); forvec(v=vector(s/d, i, [1, #u]), if(nn>=r=1+sum(i=1, #v, u[v[i]]), k=1; t=1; for(i=2, #v, if(v[i]==v[i-1], k++, t*=binomial(w[u[v[i-1]]][d]+k-1, k); k=1)); w[r][s]+=t*binomial(w[u[v[#v]]][d]+k-1, k)), 1)))); vector(nn, i, vecsum(w[i])); \\ Jinyuan Wang, Feb 25 2025

a(51) onward from Robert G. Wilson v, Jan 07 2018

A301343 Regular triangle where T(n,k) is the number of planted achiral (or generalized Bethe) trees with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 1, 1, 1, 0, 1, 3, 2, 2, 1, 1, 0, 1, 3, 2, 2, 1, 1, 1, 0, 1, 4, 2, 4, 1, 2, 1, 1, 0, 1, 4, 3, 4, 1, 3, 1, 1, 1, 0, 1, 5, 3, 6, 2, 4, 1, 2, 1, 1, 0, 1, 5, 3, 6, 2, 4, 1, 2, 1, 1, 1, 0, 1, 6, 4, 9, 2, 7, 1, 4, 2, 2, 1, 1, 0

Offset: 1

Gus Wiseman, Mar 19 2018

			Triangle begins:
1
1  0
1  1  0
1  1  1  0
1  2  1  1  0
1  2  1  1  1  0
1  3  2  2  1  1  0
1  3  2  2  1  1  1  0
1  4  2  4  1  2  1  1  0
1  4  3  4  1  3  1  1  1  0
1  5  3  6  2  4  1  2  1  1  0
The T(9,4) = 4 planted achiral trees: (((((oooo))))), ((((oo)(oo)))), (((oo))((oo))), ((o)(o)(o)(o)).

Row sums are A003238. A version without the zeroes or first row is A214575.

Cf. A000081, A003238, A004111, A032305, A055277, A214577, A273873, A289078, A289079, A290689, A291443, A298422, A298426, A301342, A301344, A301345.

tri[n_,k_]:=If[k===1,1,If[k>=n,0,Sum[tri[n-k,d],{d,Divisors[k]}]]];
Table[tri[n,k],{n,10},{k,n}]

T(n,1) = 1, T(n,k) = 0 if n <= k, otherwise T(n,k) = Sum_{d|k} T(n - k, d).

A298533 Number of unlabeled rooted trees with n vertices such that every branch of the root has the same number of leaves.

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 31, 64, 144, 333, 808, 2004, 5109, 13199, 34601, 91539, 244307, 656346, 1774212, 4820356, 13157591, 36060811, 99198470, 273790194, 757971757, 2104222594, 5856496542, 16338140048, 45678276507, 127964625782, 359155302204, 1009790944307

Offset: 1

Gus Wiseman, Jan 20 2018

nonn

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

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

Cf. A000081, A003238, A004111, A032305, A289079, A290689, A291443, A297791, A298422, A298534, A298535.

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

\\ here R is A055277 as vector of polynomials
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
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)))); concat([1],sum(i=2, #M, EulerT(M[i,])))} \\ Andrew Howroyd, May 20 2018

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

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

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 1, 10, 2, 2, 2, 2, 2, 42, 1, 2, 10, 2, 2, 138, 2, 2, 2, 34, 2, 1514, 2, 2, 42, 2, 1, 2058, 2, 162, 10, 2, 2, 8202, 2, 2, 138, 2, 2, 207370, 2, 2, 2, 130, 34, 131082, 2, 2, 1514, 2082, 2, 524298, 2, 2, 42, 2, 2, 14725738, 1, 8226, 2058, 2

Offset: 1

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(9) = 10 odd same-trees:
9,
(333),
(33(111)), (3(111)3), ((111)33)
(3(111)(111)), ((111)3(111)), ((111)(111)3),
((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, A300648, A300649, A300650.

a[n_]:=1+Sum[a[n/d]^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), a(n/d)^d))); \\ Michel Marcus, Mar 10 2018

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

cp's OEIS Frontend

A167865 Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A300273 Sorted list of Heinz numbers of collapsible integer partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A298422 Number of rooted trees with n nodes in which all positive outdegrees are the same.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A289078 Number of orderless same-trees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A298426 Regular triangle where T(n,k) is number of k-ary rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A291441 Matula-Goebel numbers of orderless same-trees with all leaves equal to 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A297791 Number of series-reduced leaf-balanced rooted trees with n nodes. Number of orderless same-trees with n nodes and all leaves equal to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions