A125189 Number of symmetric bushes with n edges. I.e., number of ordered trees with n edges, no non-root vertices of outdegree 1 and symmetrical with respect to the vertical axis passing through the root.

1, 1, 1, 2, 2, 3, 5, 7, 11, 17, 27, 42, 68, 107, 175, 278, 458, 733, 1215, 1956, 3258, 5271, 8815, 14321, 24031, 39181, 65937, 107840, 181936, 298367, 504473, 829307, 1404879, 2314453, 3927495, 6482788, 11017802, 18217839, 31004871, 51347351, 87497297

Offset

0,4

Links

Robert Israel, Table of n, a(n) for n = 0..4206

J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016).

R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.

Formula

a(n) = A082958(n) + A082958(n-1) for n >= 1 (every symmetric bush with n edges consists of the symmetric short bushes with n edges and the symmetric short bushes with n-1 edges hanging on an edge emanating from the root).

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

Conjecture: (n+1)*a(n) -3*a(n-1) +(-4*n+5)*a(n-2) +(-2*n+7)*a(n-3) +3*a(n-4) +(4*n-5)*a(n-5) +(8*n-49)*a(n-6) +3*(2*n-13)*a(n-7) +3*(n-8)*a(n-8)=0. - R. J. Mathar, Jun 08 2016

The conjecture follows from the differential equation 3*z^7 + z^6 + 3*z^5 + 5*z^4 + z^3 + 3*z^2 + z - 1 + (3*z^7 - z^6 + 15*z^5 + 3*z^4 + z^3 - 3*z^2 - 3*z + 1)*g(z) + (3*z^9 + 6*z^8 + 8*z^7 + 4*z^6 - 2*z^4 - 4*z^3 + z)*g'(z) = 0 satisfied by the g.f.. - Robert Israel, Nov 21 2017

Maple

G:=(1+z)*((1-z)*(1+z^2)-(1+z)*sqrt(1-2*z^2-3*z^4))/(2*z*(z^3+z^2+z-1)): Gser:=series(G, z=0, 50): seq(coeff(Gser, z, n), n=0..45);

Crossrefs

Sequence in context: A066889 A214040 A077419 * A226498 A196375 A300440

Adjacent sequences: A125186 A125187 A125188 * A125190 A125191 A125192

Keyword

nonn

Author

Emeric Deutsch, Dec 20 2006

Status

approved