login
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

%I #31 Jan 31 2024 08:03:52

%S 1,1,1,2,2,3,5,7,11,17,27,42,68,107,175,278,458,733,1215,1956,3258,

%T 5271,8815,14321,24031,39181,65937,107840,181936,298367,504473,829307,

%U 1404879,2314453,3927495,6482788,11017802,18217839,31004871,51347351,87497297

%N 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.

%H Robert Israel, <a href="/A125189/b125189.txt">Table of n, a(n) for n = 0..4206</a>

%H J.-L. Baril, <a href="https://doi.org/10.46298/dmtcs.2158">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016).

%H R. Donaghey and L. W. Shapiro, <a href="http://dx.doi.org/10.1016/0097-3165(77)90020-6">Motzkin numbers</a>, J. Combin. Theory, Series A, 23 (1977), 291-301.

%F 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).

%F 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)).

%F 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

%F 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

%p 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);

%K nonn

%O 0,4

%A _Emeric Deutsch_, Dec 20 2006