A080936 -id:A080936 - cp's OEIS frontend

A358725 Matula-Goebel numbers of rooted trees with a greater number of internal (non-leaf) vertices than edge-height.

9, 15, 18, 21, 23, 25, 27, 30, 33, 35, 36, 39, 42, 45, 46, 47, 49, 50, 51, 54, 55, 57, 60, 61, 63, 65, 66, 69, 70, 72, 73, 75, 77, 78, 81, 83, 84, 85, 87, 90, 91, 92, 93, 94, 95, 97, 98, 99, 100, 102, 103, 105, 108, 110, 111, 113, 114, 115, 117, 119, 120, 121

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 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 terms together with their corresponding trees begin:
   9: ((o)(o))
  15: ((o)((o)))
  18: (o(o)(o))
  21: ((o)(oo))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  30: (o(o)((o)))
  33: ((o)(((o))))
  35: (((o))(oo))
  36: (oo(o)(o))
  39: ((o)(o(o)))
  42: (o(o)(oo))
  45: ((o)(o)((o)))
  46: (o((o)(o)))
  47: (((o)((o))))
  49: ((oo)(oo))
  50: (o((o))((o)))

Gus Wiseman, The first 64 ordered trees with a greater number of internal vertices than edge-height.

Complement of A209638 (the case of equality).
These trees are counted by A316321.
Positions of positive terms in A358724.
The case of equality for node-height is A358576.
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.
Differences: A358580, A358724, A358726, A358729.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A185650, A206487, A358577, A358578, A358581-A358586, A358587, A358592, A358730.

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

A342507(a(n)) > A109082(a(n)).

A358730 Positions of first appearances in A358729 (number of nodes minus node-height).

Original entry on oeis.org

1, 4, 8, 16, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049

Offset: 1

Gus Wiseman, Dec 01 2022

First differs from A334198 in having 13122 instead of 12005.
Node-height is the number of nodes in the longest path from root to leaf.
After initial terms, this appears to become A038754.

			The terms together with their corresponding rooted trees begin:
      1: o
      4: (oo)
      8: (ooo)
     16: (oooo)
     27: ((o)(o)(o))
     54: (o(o)(o)(o))
     81: ((o)(o)(o)(o))
    162: (o(o)(o)(o)(o))
    243: ((o)(o)(o)(o)(o))
    486: (o(o)(o)(o)(o)(o))
    729: ((o)(o)(o)(o)(o)(o))

Positions of first appearances 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. A080936, A206487, A209638, A316321, A358576, A358577, A358592, A358725, A358731.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
rd=Table[Count[MGTree[n],_,{0,Infinity}]-(Depth[MGTree[n]]-1),{n,10000}];
Table[Position[rd,k][[1,1]],{k,Union[rd]}]

A206464 Number of length-n Catalan-RGS (restricted growth strings) such that the RGS is a valid mixed-radix number in falling factorial basis.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 74, 218, 672, 2126, 6908, 22876, 77100, 263514, 911992, 3189762, 11261448, 40083806, 143713968, 518594034, 1882217168, 6867064856, 25172021144, 92666294090, 342467464612, 1270183943200, 4726473541216, 17640820790092, 66025467919972

Offset: 0

Joerg Arndt, Feb 08 2012

nonn

Catalan-RGS are strings with first digit d(0)=zero, and d(k+1) <= d(k)+1, falling factorial mixed-radix numbers have last digit <= 1, second last <= 2, etc.
The digits of the RGS are <= floor(n/2).
The first few terms are the same as for A089429.
Column k=0 of A264869. - Peter Bala, Nov 27 2015
a(n) = A291680(n+1,n+1). - Alois P. Heinz, Aug 29 2017

			The a(5)=26 strings for n=5 are (dots for zeros):
   1:  [ . . . . . ]
   2:  [ . . . . 1 ]
   3:  [ . . . 1 . ]
   4:  [ . . . 1 1 ]
   5:  [ . . 1 . . ]
   6:  [ . . 1 . 1 ]
   7:  [ . . 1 1 . ]
   8:  [ . . 1 1 1 ]
   9:  [ . . 1 2 . ]
  10:  [ . . 1 2 1 ]
  11:  [ . 1 . . . ]
  12:  [ . 1 . . 1 ]
  13:  [ . 1 . 1 . ]
  14:  [ . 1 . 1 1 ]
  15:  [ . 1 1 . . ]
  16:  [ . 1 1 . 1 ]
  17:  [ . 1 1 1 . ]
  18:  [ . 1 1 1 1 ]
  19:  [ . 1 1 2 . ]
  20:  [ . 1 1 2 1 ]
  21:  [ . 1 2 . . ]
  22:  [ . 1 2 . 1 ]
  23:  [ . 1 2 1 . ]
  24:  [ . 1 2 1 1 ]
  25:  [ . 1 2 2 . ]
  26:  [ . 1 2 2 1 ]

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A080935, A080936, A264869, A291680.

