|
%I M2975 #160 Jun 15 2023 17:00:06
%S 1,1,3,14,84,594,4719,40898,379236,3711916,37975756,403127256,
%T 4415203280,49671036900,571947380775,6721316278650,80419959684900,
%U 977737404590100,12058761323277900,150656212896017400,1904342169333848400,24328661192286773400,313839729380499376860
%N a(n) = C(n)*C(n+2) - C(n+1)^2 where C() are the Catalan numbers A000108.
%C The old name was: Number of closed walks of 2n unit steps north, east, south, or west starting and ending at the origin and confined to the first octant.
%C Image of Catalan numbers (A000108) under "little Hankel" transform that sends [c_0, c_1, ...] to [d_0, d_1, ...] where d_n = c_n^2 - c_{n+1}*c_{n-1}.
%C The Niederhausen reference counts various classes of first octant paths by number of contacts with the line y=x. - _David Callan_, Sep 18 2007
%C In Sloane and Plouffe (1995) this was incorrectly described as "Dyck paths".
%C Also matchings avoiding a certain pattern (see J. Bloom and S. Elizalde). - _N. J. A. Sloane_, Jan 02 2013
%C From _Bruce Westbury_, Aug 22 2013: (Start)
%C a(n) is also the number of nested pairs of Dyck paths of length n starting and ending at the origin;
%C a(n) is also the number of 3-noncrossing perfect matchings on 2n points;
%C a(n) is also the number of 2-triangulations on n-gon;
%C a(n) is also the dimension of the invariant subspace of 2n-th tensor power of the spin representation of Spin(5);
%C a(n) is also the dimension of the invariant subspace of 2n-th tensor power of the defining representation of Sp(4). (End)
%C a(-1) = -3/2, a(-2) = -1/4 makes some formulas true for all n in Z. - _Michael Somos_, Oct 02 2014
%C a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the pattern 312. - _Colin Defant_, Jun 08 2019
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A005700/b005700.txt">Table of n, a(n) for n = 0..200</a>
%H Andrei Asinowski, Cyril Banderier, and Sarah J. Selkirk, <a href="https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2023/30.pdf">From Kreweras to Gessel: A walk through patterns in the quarter plane</a>, Séminaire Lotharingien de Combinatoire, Proc. 35th Conf. Formal Power Series and Alg. Comb. (Davis, 2023) Vol. 89B, Art. #30.
%H Jonathan Bloom and Sergi Elizalde, <a href="http://arxiv.org/abs/1211.3442">Pattern avoidance in matchings and partitions</a>, arXiv preprint arXiv:1211.3442 [math.CO], 2012. See Table 1.
%H N. Bonichon, <a href="http://dx.doi.org/10.1016/j.disc.2004.01.021"> A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths</a>, Discr. Math., 298 (2005), 104-114.
%H Matteo Cervetti and Luca Ferrari, <a href="https://arxiv.org/abs/2009.01024">Pattern avoidance in the matching pattern poset</a>, arXiv:2009.01024 [math.CO], 2020. See Section 2.
%H W. Y. C. Cheng, E. Y. P. Deng, R. R. X. Du, R. P. Stanley and C. H. Yan, <a href="https://arxiv.org/abs/math/0501230">Crossings and nestings of matchings and partitions</a>, arXiv:math/0501230 [math.CO], 2005.
%H S. J. Cyvin and I. Gutman, <a href="https://doi.org/10.1007/978-3-662-00892-8_11">Kekulé structures in benzenoid hydrocarbons</a>, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 183).
%H C. P. Davis-Stober, <a href="http://dx.doi.org/10.1016/j.jmp.2010.09.001"> A bijection between a set of lexicographic semiorders and pairs of non-crossing Dyck paths</a>, Journal of Mathematical Psychology, 54, 471-474.
%H M. de Sainte-Catherine, <a href="/A006149/a006149.pdf">Couplages et Pfaffiens en Combinatoire. Physique et Informatique.</a>, Ph.D Dissertation, Université Bordeaux I, 1983. (Annotated scanned copy)
%H Colin Defant, <a href="https://arxiv.org/abs/1904.02627">Catalan Intervals and Uniquely Sorted Permutations</a>, arXiv:1904.02627 [math.CO], 2019.
%H Stefan Felsner, Eric Fusy, Marc Noy, and David Orden, <a href="https://doi.org/10.1016/j.jcta.2010.03.017">Bijections for Baxter families and related objects</a>, J. Combin. Theory Ser. A, 118(3):993-1020, 2011. See Theorem 8.4.
%H E. Fusy, D. Poulalhon, and G. Schaeffer, <a href="https://doi.org/10.1016/j.ejc.2009.03.001">Bijective counting of plane bipolar orientations and Schnyder words</a>, Eur. J. Combinat. 30 (2009) 1646-1658, eq (2).
%H Juan B. Gil, Peter R. W. McNamara, Jordan O. Tirrell, and Michael D. Weiner, <a href="https://arxiv.org/abs/1708.00513">From Dyck paths to standard Young tableaux</a>, arXiv:1708.00513 [math.CO], 2017.
%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, Springer 1986.
%H D. Gouyou-Beauchamps, <a href="/A005700/a005700.pdf">Chemins sous-diagonaux et tableaux de Young</a>, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, Springer, 1986. (Annotated scanned copy)
%H D. Gouyou-Beauchamps. <a href="https://doi.org/10.1016/S0195-6698(89)80034-4">Standard Young tableaux of height 4 and 5</a>, European J. Combin. 10 (1989) 69 - 82.
%H Nicholas M. Katz, <a href="https://web.math.princeton.edu/~nmk/catalan11.pdf">A Note on Random Matrix Integrals, Moment Identities, and Catalan Numbers</a>, preprint, 2015; Mathemtika, Volume 62, Issue 3 2016 , pp. 811-817.
%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 Alec Mihailovs, <a href="https://arxiv.org/abs/math/9803128">Enumeration of walks on lattices</a>, arXiv:math/9803128 (1998).
%H Heinrich Niederhausen, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Niederhausen/niederhausen10.html">A Note on the Enumeration of Diffusion Walks in the First Octant by Their Number of Contacts with the Diagonal</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.3.
%H Maya Sankar, <a href="https://arxiv.org/abs/1910.08895">Further Bijections to Pattern-Avoiding Valid Hook Configurations</a>, arXiv:1910.08895 [math.CO], 2019.
%H Robert Scherer, <a href="https://www.math.ucdavis.edu/~tdenena/dissertations/202101_Scherer_Dissertation.pdf">Topics in Number Theory and Combinatorics</a>, Ph. D. Dissertation, Univ. of California Davis (2021).
%H <a href="/index/Y#Young">Index entries for sequences related to Young tableaux</a>.
%F G.f.: 3F2( [ 1, 1/2, 3/2 ]; [ 3, 4 ]; 16 x ).
%F a(n) = 6*(2*n)!*(2*n+2)!/(n!*(n+1)!*(n+2)!*(n+3)!) (Mihailovs).
%F a(n) = Det[Table[binomial[i+1, j-i+2], {i, 1, n}, {j, 1, n}]]. - _David Callan_, Jul 20 2005
%F a(n) = b(n)b(n+1)/6 where b(n) is the superballot number A007054. - _David Callan_, Feb 01 2007
%F a(n) = A000108(n)*A000108(n+2) - A000108(n+1)^2. - _Philippe Deléham_, Apr 11 2007
%F G.f.: (1 + 6*x - hypergeom([-1/2,-3/2],[2],16*x))/(4*x^2). - _Mark van Hoeij_, Nov 02 2009
%F From _Michael Somos_, Oct 02 2014: (Start)
%F a(n) = 12 * 4^n * (2*n-1)!! * (2*n+1)!! / ((n+2)! * (n+3)!).
%F D-finite with recurrence 0 = a(n) * 4*(2*n+1)*(2*n+3) - a(n+1) * (n+3)*(n+4) for all n in Z.
%F 0 = a(n)*(+65536*a(n+2) - 72192*a(n+3) + 10296*a(n+4)) + a(n+1)*(-1536*a(n+2) - 1632*a(n+3) - 282*a(n+4)) + a(n+2)*(+40*a(n+2) - 6*a(n+3) + a(n+4)) for all n in Z.
%F 0 = a(n)^2*a(n+2)*(+1792*a(n+1) - 882*a(n+2)) + a(n)*a(n+1)^2*(+768*a(n+1) + 580*a(n+2)) + 7*a(n)*a(n+1)*a(n+2)^2 +a(n+1)^3*(-18*a(n+1) + 3*a(n+2)) for all n in Z. (End)
%F a(n) ~ 3 * 2^(4*n+3) / (Pi * n^5). - _Vaclav Kotesovec_, Feb 10 2015
%F From _Peter Bala_, Feb 22 2023: (Start)
%F a(n) = (12*(2*n - 1)/((n + 1)(n + 2)(n + 3))) * Catalan(n-1)*Catalan(n+1) for n >= 1.
%F a(n) = Product_{1 <= i <= j <= n-1} (i + j + 4)/(i + j).
%F a(n) = (1/2^(n-1)) * Product_{1 <= i <= j <= n-1} (i + j + 4)/(i + j - 1) for n >= 1. (End)
%F Sum_{n>=0} a(n)/16^n = 88 - 4096/(15*Pi). - _Amiram Eldar_, May 06 2023
%e Example: a(2)=3 counts EWEW, EEWW, ENSW.
%e G.f. = 1 + x + 3*x^2 + 14*x^3 + 84*x^4 + 594*x^5 + 4719*x^6 + 40898*x^7 + ...
%t CoefficientList[ Series[ HypergeometricPFQ[ {1, 1/2, 3/2}, {3, 4}, 16 x], {x, 0, 19}], x]
%t a[ n_] := If[ n < 1, Boole[n == 0], Det[ Table[ Binomial[i + 1, j - i + 2], {i, n}, {j, n}]]]; (* _Michael Somos_, Feb 25 2014 *) (* slight modification of David Callan formula *)
%t a[ n_] := 12 * 4^n * (2*n-1)!! * (2*n+1)!! / ((n+2)! * (n+3)!); (* _Michael Somos_, Oct 02 2014 *)
%o (Magma) [6*Factorial(2*n)*Factorial(2*n+2)/(Factorial(n)*Factorial(n+1)* Factorial(n+2)*Factorial(n+3)): n in [0..25]]; // _Vincenzo Librandi_, Aug 04 2011
%o (PARI) a(n)=6*binomial(2*n+2,n)*(2*n)!/(n+1)!/(n+3)! \\ _Charles R Greathouse IV_, Aug 04 2011
%o (LiE) p_tensor(2*n,[0,1],B2)|[0,0]
%o (LiE) p_tensor(2*n,[1,0],C2)|[0,0]
%o (PARI) {a(n) = if( n<0, if( n<-2, 0, [-3/2, -1/4][-n]), 6 * (2*n)! * (2*n+2)! / (n! * (n+1)! * (n+2)! * (n+3)!))}; /* _Michael Somos_, Oct 02 2014 */
%Y A column of the triangle in A179898. A diagonal of the triangle in A185249.
%Y Row sums of A193691, A193692. - _Alois P. Heinz_, Aug 03 2011
%Y See A138349 for another version.
%Y Cf. A000108, A006149, A006150, A248152.
%K nonn,walk,easy
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _James A. Sellers_, Dec 24 1999
%E Corrected by _Vladeta Jovovic_, May 23 2004
%E Better definition from _David Callan_, Sep 18 2007
%E Definition simplified by _N. J. A. Sloane_, Nov 30 2020
| 