login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066357 Number of ordered (i.e., planar) trees on 2n edges with every subtree at the root having an even number of edges. 12
1, 1, 6, 53, 554, 6362, 77580, 986253, 12927170, 173452334, 2370742868, 32892031042, 462030186916, 6557906929108, 93909078262808, 1355087936016957, 19684187540818866, 287612514032460070, 4224238030616082948, 62329883931236020470, 923519220367120779820 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Row sums of A078990. First column of A079513.

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

Series reversion of Sum_{n>0} -a(n)(-x)^n is g.f. of A005900.

a(n) = ((2^(4n))/Gamma(1/2)) * ((6*(2n+1)*Gamma(2n+1/2)/Gamma(2n+3))-2Gamma(n+1/2)/Gamma(n+2)). - David Dickson (dcmd(AT)unimelb.edu.au), Nov 10 2009

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

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.

A. de Mier and M. Noy, A solution to the tennis ball problem, arXiv:math/0311242 [math.CO], 2003.

J.-G. Luque and J.-Y. Thibon, Noncommutative Symmetric Functions Associated with a Code, Lazard Elimination and Witt Vectors, Discrete Math. Theor. Comput. Sci. 9 (2007), no. 2, 59-72.

D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (p. 333).

Ran Pan, Problem 1, Project P.

Ran Pan, Algorithmic Solution to Problem 1 (and linear extensions of general one-level grid-like posets), Project P.

A. Regev, Enumerating triangulations by parallel diagonals, arXiv preprint arXiv:1208.3915 [math.CO], 2012. - From N. J. A. Sloane, Dec 25 2012

FORMULA

For n>0, a(n) = sum(C(2*r-1)*a(n-r), r=1..n). Here C(2*r-1) is a Catalan number (A000108). - Paul Boddington, Mar 14 2003

G.f.: 2/(1+4*sqrt(x)/(sqrt(1+4*sqrt(x))-sqrt(1-4*sqrt(x)))).

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.

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

Convolution of A079489 with itself: (1, 6, 53, 554, ...) = (1, 3, 22, 211, ...)*(1, 3, 22, 211, ...).

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

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

a(n) ~ (3-2*sqrt(2)) * 2^(4*n) / (n^(3/2) * sqrt(2*Pi)). - Vaclav Kotesovec, Mar 21 2014

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

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

MAPLE

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 A. Sellers, Feb 11 2002

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

MATHEMATICA

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 *)

PROG

(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))

(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

CROSSREFS

Cf. A078990, A079513, A001448, A005900, A079489, A274644, A274763.

Sequence in context: A027835 A055973 A223345 * A276365 A185148 A243921

Adjacent sequences:  A066354 A066355 A066356 * A066358 A066359 A066360

KEYWORD

nonn,easy

AUTHOR

Louis Shapiro, Feb 01 2002

EXTENSIONS

More terms from James A. Sellers, Feb 11 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 06:54 EDT 2017. Contains 292502 sequences.