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

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,3

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

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]

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

Example

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

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

Prog

(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
(Magma) [Catalan(n div 2)*Catalan(((n+1)) div 2) : n in [1..30]]; // Vincenzo Librandi, Apr 16 2019

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

Sequence in context: A052829 A339295 A001998 * A302093 A292617 A148093

Adjacent sequences: A005814 A005815 A005816 * A005818 A005819 A005820

Keyword

nonn,easy

Author

Simon Plouffe and N. J. A. Sloane

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

Status

approved