|
%I M1212 #85 Sep 08 2022 08:44:34
%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
%C 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
%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 Zhicong Lin, David G.L. Wang, and Tongyuan Zhao, <a href="https://arxiv.org/abs/2103.04599">A decomposition of ballot permutations, pattern avoidance and Gessel walks</a>, arXiv:2103.04599 [math.CO], 2021.
%H Zhicong Lin and Jing Liu, <a href="https://arxiv.org/abs/2112.11698">Proof of Dilks' bijectivity conjecture on Baxter permutations</a>, arXiv:2112.11698 [math.CO], 2021.
%H Alon Regev, Amitai Regev, and 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 N. A. Rosenberg, <a href="https://doi.org/10.1089/cmb.2006.0109">Counting coalescent histories</a>, J. Comput. Biol. 14 (2007), 360-377.
%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 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
%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)
%o for(n=1, 40, print1(c(floor((n+1)/2))*c(floor(n/2+1)), ", ")); \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008
%o (Magma) [Catalan(n div 2)*Catalan(((n+1)) div 2) : n in [1..30]]; // _Vincenzo Librandi_, Apr 16 2019
%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
|
