A109129 -id:A109129 - cp's OEIS frontend

A358727 Matula-Goebel numbers of rooted trees with greater number of leaves (width) than node-height.

8, 16, 24, 28, 32, 36, 38, 42, 48, 49, 53, 54, 56, 57, 63, 64, 72, 76, 80, 81, 84, 96, 98, 104, 106, 108, 112, 114, 120, 126, 128, 131, 133, 136, 140, 144, 147, 148, 152, 156, 159, 160, 162, 168, 171, 172, 178, 180, 182, 184, 189, 190, 192, 196, 200, 204, 208

Offset: 1

Gus Wiseman, Dec 01 2022

nonn

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:
   8: (ooo)
  16: (oooo)
  24: (ooo(o))
  28: (oo(oo))
  32: (ooooo)
  36: (oo(o)(o))
  38: (o(ooo))
  42: (o(o)(oo))
  48: (oooo(o))
  49: ((oo)(oo))
  53: ((oooo))
  54: (o(o)(o)(o))
  56: (ooo(oo))
  57: ((o)(ooo))
  63: ((o)(o)(oo))
  64: (oooooo)
  72: (ooo(o)(o))
  76: (oo(ooo))

Gus Wiseman, The first 64 rooted trees with greater width than height.

Positions of negative terms in A358726.
These trees are counted by A358728.
Differences: A358580, A358724, A358726, A358729.
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.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A185650, A206487, A209638, A358576, A358577, A358578, A358587, A358730.

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

A333267 If n = Product (p_j^k_j) then a(n) = Product (a(pi(p_j)) * k_j), where pi = A000720.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 2, 1, 4, 2, 2, 3, 2, 2, 1, 2, 3, 2, 1, 3, 4, 1, 1, 1, 5, 1, 2, 2, 4, 2, 3, 1, 3, 1, 2, 2, 2, 2, 2, 1, 4, 4, 2, 2, 2, 4, 3, 1, 6, 3, 1, 2, 2, 2, 1, 4, 6, 1, 1, 3, 4, 2, 2, 2, 6, 2, 2, 2, 6, 2, 1, 1, 4, 4, 1, 2, 4, 2, 2, 1, 3, 3, 2, 2, 4, 1, 1, 3, 5, 2, 4, 2, 4

Offset: 1

Ilya Gutkovskiy, Mar 13 2020

			a(36) = a(2^2 * 3^2) = a(prime(1)^2 * prime(2)^2) = a(1) * 2 * a(2) * 2 = 4.

Cf. A000026, A000720, A002110, A003963, A005361, A054725, A109129, A276625 (positions of 1's), A282446, A304117, A318046, A328880.

a:= proc(n) option remember;
      mul(a(numtheory[pi](i[1]))*i[2], i=ifactors(n)[2])
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Mar 13 2020

a[1] = 1; a[n_] := a[n] = Times @@ (a[PrimePi[#[[1]]]] #[[2]] & /@ FactorInteger[n]); Table[a[n], {n, 1, 100}]

a(n) = A005361(n) * Product_{p|n, p prime} a(pi(p)).
a(n) = a(prime(n)).
a(p^k) = k * a(p), where p is prime.
a(A002110(n)) = Product_{k=1..n} a(k).

A358723 Number of n-node rooted trees of edge-height equal to their number of leaves.

Original entry on oeis.org

0, 1, 0, 2, 1, 6, 7, 26, 43, 135, 276, 755, 1769, 4648, 11406, 29762, 75284, 195566, 503165, 1310705, 3402317, 8892807, 23231037, 60906456, 159786040, 420144405, 1105673058, 2914252306, 7688019511, 20304253421, 53667498236, 141976081288, 375858854594, 995728192169

Offset: 1

Gus Wiseman, Nov 29 2022

nonn

Edge-height (A109082) is the number of edges in the longest path from root to leaf.

			The a(1) = 0 through a(7) = 7 trees:
  .  (o)  .  ((oo))  ((o)(o))  (((ooo)))  (((o))(oo))
             (o(o))            ((o(oo)))  (((o)(oo)))
                               ((oo(o)))  ((o)((oo)))
                               (o((oo)))  ((o)(o(o)))
                               (o(o(o)))  ((o(o)(o)))
                               (oo((o)))  (o((o)(o)))
                                          (o(o)((o)))

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

For internals instead of leaves: A011782, ranked by A209638.
For internals instead of edge-height: A185650 aerated, ranked by A358578.
For node-height: A358589 (square trees), ranked by A358577, ordered A358590.
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 internals, ordered A090181.
Cf. A065097, A109082, A109129, A342507, A358552, A358587, A358591, A358728.

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

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

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

A336194 Table read by antidiagonals upwards: T(n,k) = (n - 1)*k^3 - 1, with n > 1 and k > 0.

Original entry on oeis.org

0, 1, 7, 2, 15, 26, 3, 23, 53, 63, 4, 31, 80, 127, 124, 5, 39, 107, 191, 249, 215, 6, 47, 134, 255, 374, 431, 342, 7, 55, 161, 319, 499, 647, 685, 511, 8, 63, 188, 383, 624, 863, 1028, 1023, 728, 9, 71, 215, 447, 749, 1079, 1371, 1535, 1457, 999, 10, 79, 242, 511, 874, 1295, 1714, 2047, 2186, 1999, 1330

Offset: 2

Stefano Spezia, Jul 11 2020

T(n, k) is a sharp upper bound of the tree width of a graph G that does not contain a clique on n vertices nor a minimal separator of size larger than k (see Theorem 2.1 in Pilipczuk et al.).

All the square matrices starting at top left of the table T are singular except for the 2 X 2 submatrix: det([0, 7; 1, 15]) = -7.

			The table starts at row n = 2 and column k = 1 as:
0   7   26   63  124   215 ...
1  15   53  127  249   431 ...
2  23   80  191  374   647 ...
3  31  107  255  499   863 ...
4  39  134  319  624  1079 ...
5  47  161  383  749  1295 ...
...

Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé and Nicolas Trotignon, (Theta, triangle)-free and (even hole, K4)-free graphs. Part 2 : bounds on treewidth, arXiv:2001.01607 [cs.DM], 2020. See p. 7.
Index entries for sequences related to trees.

Cf. A000578, A001093, A001477 (k = 1), A004771 (k = 2), A068601 (n = 2), A085537, A109129, A123865 (main diagonal), A325543, A325612.

T[n_,k_]:=(n-1)*k^3-1; Flatten[Table[T[n+1-k,k],{n,2,12},{k,1,n-1}]]

PARI
```
T(n, k) = (n - 1)*k^3 - 1
```

O.g.f.: x^2*y*(y*(7 - 2*y + y^2) + x*(1 - y)^3)/((1 - x)^2*(1 - y)^4).
E.g.f.: -1 + exp(x) - x + exp(y)*x + exp(y)*(1 + y + 3*y^2 + y^3) + exp(x + y)*(-1 +(-1 + x)*y*(1 + 3*y + y^2)).
T(n, k) = n*A000578(k) - A001093(k).
T(n, n) = A085537(n) - 1 for n > 1.
T(n, k) = T(n+1, 1)*T(2, k) + T(n, 1).

cp's OEIS Frontend

A358727 Matula-Goebel numbers of rooted trees with greater number of leaves (width) than node-height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A333267 If n = Product (p_j^k_j) then a(n) = Product (a(pi(p_j)) * k_j), where pi = A000720.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A358723 Number of n-node rooted trees of edge-height equal to their number of leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A336194 Table read by antidiagonals upwards: T(n,k) = (n - 1)*k^3 - 1, with n > 1 and k > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula