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