A005817 a(n) = C(floor(n/2 + 1/2))*C(floor(n/2 + 1)) where C(i) = Catalan numbers A000108.

1, 1, 2, 4, 10, 25, 70, 196, 588, 1764, 5544, 17424, 56628, 184041, 613470, 2044900, 6952660, 23639044, 81662152, 282105616, 987369656, 3455793796, 12228193432, 43268992144, 154532114800, 551900410000, 1986841476000, 7152629313600

Offset: 0

Author

Simon Plouffe and N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Number of lattice paths in the first quadrant that do not cross the main diagonal, go from (0,0) to a point on the x-axis and consist of n+1 steps from the set {E=(1,0), W=(-1,0), N=(0,1), S=(0,-1)}. Example: a(2)=4 because we have EEE, ENS, EEW and EWE [Gouyou-Beauchamps]. - Emeric Deutsch, Apr 29 2004

Also, number of standard Young tableaux of height <= 4. - Mike Zabrocki, Mar 24 2007

Also, number of walks within N^2 (the first quadrant of Z^2) starting at (0,0), ending on the vertical axis and consisting of n steps taken from {(-1, 1), (0, -1), (0, 1), (1, -1)}. - Manuel Kauers, Nov 18 2008

Also, number of walks within N^3 (the first octant of Z^3) starting at (0,0,0) and consisting of n steps taken from {(-1, 0, 0), (0, -1, 1), (0, 1, 0), (1, 0, -1)} - Manuel Kauers, Nov 18 2008

Also, number of n-length words w over alphabet {a,b,c,d} such that for every prefix z of w we have #(z,a) >= #(z,b) >= #(z,c)>= #(z,d), where #(z,x) counts the letters x in word z. The a(4) = 10 words are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca, abcd. - Alois P. Heinz, May 30 2012

Also, for n>0, number of coalescent histories for a maximally symmetric matching bicaterpillar gene tree and species tree with n+1 leaves, that is, a bicaterpillar divided into caterpillars of size floor(n/2+1/2) and floor(n/2+1) leaves (Rosenberg 2007, Theorem 3.10). - Noah A Rosenberg, Feb 04 2019

Examples

			There are 26 standard tableaux of size 5, one of them is of length longer than 4 so a(5) = 25.
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(b), y_4(n), p. 452.

Links

• T. D. Noe, Table of n, a(n) for n=0..200
• F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math, vol. 139, no. 1-3 (1995), 463-468.
• A. Bostan and M. Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009.
• M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
• R. Cori et al., Shuffle of parenthesis systems and Baxter permutations, J. Combin. Theory, A 43 (1986), 1-22.
• D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableaux de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.
• Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, arXiv:0803.4462 [math.NT], 2008-2010.
• Zhicong Lin, David G.L. Wang, and Tongyuan Zhao, A decomposition of ballot permutations, pattern avoidance and Gessel walks, arXiv:2103.04599 [math.CO], 2021.
• Zhicong Lin and Jing Liu, Proof of Dilks' bijectivity conjecture on Baxter permutations, arXiv:2112.11698 [math.CO], 2021.
• Alon Regev, Amitai Regev, and Doron Zeilberger, Identities in character tables of S_n, arXiv preprint arXiv:1507.03499 [math.CO], 2015.
• N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.
• Albert Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949. [Annotated scanned copy]

Crossrefs

Cf. A000108, A001405, A001006, A005700, A049401, A007579, A007578.

Bisections are A001246 and A005568.

Column k=4 of A182172. - Alois P. Heinz, May 30 2012

Programs

Magma

[Catalan(n div 2)*Catalan(((n+1)) div 2) : n in [1..30]]; // Vincenzo Librandi, Apr 16 2019

Maple

c := n->binomial(2*n,n)/(n+1); seq(c(floor((n+1)/2))*c(floor(n/2+1)), n=0..16);

Mathematica

Table[Binomial[2*Floor[(n+1)/2], Floor[(n+1)/2]]/(Floor[(n+1)/2]+1) * Binomial[2*Floor[n/2+1], Floor[n/2+1]]/(Floor[n/2+1]+1), {n,0,20}] (* Vaclav Kotesovec, Sep 11 2013 *)

PARI

c(n)=binomial(2*n, n)/(n+1)
for(n=1, 40, print1(c(floor((n+1)/2))*c(floor(n/2+1)), ", ")); \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008

Formula

G.f.: (hypergeom([-1/2, -1/2],[1],16*x^2)-2*x*hypergeom([-1/2, 1/2],[2],16*x^2)-1+2*x-4*x^2)/(4*x^3). - Mark van Hoeij, Oct 25 2011

D-finite with recurrence (n+3)*(n+4)*a(n) = 4*(2*n+3)*a(n-1) + 16*(n-1)*n*a(n-2). - Vaclav Kotesovec, Sep 11 2013

a(n) ~ 2^(2*n+5)/(Pi*n^3). - Vaclav Kotesovec, Sep 11 2013

Extensions

Description corrected Feb 15 1997.

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008

Offset changed by N. J. A. Sloane, Nov 28 2008