A304173 Number of rooted plane trees where every branch that has a predecessor (a branch directly to its left and emanating from the same root) has at least as many leaves as its predecessor.

1, 1, 2, 5, 13, 34, 90, 242, 660, 1822, 5085, 14333, 40759, 116817, 337140, 979098, 2859439, 8393113, 24747052, 73262246, 217681621, 648939319, 1940461444, 5818595438, 17492367097, 52712114792, 159193762250, 481754196170, 1460650624068, 4436422703787, 13496947320929

Offset

1,3

Links

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

Formula

G.f.: A(x,1) where A(x,y) satisfies A(x,y) = x*(y-1 + 1/(Product_{k>=1} 1 - y^k * [y^k] A(x,y))). - Andrew Howroyd, Jan 22 2021

Example

The a(5) = 13 plane trees:
  ((((o)))), (((oo))), (((o)o)), ((o(o))), ((ooo)),
  (((o))o), (o((o))), (o(oo)), ((o)(o)),
  ((o)oo), (o(o)o), (oo(o)),
  (oooo).
Missing from this list is ((oo)o).

Mathematica

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

Prog

(PARI) seq(n)={my(p=x*y+O(x^2)); for(n=2, n, p=x*(y-1 + 1/prod(k=1, n-1, 1 - y^k*polcoef(p, k, y)))); Vec(subst(p, y, 1))} \\ Andrew Howroyd, Jan 22 2021

Crossrefs

Cf. A000081, A000108, A001003, A001006, A003238, A007853, A126120, A291442, A291443, A304175.

Sequence in context: A114173 A238435 A023425 * A217896 A360709 A090827

Adjacent sequences: A304170 A304171 A304172 * A304174 A304175 A304176

Keyword

nonn

Author

Gus Wiseman, Aug 16 2018

Extensions

Terms a(15) and beyond from Andrew Howroyd, Jan 22 2021

Status

approved