b:= proc(i, l) option remember;
      `if`(i<=0, 1, add(b(i-1, j), j=0..min(l+1, i)))
    end:
a:= n-> b(n-1, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 08 2012

b[i_, l_] := b[i, l] = If[i <= 0, 1, Sum[b[i-1, j], {j, 0, Min[l+1, i]}]];
a[n_] := b[n-1, 0];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)

Conjecture: a(n) = Sum_{k = 0..floor(n/4)} (-1)^k * C(floor(n/2) + 1 - k, k + 1) * a(n - 1 - k), a(0) = 1. - Gionata Neri, Jun 17 2018

A259885 a(n) = max{T(n,k), k=1..n}, where T(n,k) is the number of Dyck paths of length 2n and height k (1<=k<=n).

Original entry on oeis.org

1, 1, 3, 7, 18, 57, 169, 484, 1684, 5661, 18579, 59917, 214058, 760487, 2665884, 9246276, 31945379, 117939506, 431530926, 1567159901, 5655480303, 20299352107, 74300429926, 278279597781, 1037075511926, 3848154018734, 14224439297732, 52402156308977

Offset: 1

Gheorghe Coserea, Jul 07 2015

			For n=4, a(4)=7 because T(4,1)=1, T(4,2)=7, T(4,3)=5, T(4,4)=1.

Gheorghe Coserea, Table of n, a(n) for n = 1..1535

Cf. A080936, A259899 (position of maximum), A265180.

a(n) ~ 4*K/sqrt(Pi) * 4^n/n^2, where K = 0.2675... (see A265180). - Gheorghe Coserea, Dec 05 2015

A262600 Number of Dyck paths of semilength n and height exactly 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 7, 33, 132, 484, 1684, 5661, 18579, 59917, 190696, 600744, 1877256, 5828185, 17998783, 55342617, 169552428, 517884748, 1577812060, 4796682165, 14555626635, 44100374341, 133436026192, 403279293648, 1217616622992, 3673214880049, 11072960931319

Offset: 0

Ran Pan, Sep 25 2015

			a(4) = 1 because the only favorable path is UUUUDDDD.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (7,-16,13,-3).

Cf. A001519, A124302.

Column k=4 of A080936.

[((3^(n-1)+1)/2)-Fibonacci(2*n-1): n in [1.. 35]]; // Vincenzo Librandi, Sep 26 2015

CoefficientList[ Series[x^4/((x-1) (3 x-1) (x^2-3 x+1)), {x, 0, 30}], x]

a(n) = if( n<1, n==0, (3^(n-1) + 1) / 2) - fibonacci(2*n-1); vector(30, n, a(n-1)) \\ Altug Alkan, Sep 25 2015

concat(vector(4), Vec(x^4/((1-x)*(1-3*x)*(1-3*x+x^2)) + O(x^100))) \\ Colin Barker, Feb 08 2016

