cp's OEIS Frontend

A066357 Number of ordered (i.e., planar) trees on 2n edges with every subtree at the root having an even number of edges.

%I A066357 #97 Jul 02 2025 16:02:01
%S A066357 1,1,6,53,554,6362,77580,986253,12927170,173452334,2370742868,
%T A066357 32892031042,462030186916,6557906929108,93909078262808,
%U A066357 1355087936016957,19684187540818866,287612514032460070,4224238030616082948,62329883931236020470,923519220367120779820
%N A066357 Number of ordered (i.e., planar) trees on 2n edges with every subtree at the root having an even number of edges.
%C A066357 Row sums of A078990. First column of A079513.
%C A066357 a(n) is the number of walks from (0,0) to (2n,2n) using steps (0,1) and (1,0) which never stray below the line y=x and which avoid the points (m,m) m odd. - _Paul Boddington_, Mar 14 2003
%C A066357 Series reversion of Sum_{n>0} -a(n)(-x)^n is g.f. of A005900.
%C A066357 a(n) is the number of linear extensions of the one-level grid poset G[(0^n), (1^(n-1)), (1^(n-1))]. The definition of a one-level grid poset can be found in the Pan links. - _Ran Pan_, Jul 05 2016
%C A066357 These numbers have the same parity as the Catalan numbers C(n), that is, a(n) is even except when n has the form 2^m - 1. This follows immediately from the formula a(n) = C(2*n+1) + 2*C(2*n) - 2^(2*n + 1)*C(n) given below by Callan. We conjecture that a(n) and C(n) have the same 2-adic valuation (checked up to n = 100). - _Peter Bala_, Aug 02 2016
%H A066357 Vincenzo Librandi, <a href="/A066357/b066357.txt">Table of n, a(n) for n = 0..200</a>
%H A066357 C. Banderier and D. Merlini, <a href="http://algo.inria.fr/banderier/Papers/infjumps.ps">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.
%H A066357 Nantel Bergeron, Cesar Ceballos, Vincent Pilaud, <a href="https://arxiv.org/abs/1807.03044">Hopf dreams</a>, arXiv:1807.03044 [math.CO], 2018. See p. 17.
%H A066357 A. de Mier and M. Noy, <a href="https://arxiv.org/abs/math/0311242">A solution to the tennis ball problem</a>, arXiv:math/0311242 [math.CO], 2003.
%H A066357 J.-G. Luque and J.-Y. Thibon, <a href="https://arxiv.org/abs/math/0607254">Noncommutative Symmetric Functions Associated with a Code, Lazard Elimination and Witt Vectors</a>, arXiv:math/0607254 [math.CO], 2006; Discrete Math. Theor. Comput. Sci. 9 (2007), no. 2, 59-72.
%H A066357 D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://dx.doi.org/10.1006/jcta.2002.3273">The tennis ball problem</a>, J. Combin. Theory, A 99 (2002), 307-344 (p. 333).
%H A066357 Ran Pan, <a href="http://www.math.ucsd.edu/~projectp/problems/p1.html">Problem 1</a>, Project P.
%H A066357 Ran Pan, <a href="http://www.math.ucsd.edu/~projectp/problems/solutions/OneLevelGridPoset.pdf">Algorithmic Solution to Problem 1 (and linear extensions of general one-level grid-like posets)</a>, Project P.
%H A066357 A. Regev, <a href="http://arxiv.org/abs/1208.3915">Enumerating triangulations by parallel diagonals</a>, arXiv:1208.3915 [math.CO], 2012, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Regev/alon3.html">J. Int. Seq. 15 (2012) #12.8.5</a>
%F A066357 For n>0, a(n) = Sum_{r=1..n} C(2*r-1)*a(n-r). Here C(2*r-1) is a Catalan number (A000108). - _Paul Boddington_, Mar 14 2003
%F A066357 G.f.: 2/(1+4*sqrt(x)/(sqrt(1+4*sqrt(x))-sqrt(1-4*sqrt(x)))).
%F A066357 D-finite with recurrence a(n)*(2*n-1)*(n+1)n = a(n-1)*(32*n^2 - 64*n + 39)*2*n - a(n-2)*(2*n-3)*(4*n-5)*(4*n-7)*16, n>1.
%F A066357 a(0) = 1,a(n) = (1/n)*Sum_{k=0..n} C(4*n,k)*C(3*n-k-2,n-k-1), n>1. - _Paul Barry_, Apr 09 2007
%F A066357 a(n) = ((2^(4*n))/Gamma(1/2)) * ((6*(2*n+1)*Gamma(2*n+1/2)/Gamma(2*n+3))-2*Gamma(n+1/2)/Gamma(n+2)). - David Dickson (dcmd(AT)unimelb.edu.au), Nov 10 2009
%F A066357 Convolution of A079489 with itself: (1, 6, 53, 554, ...) = (1, 3, 22, 211, ...)*(1, 3, 22, 211, ...).
%F A066357 Proof. Working with Dyck paths, we must show that Dyck paths of size (semilength) 2n, all of whose components (constituent primitive Dyck paths) have even size, are equinumerous with ordered pairs of nonempty Dyck paths of total size 2n in each of which the first component is of odd size and all other components (if any) are of even size. Given a Dyck path P of the former class, use the first return decomposition to write P (uniquely) as the concatenation of U A_1 A_2 ... A_j O E D Q where U denotes upstep, D denotes downstep, A_1,...,A_j are all primitive Dyck paths of even size with j>=0, O is a primitive Dyck path of odd size, E is a Dyck path of even size, and Q is a Dyck path in which all components are of even size. Then P -> (O A_1 A_2 ... A_j, U E D Q) is the desired bijection. QED - _David Callan_, Apr 11 2012
%F A066357 a(n) = C(2*n+1) + 2*C(2*n) - 2^(2*n+1)*C(n), where C(n) is the Catalan number A000108. This formula can be obtained by manipulating generating functions. The equivalence of this formula and the Barry (Apr 09 2007) sum can be established by the WZ method with a second-order operator. A combinatorial interpretation of the Barry sum would be nice. - _David Callan_, Apr 10 2012
%F A066357 a(n) ~ (3-2*sqrt(2)) * 2^(4*n) / (n^(3/2) * sqrt(2*Pi)). - _Vaclav Kotesovec_, Mar 21 2014
%F A066357 exp( Sum_{n >= 1} binomial(4*n,2*n)*x^n/n ) = 1 + 6*x + 53*x^2 + 554*x^3 + ... is an o.g.f. for this sequence omitting the initial term. See A001448. - _Peter Bala_, Oct 02 2015
%F A066357 a(n) = binomial(3*n-2,n-1)*hypergeom([1-n,-4*n],[2-3*n],-1)/n for n>=1. - _Peter Luschny_, Oct 15 2015
%F A066357 a(n) = 3*(2*n+1) /(2*n+2) /(4*n+1) *binomial(4*n+2,2*n+1) -4^n /(2*n+1) *binomial(2*n+2,n+1) [Merlini et al F_n formula] - _R. J. Mathar_, Oct 01 2021
%p A066357 gf := (1-sqrt(1-4*z)-sqrt(1+4*z)+sqrt(1-16*z^2))/(z*(sqrt(1-4*z)-sqrt(1+4*z))):s := series(gf, z, 80): for i from 0 to 50 by 2 do printf(`%d,`,coeff(s,z,i)) od: # _James Sellers_, Feb 11 2002
%p A066357 a := n -> `if`(n=0,1,binomial(3*n-2,n-1)*hypergeom([1-n,-4*n],[2-3*n], -1)/n): seq(simplify(a(n)),n=0..20); # _Peter Luschny_, Oct 15 2015
%t A066357 CoefficientList[Series[2/(1 + 4 Sqrt[x]/(Sqrt[1 + 4 Sqrt[x]] - Sqrt[1 - 4 Sqrt[x]])), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Mar 21 2014 *)
%o A066357 (PARI) a(n)=local(A); if(n<1,n==0,A=sqrt(1+4*x+O(x^(2*n+2))); A-=subst(A,x,-x); polcoeff(((2*A-8*x)/A^2)^2,2*n))
%o A066357 (PARI) vector (100, n, n--; if(n<1, 1, sum(k=0, n, binomial(4*n,k)*binomial(3*n-k-2,n-k-1)/n))) \\ _Altug Alkan_, Oct 07 2015
%o A066357 (Magma) [1] cat [(&+[Binomial(4*n,k)*Binomial(3*n-k-2,n-k-1)/n: k in [0..n]]): n in [1..30]]; // _G. C. Greubel_, Jan 15 2019
%o A066357 (Sage) [1] + [sum(binomial(4*n,k)*binomial(3*n-k-2,n-k-1)/n for k in (0..n)) for n in (1..30)] # _G. C. Greubel_, Jan 15 2019
%Y A066357 Cf. A078990, A079513, A001448, A005900, A079489, A274644, A274763.
%K A066357 nonn,easy
%O A066357 0,3
%A A066357 _Louis Shapiro_, Feb 01 2002