A048816 -id:A048816 - cp's OEIS frontend

A048813 Number of rooted trees with n nodes with every leaf at height 8.

1, 1, 2, 3, 6, 9, 17, 28, 49, 82, 143, 241, 417, 707, 1213, 2065, 3534, 6014, 10272, 17487, 29820, 50758, 86469, 147123, 250429, 425932, 724517, 1231765, 2094116, 3558799, 6047447, 10273349, 17450221, 29633832, 50317376, 85420630

Offset: 9

Christian G. Bower, Apr 15 1999

nonn

Alois P. Heinz, Table of n, a(n) for n = 9..1000
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A048808-A048816.

Column k=8 of A244925.

Euler transform of A048812 shifted right.

A048814 Number of rooted trees with n nodes with every leaf at height 9.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 17, 28, 49, 83, 144, 244, 422, 719, 1234, 2109, 3615, 6173, 10565, 18042, 30839, 52653, 89927, 153462, 261931, 446818, 762190, 1299678, 2215990, 3777230, 6437673, 10969447, 18688879, 31834676, 54220089, 92331502

Offset: 10

Christian G. Bower, Apr 15 1999

nonn

Alois P. Heinz, Table of n, a(n) for n = 10..1000
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A048808-A048816.

Column k=9 of A244925.

Euler transform of A048813 shifted right.

A306269 Regular triangle read by rows where T(n,k) is the number of unlabeled balanced rooted semi-identity trees with n >= 1 nodes and depth 0 <= k < n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 2, 1, 1, 1, 0, 1, 2, 2, 1, 1, 1, 0, 1, 3, 3, 2, 1, 1, 1, 0, 1, 3, 4, 3, 2, 1, 1, 1, 0, 1, 5, 6, 5, 3, 2, 1, 1, 1, 0, 1, 5, 9, 7, 5, 3, 2, 1, 1, 1, 0, 1, 7, 12, 12, 8, 5, 3, 2, 1, 1, 1, 0, 1, 8, 17, 17, 13, 8, 5, 3, 2, 1, 1, 1

Offset: 1

Gus Wiseman, Feb 01 2019

A rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees. It is balanced if all leaves are the same distance from the root.

			Triangle begins:
  1
  0  1
  0  1  1
  0  1  1  1
  0  1  1  1  1
  0  1  2  1  1  1
  0  1  2  2  1  1  1
  0  1  3  3  2  1  1  1
  0  1  3  4  3  2  1  1  1
  0  1  5  6  5  3  2  1  1  1
  0  1  5  9  7  5  3  2  1  1  1
  0  1  7 12 12  8  5  3  2  1  1  1
  0  1  8 17 17 13  8  5  3  2  1  1  1
  0  1 10 25 26 20 14  8  5  3  2  1  1  1
  0  1 12 34 39 31 21 14  8  5  3  2  1  1  1
The postpositive terms of row 9 {3, 4, 3, 2} count the following trees:
  ((ooooooo))   (((oooooo)))    ((((ooooo))))    (((((oooo)))))
  ((o)(ooooo))  (((o)(oooo)))   ((((o)(ooo))))   (((((o)(oo)))))
  ((oo)(oooo))  (((oo)(ooo)))   ((((o))((oo))))
                (((o))((ooo)))

Alois P. Heinz, Rows n = 1..200, flattened
Gus Wiseman, Unlabeled balanced rooted semi-identity trees with 12 nodes, organized by depth.

Row sums give A306201.
T(2n-1,n) gives A306274.
Cf. A000081, A004111, A048816, A079500, A120803, A184155, A276625, A306200, A306202, A306203, A320222, A320270.

