|
|
A005817
|
|
a(n) = C(floor(n/2 + 1/2))*C(floor(n/2 + 1)) where C(i) = Catalan numbers A000108.
(Formerly M1212)
|
|
19
|
|
|
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
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
|
|
|
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
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Description corrected Feb 15 1997.
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008
|
|
STATUS
|
approved
|
|
|
|