A055277 -id:A055277 - cp's OEIS frontend

A358553 Number of internal (non-leaf) nodes in the n-th standard ordered rooted tree.

0, 1, 2, 1, 3, 2, 2, 1, 2, 3, 3, 2, 3, 2, 2, 1, 4, 2, 4, 3, 4, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 1, 3, 4, 3, 2, 5, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 2, 4, 2, 4, 3, 4, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 1, 3, 3, 5, 4, 4, 3, 3, 2, 4, 5, 5, 4, 5, 4, 4, 3, 5, 3, 5, 4, 5, 4, 4

Offset: 1

Gus Wiseman, Nov 26 2022

nonn

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 89-th standard rooted tree is ((o)o(oo)), and it has 3 internal nodes, so a(89) = 3.

This statistic is counted by A001263, unordered A358575 (reverse A055277).
The unordered version is A342507, firsts A358554.
Other statistics: A358371 (leaves), A358372 (nodes), A358379 (edge-height).
A000081 counts rooted trees, ordered A000108.
Cf. A000891, A014221, A358373, A358585, A358586, A358588.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Table[Count[srt[n],[_],{0,Infinity}],{n,100}]

A358728 Number of n-node rooted trees whose node-height is less than their number of leaves.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 10, 30, 76, 219, 582, 1662, 4614, 13080, 36903, 105098, 298689, 852734, 2434660, 6964349, 19931147, 57100177, 163647811, 469290004, 1346225668, 3863239150, 11089085961, 31838349956, 91430943515, 262615909503, 754439588007, 2167711283560

Offset: 1

Gus Wiseman, Nov 29 2022

nonn

Node-height is the number of nodes in the longest path from root to leaf.

			The a(1) = 0 through a(7) = 10 trees:
  .  .  .  (ooo)  (oooo)  (ooooo)   (oooooo)
                          ((oooo))  ((ooooo))
                          (o(ooo))  (o(oooo))
                          (oo(oo))  (oo(ooo))
                          (ooo(o))  (ooo(oo))
                                    (oooo(o))
                                    ((o)(ooo))
                                    ((oo)(oo))
                                    (o(o)(oo))
                                    (oo(o)(o))

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

