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

Author

Marko Riedel, Jan 09 2020

Keywords

• nonn

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.

Examples

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

References

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

Links

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

Crossrefs

Cf. A308616.

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