A331106 Number of plane trees of total weight n of combinatorial class T=Z*U + Z*T^2/(1-T) with nodes Z of weight one and leaves U of weight three.

0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 1, 5, 5, 0, 1, 9, 21, 14, 1, 14, 56, 84, 43, 20, 120, 300, 331, 159, 225, 825, 1486, 1322, 814, 1925, 5006, 7051, 5621, 5434, 14015, 28082, 32968, 27092, 39261, 91793, 149877, 156858, 152023, 276769, 558845, 778920, 786931, 953756

Offset

1,14

Comments

The underlying tree structure before the weights are applied (Z with weight one, U with weight three) is a series-reduced tree because a non-leaf node Z has at least two children.

References

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009.

Links

Table of n, a(n) for n=1..58.

Marko Riedel et al., Math.StackExchange, Counting plane trees

Formula

G.f.: (1 + z^4 - sqrt(z^8 - 4*z^5 - 2*z^4 +1))/(2*(z+1)).

a(n) = Sum_{k=floor(n/5)+1..floor((n-1)/4)} (1/(n-3*k)) * binomial(n-3*k,k) * binomial(k-2, n-4*k-1)) for n >= 1, n <> 4. a(4) = 1.

D-finite with recurrence: n*a(n) +(n)*a(n-1) +(n-2)*a(n-2) +(n-2)*a(n-3) +2*(-n+6)*a(n-4) +6*(-n+7)*a(n-5) +2*(-3*n+23)*a(n-6) +6*(-n+9)*a(n-7) +(-3*n+26)*a(n-8) +(n-12)*a(n-9) +(n-14)*a(n-10) +(n-14)*a(n-11)=0. - R. J. Mathar, Jan 27 2020

Example

For n=4, the tree is Z-U, for n=9 the tree is
    Z-U
   /
  Z
   \
    Z-U.

Crossrefs

Cf. A308616.

Sequence in context: A369321 A122890 A309524 * A318373 A138497 A295858

Adjacent sequences: A331103 A331104 A331105 * A331107 A331108 A331109

Keyword

nonn

Author

Marko Riedel, Jan 09 2020

Status

approved