These trees are ranked by A358727.
For internals instead of node-height we have A358581, ordered A358585.
The case of equality is A358589 (square trees), ranked by A358577.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height, ordered A080936.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
Cf. A109082, A109129, A185650, A358552, A358582-A358586, A358587, A358591.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Depth[#]-1

\\ Needs R(n,f) defined in A358589.
seq(n) = {Vec(R(n, (h,p)->sum(j=h+1, n-1, polcoef(p,j,y))), -n)} \\ Andrew Howroyd, Jan 01 2023

Terms a(19) and beyond from Andrew Howroyd, Jan 01 2023

A358731 Matula-Goebel numbers of rooted trees whose number of nodes is one more than their node-height.

Original entry on oeis.org

4, 6, 7, 10, 13, 17, 22, 29, 41, 59, 62, 79, 109, 179, 254, 277, 293, 401, 599, 1063, 1418, 1609, 1787, 1913, 2749, 4397, 8527, 10762, 11827, 13613, 15299, 16519, 24859, 42043, 87803

Offset: 1

Gus Wiseman, Dec 01 2022

These are paths with a single extra leaf growing from them.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.
Node-height is the number of nodes in the longest path from root to leaf.

			The terms together with their corresponding rooted trees begin:
    4: (oo)
    6: (o(o))
    7: ((oo))
   10: (o((o)))
   13: ((o(o)))
   17: (((oo)))
   22: (o(((o))))
   29: ((o((o))))
   41: (((o(o))))
   59: ((((oo))))
   62: (o((((o)))))
   79: ((o(((o)))))
  109: (((o((o)))))
  179: ((((o(o)))))
  254: (o(((((o))))))
  277: (((((oo)))))
  293: ((o((((o))))))
  401: (((o(((o))))))
  599: ((((o((o))))))

These trees are counted by A289207.
Positions of 1's in A358729.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height.
A055277 counts rooted trees by nodes and leaves.
MG differences: A358580, A358724, A358726, A358729.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A206487, A209638, A316321, A358576, A358577, A358592, A358725.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],Count[MGTree[#],_,{0,Infinity}]==Depth[MGTree[#]]&]

A055279 Number of rooted trees with n nodes and 4 leaves.

Original entry on oeis.org

1, 4, 14, 39, 97, 212, 429, 804, 1427, 2406, 3900, 6094, 9245, 13645, 19682, 27791, 38530, 52516, 70521, 93390, 122157, 157945, 202104, 256090, 321628, 400567, 495070, 607445, 740362, 896657, 1079581, 1292574, 1539546, 1824621, 2152452, 2527932, 2956546

Offset: 5

Christian G. Bower, May 09 2000

nonn

			G.f. = x^5 + 4*x^6 + 14*x^7 + 39*x^8 + 97*x^9 + 212*x^10 + 429*x^11 + ...

Georg Fischer, Table of n, a(n) for n = 5..200
Index entries for sequences related to rooted trees

Column 4 of A055277.

Cf. A055365.

{a(n) = if( n<5, n = -1-n; polcoeff( (1 + 2*x + 5*x^2 + 5*x^3 + 7*x^4 + 5*x^5 + 3*x^6 + x^7 + x^8) / ((1 - x)^3 * (1 - x^2)^2 * (1 - x^3) * (1 - x^4)) + x * O(x^n), n), n = n-5; polcoeff( (1 + x + 3*x^2 + 5*x^3 + 7*x^4 + 5*x^5 + 5*x^6 + 2*x^7 + x^8) / ((1 - x)^3 * (1 - x^2)^2 * (1 - x^3) * (1 - x^4)) + x * O(x^n), n))}; /* Michael Somos, Nov 02 2014 */

G.f.: x^5 * (1 + x + 3*x^2 + 5*x^3 + 7*x^4 + 5*x^5 + 5*x^6 + 2*x^7 + x^8) / ((1 - x)^3 * (1 - x^2)^2 * (1 - x^3) * (1 - x^4)). - Michael Somos, Nov 02 2014
a(5-n) = A055365(n). for all n in Z. - Michael Somos, Nov 02 2014
0 = -30 + a(n) - 2*a(n+1) - a(n+2) + 3*a(n+3) + a(n+5) - 2*a(n+6) - 2*a(n+7) + a(n+8) + 3*a(n+10) - a(n+11) - 2*a(n+12) + a(n+13) for all n in Z. - Michael Somos, Nov 02 2014
a(n) ~ n^6 / 1152 as n -> infinity. - Michael Somos, Nov 02 2014

A055287 Number of rooted trees with n nodes and 12 leaves.

Original entry on oeis.org

1, 12, 114, 864, 5541, 30846, 152596, 681428, 2783239, 10504028, 36943275, 121939535, 380006322, 1123838933, 3168283157, 8547632165, 22144509397, 55260123176, 133188829780, 310810391963, 703802522743, 1549519595711

Offset: 13

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 13..278
Index entries for sequences related to rooted trees

Column 12 of A055277.

A262395 Difference between the numbers of trees on n vertices with an even number and an odd number of leaves.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 3, 2, 5, 5, 13, 13, 29, 32, 71, 81, 177, 209, 449, 538, 1148, 1415, 3002, 3736, 7862, 9930, 20877, 26648, 55756, 71767, 149860, 194507, 405332, 529708, 1101502, 1447956, 3006750, 3974959, 8242691, 10948355, 22673357, 30249668, 62583402, 83831176, 173259448, 232917913, 480970826, 648753720

Offset: 2

Max Alekseyev, Sep 21 2015

nonn

The sequence could be prepended with a(0)=1 and a(1)=-1. However, it is conjectured that for all n>=2, we have a(n)>=0 (cf. MathOverflow link).

MathOverflow, Counting trees according to endpoints, 2015.

Cf. A055290, A055277.

a(n) = A262430(n) - A262431(n).

G.f.: x + A(x,-1), where A(x,y) is g.f. for A055290.

A262430 Number of trees on n vertices with an even number of leaves.

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 3, 6, 12, 25, 54, 120, 278, 657, 1586, 3885, 9676, 24350, 61974, 159066, 411637, 1072477, 2812147, 7414611, 19650656, 52319946, 139898593, 375536661, 1011726481, 2734793731, 7415449225, 20165442393, 54986240994, 150314506170, 411889913114, 1131183374539, 3113153283443, 8584839296108, 23718157486109, 65645273392938, 181995130879151, 505374042479921, 1405493247220915, 3914493122094481, 10917513971606377, 30489195524251154, 85254349619909519, 238677545463592954, 668973050139380099, 1877097093098685409, 5272616851780131627

Offset: 0

Max Alekseyev, Sep 22 2015

nonn

For n>=0, a(n) + A262431(n) = A000055(n).

For n>=2, a(n) - A262431(n) = A262395(n).

Cf. A000055, A055290, A055277, A262431.

G.f.: (A(x,1)+A(x,-1))/2, where A(x,y) is g.f. for A055290.

A262431 Number of trees on n vertices with an odd number of leaves.

Original entry on oeis.org

0, 1, 0, 0, 1, 1, 3, 5, 11, 22, 52, 115, 273, 644, 1573, 3856, 9644, 24279, 61893, 158889, 411428, 1072028, 2811609, 7413463, 19649241, 52316944, 139894857, 375528799, 1011716551, 2734772854, 7415422577, 20165386637, 54986169227, 150314356310, 411889718607, 1131182969207, 3113152753735, 8584838194606, 23718156038153, 65645270386188, 181995126904192, 505374034237230, 1405493236272560, 3914493099421124, 10917513941356709, 30489195461667752, 85254349536078343, 238677545290333506, 668973049906462186, 1877097092617714583, 5272616851131377907

Offset: 0

Max Alekseyev, Sep 22 2015

nonn

For n>=0, A262430(n) + a(n) = A000055(n).

For n>=2, A262430(n) - a(n) = A262395(n).

Cf. A000055, A055290, A055277, A262430.

G.f.: (A(x,1)-A(x,-1))/2, where A(x,y) is g.f. for A055290.

A301365 Regular triangle where T(n,k) is the number of strict trees of weight n with k leaves.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 4, 4, 1, 0, 1, 3, 7, 9, 7, 1, 0, 1, 3, 10, 19, 20, 11, 1, 0, 1, 4, 15, 35, 51, 43, 16, 1, 0, 1, 4, 18, 55, 104, 123, 84, 22, 1, 0, 1, 5, 25, 84, 196, 298, 284, 153, 29, 1, 0, 1, 5, 30, 120, 331, 624, 783, 614, 260, 37

Offset: 1

Gus Wiseman, Mar 19 2018

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

			Triangle begins:
  1
  1   0
  1   1   0
  1   1   1   0
  1   2   2   1   0
  1   2   4   4   1   0
  1   3   7   9   7   1   0
  1   3  10  19  20  11   1   0
  1   4  15  35  51  43  16   1   0
The T(7,3) = 7 strict trees: ((51)1), ((42)1), ((41)2), ((32)2), (4(21)), ((31)3), (421).

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

Row sums are A273873.

Cf. A004111, A008284, A032305, A055277, A063834, A281145, A289501, A294018, A294079, A300352, A300442, A300443, A301342, A301364-A301368.

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

A(n)={my(v=vector(n)); for(n=1, n, v[n] = y + polcoef(prod(k=1, n-1, 1 + v[k]*x^k + O(x*x^n)), n)); vector(n, k, Vecrev(v[k]/y, k))}
my(T=A(10));for(n=1, #T, print(T[n])) \\ Andrew Howroyd, Aug 26 2018

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

cp's OEIS Frontend

A358553 Number of internal (non-leaf) nodes in the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358728 Number of n-node rooted trees whose node-height is less than their number of leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A358731 Matula-Goebel numbers of rooted trees whose number of nodes is one more than their node-height.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A055279 Number of rooted trees with n nodes and 4 leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A055287 Number of rooted trees with n nodes and 12 leaves.

Views

Author

Keywords

Links

Crossrefs

A262395 Difference between the numbers of trees on n vertices with an even number and an odd number of leaves.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A262430 Number of trees on n vertices with an even number of leaves.

Views

Author

Keywords

Comments

Crossrefs

Formula

A262431 Number of trees on n vertices with an odd number of leaves.

Views

Author

Keywords

Comments

Crossrefs

Formula

A301365 Regular triangle where T(n,k) is the number of strict trees of weight n with k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI