This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005817 a(n) = C(floor(n/2 + 1/2))*C(floor(n/2 + 1)) where C(i) = Catalan numbers A000108.
(Formerly M1212)

%I M1212

%S 1,1,2,4,10,25,70,196,588,1764,5544,17424,56628,184041,613470,2044900,

%T 6952660,23639044,81662152,282105616,987369656,3455793796,12228193432,

%U 43268992144,154532114800,551900410000,1986841476000,7152629313600

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

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

%C Also, number of standard Young tableaux of height <= 4. - _Mike Zabrocki_, Mar 24 2007

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

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

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

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(b), y_4(n), p. 452.

%H T. D. Noe, <a href="/A005817/b005817.txt">Table of n, a(n) for n=0..200</a>

%H F. Bergeron, L. Favreau and D. Krob, <a href="http://dx.doi.org/10.1016/0012-365X(94)00148-C">Conjectures on the enumeration of tableaux of bounded height</a>, Discrete Math, vol. 139, no. 1-3 (1995), 463-468.

%H A. Bostan and M. Kauers, <a href="https://arxiv.org/abs/0811.2899">Automatic Classification of Restricted Lattice Walks</a>, arXiv:0811.2899 [math.CO], 2008-2009.

%H M. Bousquet-Mélou and M. Mishna, <a href="https://arxiv.org/abs/0810.4387">Walks with small steps in the quarter plane</a>, arXiv:0810.4387 [math.CO], 2008-2009.

%H R. Cori et al., <a href="http://dx.doi.org/10.1016/0097-3165(86)90018-X">Shuffle of parenthesis systems and Baxter permutations</a>, J. Combin. Theory, A 43 (1986), 1-22.

%H D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1007/BFb0072513">Chemins sous-diagonaux et tableaux de Young</a>, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.

%H Kiran S. Kedlaya and Andrew V. Sutherland, <a href="http://arXiv.org/abs/0803.4462">Hyperelliptic curves, L-polynomials and random matrices</a>, arXiv:0803.4462 [math.NT], 2008-2010.

%H Alon Regev, Amitai Regev, Doron Zeilberger, <a href="http://arxiv.org/abs/1507.03499">Identities in character tables of S_n</a>, arXiv preprint arXiv:1507.03499 [math.CO], 2015.

%H Albert Sade, <a href="/A000108/a000108_17.pdf">Sur les Chevauchements des Permutations</a>, published by the author, Marseille, 1949. [Annotated scanned copy]

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

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

%F a(n) ~ 2^(2*n+5)/(Pi*n^3). - _Vaclav Kotesovec_, Sep 11 2013

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

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

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

%o (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

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

%Y Bisections are A001246 and A005568.

%Y Column k=4 of A182172. - _Alois P. Heinz_, May 30 2012

%K nonn,easy

%O 0,3

%A Simon Plouffe and _N. J. A. Sloane_

%E Description corrected Feb 15 1997.

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

%E Offset changed by _N. J. A. Sloane_, Nov 28 2008

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 February 19 15:01 EST 2018. Contains 299334 sequences. (Running on oeis4.)