ubk[n_,k_]:=Select[Join@@Table[Select[Union[Sort/@Tuples[ubk[#,k-1]&/@ptn]],UnsameQ@@DeleteCases[#,{}]&],{ptn,IntegerPartitions[n-1]}],SameQ[k,##]&@@Length/@Position[#,{}]&];
Table[Length[ubk[n,k]],{n,1,10},{k,0,n-1}]

A358524 Binary encoding of balanced ordered rooted trees (counted by A007059).

Original entry on oeis.org

0, 2, 10, 12, 42, 52, 56, 170, 204, 212, 232, 240, 682, 820, 844, 852, 920, 936, 976, 992, 2730, 3276, 3284, 3380, 3404, 3412, 3640, 3688, 3736, 3752, 3888, 3920, 4000, 4032, 10922, 13108, 13132, 13140, 13516, 13524, 13620, 13644, 13652, 14568, 14744, 14760

Offset: 1

Gus Wiseman, Nov 21 2022

nonn

An ordered tree is balanced if all leaves are the same distance from the root.

The binary encoding of an ordered tree (see A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

			The terms together with their corresponding trees begin:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  204: ((o)(o))
  212: ((ooo))
  232: (((oo)))
  240: ((((o))))
  682: (ooooo)
  820: ((o)(oo))
  844: ((oo)(o))
  852: ((oooo))
  920: (((o)(o)))
  936: (((ooo)))
  976: ((((oo))))
  992: (((((o)))))

These trees are counted by A007059.
This is a subset of A014486.
The version for binary trees is A057122.
The unordered version is A184155, counted by A048816.
Another ranking of balanced ordered trees is A358459.
A000108 counts ordered rooted trees, unordered A000081.
A358453 counts transitive ordered trees, unordered A290689.
Cf. A001263, A003238, A244925, A358377, A358379, A358523.

binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]]
Select[Range[0,1000],binbalQ[#]&&SameQ@@Length/@Position[bint[#],{}]&]

A238372 Number of labeled rooted trees with n nodes with every leaf at the same height.

Original entry on oeis.org

1, 2, 9, 40, 265, 1956, 18529, 183520, 2226753, 28663300, 421589641, 6696832704, 117283627201, 2190260755060, 44645172510345, 964646320357696, 22317294448547329, 547594529028427908, 14246751684203363593, 390309056795283743200, 11276891642831796476481

Offset: 1

F. Chapoton, Feb 25 2014

nonn

			On 4 vertices, there are:
24 rooted trees X-O-O-O
12 rooted trees X-O-O
                   \
                    O
4 rooted trees    X
                 /|\
                O O O

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

Cf. A048816 for the unlabeled version.

p:= proc(i) p(i):= `if`(i=1, x, x*(exp(p(i-1))-1)) end:
s:= proc(n) s(n):= `if`(n=0, 0, s(n-1)+p(n)) end:
a:= n-> n! * coeff(series(s(n), x, n+1), x, n):
seq(a(n), n=1..25);  # Alois P. Heinz, Feb 26 2014

T[n_, n_] = 1; T[n_, m_] := T[n, m] = n!/(n-m)!*Sum[StirlingS2[k, m]*T[n-m, k], {k, 1, n-m}]; a[n_] := T[n, 1]; Array[a, 25] (* Jean-François Alcover, Jan 08 2016, after Vladimir Kruchinin *)

T(n,m):=if n=m then 1 else n!/(n-m)!*sum(stirling2(k,m)*T(n-m,k),k,1,n-m);
makelist(T(n,1),n,1,15); /* Vladimir Kruchinin, Apr 01 2015 */

x = QQ[['x']].gen()
P = {}
N = 20
P[1] = x.O(N)
for i in range(2, N):
    P[i] = x*(P[i-1].exp(N)-1)
add(P[u] for u in P)

E.g.f.: Sum_{i>=1} P_i with P_1 = x and P_i = x * (exp(P_{i-1})-1) for i>1.

a(n) = T(n,1), T(n,m) = n!/(n-m)!*Sum_{k=1..n-m}(stirling2(k,m)*T(n-m,k)), T(n,n)=1. - Vladimir Kruchinin, Apr 01 2015

A320221 Irregular triangle where T(n,k) is the number of unlabeled series-reduced rooted trees with n leaves in which every leaf is at height k, (n>=1, min(1,n-1) <= k <= log_2(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 6, 1, 1, 7, 1, 1, 11, 4, 1, 13, 6, 1, 20, 16, 1, 23, 23, 1, 33, 46, 1, 40, 70, 1, 54, 127, 1, 1, 65, 189, 1, 1, 87, 320, 5, 1, 104, 476, 10, 1, 136, 771, 32, 1, 164, 1145, 63, 1, 209, 1795, 154, 1, 252, 2657, 304, 1, 319, 4091, 656

Offset: 1

Gus Wiseman, Oct 07 2018

			Triangle begins:
  1
  1
  1
  1  1
  1  1
  1  3
  1  3
  1  6  1
  1  7  1
  1 11  4
  1 13  6
  1 20 16
  1 23 23
  1 33 46
  1 40 70
The T(11,3) = 6 rooted trees:
   (((oo)(oo))((oo)(ooooo)))
   (((oo)(oo))((ooo)(oooo)))
   (((oo)(ooo))((oo)(oooo)))
   (((oo)(ooo))((ooo)(ooo)))
  (((oo)(oo))((oo)(oo)(ooo)))
  (((oo)(ooo))((oo)(oo)(oo)))

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

Row sums are A120803. Second column is A083751. A regular version is A320179.
Cf. A000669, A005804, A048816, A119262, A120803, A141268, A244925, A319312.
Cf. A316624, A320154, A320155, A320160, A320172, A320173.

qurt[n_]:=If[n==1,{{}},Join@@Table[Union[Sort/@Tuples[qurt/@ptn]],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}]];
DeleteCases[Table[Length[Select[qurt[n],SameQ[##,k]&@@Length/@Position[#,{}]&]],{n,10},{k,0,n-1}],0,{2}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
T(n)={my(u=vector(n), v=vector(n), h=1); u[1]=1; while(u, v+=u*h; h*=x; u=EulerT(u)-u); v[1]=x; [Vecrev(p/x) | p<-v]}
{ my(A=T(15)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 09 2020

Terms a(36) and beyond from Andrew Howroyd, Dec 09 2020

Name clarified by Andrew Howroyd, Dec 09 2020

A320266 Number of balanced orderless tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 6, 1, 4, 1, 4, 2, 2, 1, 8, 2, 2, 3, 4, 1, 5, 1, 9, 2, 2, 2, 11, 1, 2, 2, 8, 1, 5, 1, 4, 4, 2, 1, 17, 2, 4, 2, 4, 1, 8, 2, 8, 2, 2, 1, 13, 1, 2, 4, 19, 2, 5, 1, 4, 2, 5, 1, 24, 1, 2, 4, 4, 2, 5, 1, 17, 6, 2, 1, 13, 2

Offset: 1

Gus Wiseman, Oct 08 2018

nonn

A rooted tree is balanced if all leaves are the same distance from the root.
An orderless tree-factorization of n is either (case 1) the number n itself or (case 2) a finite multiset of two or more orderless tree-factorizations, one of each factor in a factorization of n.
a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

			The a(36) = 11 balanced orderless tree-factorizations:
  36,
  (2*18), (3*12), (4*9), (6*6),
  (2*2*9), (2*3*6), (3*3*4),
  (2*2*3*3), ((2*2)*(3*3)), ((2*3)*(2*3)).

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

Cf. A000669, A001055, A048816, A050336, A281118, A292505, A119262, A120803, A141268, A292504, A319312, A320160, A320267.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[facs[n],{n}],n]];
Table[Length[Select[oltfacs[n],SameQ@@Length/@Position[#,_Integer]&]],{n,100}]

MultEulerT(u)={my(v=vector(#u)); v[1]=1; for(k=2, #u, forstep(j=#v\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j]+=binomial(e+u[k]-1, e)*v[i]))); v}
seq(n)={my(u=vector(n, i, 1), v=vector(n)); while(u, v+=u; u[1]=1; u=MultEulerT(u)-u); v} \\ Andrew Howroyd, Nov 18 2018

a(p^n) = A320160(n) for prime p. - Andrew Howroyd, Nov 18 2018

A320267 Number of balanced complete orderless tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 1, 1, 1

Offset: 1

Gus Wiseman, Oct 08 2018

nonn

a(1) = 1 by convention.
A rooted tree is balanced if all leaves are the same distance from the root.
An orderless tree-factorization (see A292504 for definition) is complete if all leaves are prime numbers.
a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

			The a(96) = 5 balanced complete orderless tree-factorizations:
     (2*2*2*2*2*3)
   ((2*2)*(2*2*2*3))
   ((2*3)*(2*2*2*2))
   ((2*2*2)*(2*2*3))
  ((2*2)*(2*2)*(2*3))

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

Cf. A001055, A048816, A050336, A281118, A292505, A119262, A120803, A292504, A320160, A320266.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[facs[n],{n}],n]];
Table[Length[Select[oltfacs[n],And[SameQ@@Length/@Position[#,_Integer],FreeQ[#,_Integer?(!PrimeQ[#]&)]]&]],{n,100}]

MultEulerT(u)={my(v=vector(#u)); v[1]=1; for(k=2, #u, forstep(j=#v\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j]+=binomial(e+u[k]-1, e)*v[i]))); v}
seq(n)={my(u=vector(n, i, i==1 || isprime(i)), v=vector(n)); while(u, v+=u; u[1]=1; u=MultEulerT(u)-u); v} \\ Andrew Howroyd, Nov 18 2018

a(p^n) = A120803(n) for prime p. - Andrew Howroyd, Nov 18 2018

A358459 Numbers k such that the k-th standard ordered rooted tree is balanced (counted by A007059).

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 9, 11, 16, 17, 32, 35, 37, 41, 43, 64, 128, 129, 137, 139, 163, 169, 171, 256, 257, 293, 512, 515, 529, 547, 553, 555, 641, 649, 651, 675, 681, 683, 1024, 1025, 2048, 2053, 2057, 2059, 2177, 2185, 2187, 2211, 2217, 2219, 2305, 2341, 2563

Offset: 1

Gus Wiseman, Nov 19 2022

nonn

An ordered tree is balanced if all leaves have the same distance from the root.

We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

			The terms together with their corresponding ordered trees begin:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   8: (ooo)
   9: ((oo))
  11: ((o)(o))
  16: (oooo)
  17: ((((o))))
  32: (ooooo)
  35: ((oo)(o))
  37: (((o))((o)))
  41: ((o)(oo))
  43: ((o)(o)(o))

Gus Wiseman, Statistics, classes, and transformations of standard compositions

These trees are counted by A007059.
The unordered version is A184155, counted by A048816.
A000108 counts ordered rooted trees, unordered A000081.
A358379 gives depth of standard ordered trees.
Cf. A003238, A004249, A032027, A244925, A290822, A318185, A358373-A358378.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[100],SameQ@@Length/@Position[srt[#],{}]&]

cp's OEIS Frontend

A048813 Number of rooted trees with n nodes with every leaf at height 8.

Views

Author

Keywords

Links

Crossrefs

Formula

A048814 Number of rooted trees with n nodes with every leaf at height 9.

Views

Author

Keywords

Links

Crossrefs

Formula

A306269 Regular triangle read by rows where T(n,k) is the number of unlabeled balanced rooted semi-identity trees with n >= 1 nodes and depth 0 <= k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358524 Binary encoding of balanced ordered rooted trees (counted by A007059).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A238372 Number of labeled rooted trees with n nodes with every leaf at the same height.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Sage

Formula

A320221 Irregular triangle where T(n,k) is the number of unlabeled series-reduced rooted trees with n leaves in which every leaf is at height k, (n>=1, min(1,n-1) <= k <= log_2(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A320266 Number of balanced orderless tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A320267 Number of balanced complete orderless tree-factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica