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

 

Logo


Hints
(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)
12
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 (list; graph; refs; listen; history; text; internal format)
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

REFERENCES

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.

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 tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.

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

A. Bostan and M. Kauers, 2008. Automatic Classification of Restricted Lattice Walks, ArXiv 0811.2899.

M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.

Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, arXiv:0803.4462 [math.NT], 2008-2010.

Alon Regev, Amitai Regev, Doron Zeilberger, Identities in character tables of S_n, arXiv preprint arXiv:1507.03499, 2015

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

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

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: A032128 A052829 A001998 * A148093 A206289 A148094

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

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 July 22 00:13 EDT 2017. Contains 289648 sequences.