a(n) = A124302(n) - A001519(n).
G.f.: x^4/((x-1)*(3*x-1)*(x^2-3*x+1)).
a(n) = A080936(n,4).
From Colin Barker, Feb 08 2016: (Start)
a(n) = 7*a(n-1)-16*a(n-2)+13*a(n-3)-3*a(n-4) for n>4.
a(n) = 2^(-1-n)*(5*2^n*(3+3^n)+3*(-5+sqrt(5))*(3+sqrt(5))^n-3*(3-sqrt(5))^n*(5+sqrt(5)))/15 for n>0. (End)
E.g.f.: (2 + 3*exp(x) + exp(3*x))/6 - exp(3*x/2)*(5*cosh(sqrt(5)*x/2) - sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, May 21 2024

A268316 a(n) is the number of Dyck paths of length 4n and height n.

Original entry on oeis.org

1, 1, 7, 57, 484, 4199, 36938, 328185, 2937932, 26457508, 239414383, 2175127695, 19827974412, 181266501290, 1661241473220, 15257624681145, 140400178555644, 1294141164447692, 11946771748196428, 110435320379615620, 1022108852175416720, 9470416604629933935

Offset: 0

Gheorghe Coserea, Feb 01 2016

Equivalently, a(n) is the number of rooted plane trees with 2n+1 nodes and height n.

			For n = 2 the a(2) = 7 solutions are
              /\/\/\       |
LLRLRLRR     /      \     /|\
................................
                /\        /|\
LRLLRRLR     /\/  \/\      |
................................
              /\  /\       /\
LLRRLLRR     /  \/  \     /  \
................................
              /\           /|\
LLRRLRLR     /  \/\/\     /
................................
                  /\      /|\
LRLRLLRR     /\/\/  \        \
................................
              /\/\         /\
LLRLRRLR     /    \/\     /\
................................
                /\/\       /\
LRLLRLRR     /\/    \       /\

Gheorghe Coserea, Table of n, a(n) for n = 0..1000.
Gheorghe Coserea, Solutions for n=3.
Gheorghe Coserea, Solutions for n=4.
Gheorghe Coserea, MiniZinc model for generating solutions.

Cf. A080936, A268315.

Column k=2 of A289481.

[Binomial(4*n, n)*2*(2*n+3)*(2*n^2+1)/((3*n+1)*(3*n+2)*(3*n+3)): n in [1..30]]; // Vincenzo Librandi, Feb 04 2016

Table[Binomial[4 n, n] 2 (2 n + 3) (2 n^2 + 1) / ((3 n + 1) (3 n + 2) (3 n + 3)), {n, 1, 25}] (* Vincenzo Librandi, Feb 04 2016 *)
Drop[CoefficientList[Series[-((-1 + HypergeometricPFQ[{-3/4, -1/2, -1/4}, {1/3, 2/3}, 256 x/27])/(4x)) + 4/5 x HypergeometricPFQ[{5/4, 3/2, 7/4}, {7/3, 8/3}, 256 x/27] + 8/3 x^2 HypergeometricPFQ[{9/4, 5/2, 11/4}, {10/3, 11/3}, 256x/27], {x, 0, 20}], x], 1] (* Benedict W. J. Irwin, Aug 09 2016 *)

a(n) = binomial(4*n,n) * 2*(2*n+3)*(2*n^2+1)/((3*n+1)*(3*n+2)*(3*n+3));
vector(21, i, a(i))

a(n) = T(2n,n), where T(n,k) is defined by A080936.
a(n) = binomial(4*n,n) * 2*(2*n+3)*(2*n^2+1)/((3*n+1)*(3*n+2)*(3*n+3)).
a(n) ~ K * A268315^n / sqrt(n), where K = 8/27 * sqrt(2/(3*Pi)) = 0.13649151584...
G.f.: -((3F2(-3/4, -1/2, -1/4; 1/3, 2/3; 256*x/27)-1)/(4*x)) + 4/5*x*3F2(5/4, 3/2, 7/4; 7/3, 8/3; 256*x/27) + 8/3*x^2*3F2(9/4, 5/2, 11/4; 10/3, 11/3; 256*x/27). - Benedict W. J. Irwin, Aug 09 2016
Recurrence: 3*(n+1)*(2*n + 1)*(3*n + 1)*(3*n + 2)*(2*n^2 - 4*n + 3)*a(n) = 8*(2*n - 1)*(2*n + 3)*(4*n - 3)*(4*n - 1)*(2*n^2 + 1)*a(n-1). - Vaclav Kotesovec, Aug 10 2016

Added a(0)=1, adjusted b-file - N. J. A. Sloane, Dec 22 2016

A080935 Triangle read by rows of number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2n steps with all values less than or equal to k.

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 1, 8, 13, 14, 1, 16, 34, 41, 42, 1, 32, 89, 122, 131, 132, 1, 64, 233, 365, 417, 428, 429, 1, 128, 610, 1094, 1341, 1416, 1429, 1430, 1, 256, 1597, 3281, 4334, 4744, 4846, 4861, 4862, 1, 512, 4181, 9842, 14041, 16016, 16645, 16778, 16795

Offset: 1

Henry Bottomley, Feb 25 2003

T(n,k) is the number of different out-stack sequences of n elements to be pushed into a stack of size k. E.g. T(3,2) = 4 since the 4 possible out-stack sequences are 123, 132, 213, 231; 321 is not allowed since it requires a stack of size 3. - Jianing Song, Oct 28 2021

			Rows start:
  1;
  1,2;
  1,4,5;
  1,8,13,14;
  1,16,34,41,42;
  ...
T(3,2)=4 since the paths of length 2*3 (7 points) with all values less than or equal to 2 can take the routes 0101010, 0101210, 0121010 or 0121210, but not 0123210.

Vince White, Enumeration of Lattice Paths with Restrictions, (2024). Electronic Theses and Dissertations. 2799. See pp. 20, 25.

Cf. A000108, A079214, A080934, A080936.

For 1<=k<=n, T(n, k) =A080934(n, k) =T(n, k-1)+A080936(n, k).

A289419 Number of Dyck paths of semilength n and height exactly 6.

Original entry on oeis.org

1, 11, 75, 410, 1975, 8778, 36938, 149501, 587951, 2262375, 8558854, 31945379, 117939506, 431530926, 1567159901, 5655480303, 20299352107, 72522832282, 258054207727, 914973048634, 3234061126690, 11399437533757, 40081465493919, 140617625960143, 492342898340494

Offset: 6

Alois P. Heinz, Jul 06 2017

Alois P. Heinz, Table of n, a(n) for n = 6..1000
Index entries for linear recurrences with constant coefficients, signature (11,-46,91,-86,34,-4).

Column k=6 of A080936.

G.f.: x^6/((2*x-1)*(2*x^2-4*x+1)*(x^3-6*x^2+5*x-1)).

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

A289418 Number of Dyck paths of semilength n and height exactly 5.

Original entry on oeis.org

1, 9, 52, 247, 1053, 4199, 16017, 59224, 214058, 760487, 2665884, 9246276, 31793724, 108548332, 368400045, 1244027317, 4182854728, 14012220027, 46789129817, 155798575851, 517500496981, 1715190689420, 5673820630478, 18736674281091, 61779282616728

Offset: 5

Alois P. Heinz, Jul 06 2017

Alois P. Heinz, Table of n, a(n) for n = 5..1000
Index entries for linear recurrences with constant coefficients, signature (9,-29,40,-22,3).

Column k=5 of A080936.

LinearRecurrence[{9,-29,40,-22,3},{1,9,52,247,1053},40] (* Harvey P. Dale, Dec 07 2018 *)

G.f.: -x^5/((x-1)*(3*x-1)*(x^3-6*x^2+5*x-1)).

cp's OEIS Frontend

A358725 Matula-Goebel numbers of rooted trees with a greater number of internal (non-leaf) vertices than edge-height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A358730 Positions of first appearances in A358729 (number of nodes minus node-height).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A206464 Number of length-n Catalan-RGS (restricted growth strings) such that the RGS is a valid mixed-radix number in falling factorial basis.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A259885 a(n) = max{T(n,k), k=1..n}, where T(n,k) is the number of Dyck paths of length 2n and height k (1<=k<=n).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A262600 Number of Dyck paths of semilength n and height exactly 4.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A268316 a(n) is the number of Dyck paths of length 4n and height n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A080935 Triangle read by rows of number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2n steps with all values less than or equal to k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A289419 Number of Dyck paths of semilength n and height exactly 6.

Views

Author