A358583 -id:A358583 - cp's OEIS frontend

A358580 Difference between the number of leaves and the number of internal (non-leaf) nodes in the rooted tree with Matula-Goebel number n.

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

Offset: 1

Gus Wiseman, Nov 25 2022

sign

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.

			The Matula-Goebel number of ((ooo(o))) is 89, and it has 4 leaves and 3 internal nodes, so a(89) = 1.

Zeros are A358578, counted by A185650 (ordered A358579).
Positions of positive terms are counted by A358581, negative A358582.
Positions of nonnegative terms are counted by A358583, nonpositive A358584.
A000081 counts rooted trees, ordered A000108.
A034781 counts trees by nodes and height.
A055277 counts trees by nodes and leaves, ordered A001263.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
Cf. A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A206487, A358371, A358576, A358577, A358592.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Count[MGTree[n],{},{0,Infinity}]-Count[MGTree[n],[_],{0,Infinity}],{n,100}]

a(n) = A109129(n) - A342507(n).

A358586 Number of ordered rooted trees with n nodes, at least half of which are leaves.

Original entry on oeis.org

1, 1, 1, 4, 7, 31, 66, 302, 715, 3313, 8398, 39095, 104006, 484706, 1337220, 6227730, 17678835, 82204045, 238819350, 1108202513, 3282060210, 15195242478, 45741281820, 211271435479, 644952073662, 2971835602526, 9183676536076, 42217430993002, 131873975875180, 604834233372884

Offset: 1

Gus Wiseman, Nov 24 2022

nonn

			The a(1) = 1 through a(5) = 7 ordered trees:
  o  (o)  (oo)  (ooo)   (oooo)
                ((o)o)  ((o)oo)
                ((oo))  ((oo)o)
                (o(o))  ((ooo))
                        (o(o)o)
                        (o(oo))
                        (oo(o))

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

For equality we have A000891, unordered A185650.
Odd-indexed terms appear to be A065097.
The unordered version is A358583.
The opposite is the same, unordered A358584.
The strict case is A358585, unordered A358581.
A000108 counts ordered rooted trees, unordered A000081.
A001263 counts ordered rooted trees by nodes and leaves, unordered A055277.
A080936 counts ordered rooted trees by nodes and height, unordered A034781.
A090181 counts ordered rooted trees by nodes and internals, unord. A358575.
A358590 counts square ordered trees, unordered A358589 (ranked by A358577).
Cf. A109129, A342507, A358371, A358579, A358580, A358582, A358584, A358588.

aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],Count[#,{},{0,Infinity}]>=Count[#,[_],{0,Infinity}]&]],{n,1,10}]

a(n) = if(n==1, 1, n--; (binomial(2*n,n)/(n+1) + if(n%2, binomial(n, (n-1)/2)^2 / n))/2) \\ Andrew Howroyd, Jan 13 2024

From Andrew Howroyd, Jan 13 2024: (Start)
a(n) = Sum_{k=1..floor(n/2)} A001263(n-1, k) for n >= 2.
a(2*n) = (A000108(2*n-1) + A000891(n-1))/2 for n >= 1;
a(2*n+1) = A000108(2*n)/2 for n >= 1. (End)

a(16) onwards from Andrew Howroyd, Jan 13 2024

A358581 Number of rooted trees with n nodes, most of which are leaves.

Original entry on oeis.org

1, 0, 1, 1, 4, 5, 20, 28, 110, 169, 663, 1078, 4217, 7169, 27979, 49191, 191440, 345771, 1341974, 2477719, 9589567, 18034670, 69612556, 132984290, 511987473, 991391707, 3807503552, 7460270591, 28585315026, 56595367747, 216381073935, 432396092153

Offset: 1

Gus Wiseman, Nov 23 2022

nonn

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

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

For equality we have A185650 aerated, ranked by A358578.
The opposite version is A358582, non-strict A358584.
The non-strict version is A358583.
The ordered version is A358585, odd-indexed terms A065097.
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.
A358575 counts rooted trees by nodes and internal nodes, ordered A090181.
A358589 counts square trees, ranked by A358577, ordered A358590.
Cf. A000891, A109129, A342507, A358579, A358580, A358586, A358591.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Count[#,{},{0,Infinity}]>Count[#,[_],{0,Infinity}]&]],{n,0,10}]

\\ See A358584 for R(n).
seq(n) = {my(A=R(n)); vector(n, n, my(u=Vecrev(A[n]/y)); vecsum(u[n\2+1..#u]))} \\ Andrew Howroyd, Dec 31 2022

A358581(n) + A358584(n) = A000081(n).
A358582(n) + A358583(n) = A000081(n).
a(n) = Sum_{k=floor(n/2)+1..n} A055277(n, k). - Andrew Howroyd, Dec 31 2022

Terms a(19) and beyond from Andrew Howroyd, Dec 31 2022

A358575 Triangle read by rows where T(n,k) is the number of unlabeled n-node rooted trees with k = 0..n-1 internal (non-leaf) nodes.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 8, 6, 1, 0, 1, 5, 14, 18, 9, 1, 0, 1, 6, 21, 39, 35, 12, 1, 0, 1, 7, 30, 72, 97, 62, 16, 1, 0, 1, 8, 40, 120, 214, 212, 103, 20, 1, 0, 1, 9, 52, 185, 416, 563, 429, 161, 25, 1

Offset: 1

Gus Wiseman, Nov 23 2022

			Triangle begins:
    1
    0    1
    0    1    1
    0    1    2    1
    0    1    3    4    1
    0    1    4    8    6    1
    0    1    5   14   18    9    1
    0    1    6   21   39   35   12    1
    0    1    7   30   72   97   62   16    1
    0    1    8   40  120  214  212  103   20    1
    0    1    9   52  185  416  563  429  161   25    1

Row sums are A000081.
Column k = n - 2 appears to be A002620.
Column k = 3 appears to be A006578.
The version for height instead of internal nodes is A034781.
Equals A055277 with rows reversed.
The ordered version is A090181 or A001263.
The central column is A185650, ordered A000891.
The left half sums to A358583, strict A358581.
The right half sums to A358584, strict A358582.
Cf. A000108, A065097, A109129, A342507, A358578, A358587, A358589.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Count[#,[_],{0,Infinity}]==k&]],{n,1,10},{k,0,n-1}]

A358584 Number of rooted trees with n nodes, at most half of which are leaves.

Original entry on oeis.org

0, 1, 1, 3, 5, 15, 28, 87, 176, 550, 1179, 3688, 8269, 25804, 59832, 186190, 443407, 1375388, 3346702, 10348509, 25632265, 79020511, 198670299, 610740694, 1555187172, 4768244803, 12276230777, 37546795678, 97601239282, 297831479850, 780790439063, 2377538260547

Offset: 1

Gus Wiseman, Nov 23 2022

nonn

			The a(2) = 1 through a(6) = 15 trees:
  (o)  ((o))  ((oo))   (((oo)))   (((ooo)))
              (o(o))   ((o)(o))   ((o)(oo))
              (((o)))  ((o(o)))   ((o(oo)))
                       (o((o)))   ((oo(o)))
                       ((((o))))  (o((oo)))
                                  (o(o)(o))
                                  (o(o(o)))
                                  (oo((o)))
                                  ((((oo))))
                                  (((o)(o)))
                                  (((o(o))))
                                  ((o)((o)))
                                  ((o((o))))
                                  (o(((o))))
                                  (((((o)))))

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

For equality we have A185650 aerated, ranked by A358578.
The complement is A358581.
The strict case is A358582.
The opposite version is A358583.
A000081 counts rooted trees, ordered A000108.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
A358575 counts rooted trees by nodes and internal nodes, ordered A090181.
A358589 counts square trees, ranked by A358577, ordered A358590.
Cf. A000891, A034781, A065097, A109129, A342507, A358579, A358580, A358585, A358586, A358591.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Count[#,{},{0,Infinity}]<=Count[#,[_],{0,Infinity}]&]],{n,0,10}]

R(n) = {my(A = O(x)); for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + O(x*x^(j\i)), x, x^i), y, y^i) ) ))); Vec(A)};
seq(n) = {my(A=R(n)); vector(n, n, vecsum(Vecrev(A[n]/y)[1..n\2]))} \\ Andrew Howroyd, Dec 30 2022

A358581(n) + A358584(n) = A000081(n).
A358582(n) + A358583(n) = A000081(n).
a(n) = Sum_{k=1..floor(n/2)} A055277(n, k). - Andrew Howroyd, Dec 30 2022

Terms a(19) and beyond from Andrew Howroyd, Dec 30 2022

A358582 Number of rooted trees with n nodes, most of which are not leaves.

Original entry on oeis.org

0, 0, 1, 1, 5, 7, 28, 48, 176, 336, 1179, 2420, 8269, 17855, 59832, 134289, 443407, 1025685, 3346702, 7933161, 25632265, 62000170, 198670299, 488801159, 1555187172, 3882403641, 12276230777, 31034921462, 97601239282, 249471619165, 780790439063, 2015194486878

Offset: 1

Gus Wiseman, Nov 23 2022

nonn

			The a(3) = 1 through a(6) = 7 trees:
  ((o))  (((o)))  (((oo)))   ((((oo))))
                  ((o)(o))   (((o)(o)))
                  ((o(o)))   (((o(o))))
                  (o((o)))   ((o)((o)))
                  ((((o))))  ((o((o))))
                             (o(((o))))
                             (((((o)))))

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

For equality we have A185650 aerated, ranked by A358578.
The opposite version is A358581, non-strict A358583.
The non-strict version is A358584.
The ordered version is A358585, odd-indexed terms A065097.
A000081 counts rooted trees, ordered A000108.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
A358575 counts rooted trees by nodes and internal nodes, ordered A090181.
A358589 counts square trees, ranked by A358577, ordered A358590.
Cf. A000891, A034781, A109129, A342507, A358579, A358580, A358586, A358591.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Count[#,{},{0,Infinity}][_],{0,Infinity}]&]],{n,0,10}]

\\ See A358584 for R(n).
seq(n) = {my(A=R(n)); vector(n, n, vecsum(Vecrev(A[n]/y)[1..(n-1)\2]))} \\ Andrew Howroyd, Dec 30 2022

A358581(n) + A358584(n) = A000081(n).
A358582(n) + A358583(n) = A000081(n).
a(n) = Sum_{k=1..floor((n-1)/2)} A055277(n, k). - Andrew Howroyd, Dec 30 2022

Terms a(19) and beyond from Andrew Howroyd, Dec 30 2022

A358585 Number of ordered rooted trees with n nodes, most of which are leaves.

Original entry on oeis.org

1, 0, 1, 1, 7, 11, 66, 127, 715, 1549, 8398, 19691, 104006, 258194, 1337220, 3467115, 17678835, 47440745, 238819350, 659060677, 3282060210, 9271024542, 45741281820, 131788178171, 644952073662, 1890110798926, 9183676536076, 27316119923002, 131873975875180, 397407983278484

Offset: 1

Gus Wiseman, Nov 24 2022

nonn

			The a(1) = 1 through a(6) = 11 ordered trees:
  o  .  (oo)  (ooo)  (oooo)   (ooooo)
                     ((o)oo)  ((o)ooo)
                     ((oo)o)  ((oo)oo)
                     ((ooo))  ((ooo)o)
                     (o(o)o)  ((oooo))
                     (o(oo))  (o(o)oo)
                     (oo(o))  (o(oo)o)
                              (o(ooo))
                              (oo(o)o)
                              (oo(oo))
                              (ooo(o))

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

For equality we have A000891, unordered A185650.
Odd-indexed terms are A065097.
The unordered version is A358581.
The opposite is the same, unordered A358582.
The non-strict version is A358586, unordered A358583.
A000108 counts ordered rooted trees, unordered A000081.
A001263 counts ordered rooted trees by nodes and leaves, unordered A055277.
A080936 counts ordered rooted trees by nodes and height, unordered A034781.
A090181 counts ordered rooted trees by nodes and internals, unord. A358575.
A358590 counts square ordered trees, unordered A358589 (ranked by A358577).
Cf. A109129, A342507, A358371, A358579, A358580, A358584, A358588, A358590.

aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],Count[#,{},{0,Infinity}]>Count[#,[_],{0,Infinity}]&]],{n,10}]

a(n) = if(n==1, 1, n--; (binomial(2*n,n)/(n+1) - if(n%2, binomial(n, (n-1)/2)^2 / n))/2) \\ Andrew Howroyd, Jan 13 2024

From Andrew Howroyd, Jan 13 2024: (Start)
a(n) = Sum_{k=1..floor((n-1)/2)} A001263(n-1, k) for n >= 2.
a(2*n) = (A000108(2*n-1) - A000891(n-1))/2 for n >= 1;
a(2*n+1) = A000108(2*n)/2 for n >= 1. (End)

a(16) onwards from Andrew Howroyd, Jan 13 2024

cp's OEIS Frontend

A358580 Difference between the number of leaves and the number of internal (non-leaf) nodes in the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A358586 Number of ordered rooted trees with n nodes, at least half of which are leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A358581 Number of rooted trees with n nodes, most of which are leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A358575 Triangle read by rows where T(n,k) is the number of unlabeled n-node rooted trees with k = 0..n-1 internal (non-leaf) nodes.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A358584 Number of rooted trees with n nodes, at most half of which are leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A358582 Number of rooted trees with n nodes, most of which are not leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A358585 Number of ordered rooted trees with n nodes, most of which are leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions