%I #132 May 13 2022 18:41:32
%S 1,2,9,52,340,2394,17710,135720,1068012,8579560,70068713,580034052,
%T 4855986044,41043559340,349756577100,3001701610320,25921837477692,
%U 225083787458904,1963988670706228,17211860478150800,151433425446423120
%N a(n) = binomial(4*n+1,n)*2/(3*n+2).
%C This sequence counts the set B_n of plane trees defined in the Poulalhon and Schaeffer link (Definition 2.2 and Section 4.2, Proposition 4). - _David Callan_, Aug 20 2014
%C a(n) is the number of lattice paths of length 4n starting and ending on the x-axis consisting of steps {(1, 1), (1, -3)} that remain on or above the line y=-1. - _Sarah Selkirk_, Mar 31 2020
%C a(n) is the number of ordered pairs of 4-ary trees with a (summed) total of n internal nodes. - _Sarah Selkirk_, Mar 31 2020
%H Vincenzo Librandi, <a href="/A069271/b069271.txt">Table of n, a(n) for n = 0..100</a>
%H T. Anderson, T. B. McLean, H. Pajoohesh and C. Smith, <a href="https://doi.org/10.1016/j.ejc.2009.01.005">The combinatorics of all regular flexagons</a>, Eu. J. Combinat. 31 (2010) 72-80, Theorem 2.
%H Roland Bacher, <a href="http://arXiv.org/abs/0710.0960">Fair Triangulations</a>, arXiv:0710.0960 [math.CO], 2007.
%H Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%H Gi-Sang Cheon, S.-T. Jin and L. W. Shapiro, <a href="https://doi.org/10.1016/j.laa.2015.03.015">A combinatorial equivalence relation for formal power series</a>, Linear Algebra and its Applications, Volume 491, 15 February 2016, Pages 123-137.
%H Emmanuel Guitter, <a href="http://doi.org/10.4171/AIHPD/38">The distance-dependent two-point function of triangulations: a new derivation from old results</a>, Ann. Inst. Henri Poincaré Comb. Phys. Interact. Vol. 4 (2017), 177-211. DOI: 10.4171/AIHPD/38.
%H Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, <a href="https://arxiv.org/abs/2204.14023">Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k</a>, arXiv:2204.14023 [math.CO], 2022.
%H Ionut E. Iacob, T. Bruce McLean and Hua Wang, <a href="http://www.jstor.org/stable/10.4169/college.math.j.43.1.006">The V-flex, Triangle Orientation, and Catalan Numbers in Hexaflexagons</a>, The College Mathematics Journal, Vol. 43, No. 1 (January 2012), pp. 6-10.
%H J.-C. Novelli and J.-Y. Thibon, <a href="https://arxiv.org/abs/math/0512570">Noncommutative Symmetric Functions and Lagrange Inversion</a>, arXiv:math/0512570 [math.CO], 2005-2006.
%H C. O. Oakley and R. J. Wisner, <a href="https://doi.org/10.2307/2310544">Flexagons</a>, Am. Math. Monthly 64 (3) (1957) 143-154, u_{3k+2}.
%H Karol A. Penson and Karol Zyczkowski, <a href="http://arxiv.org/abs/1103.3453">Product of Ginibre matrices : Fuss-Catalan and Raney distribution</a>, arXiv:1103.3453 [math-ph], 2011.
%H Karol A. Penson and Karol Zyczkowski, <a href="http://dx.doi.org/10.1103/PhysRevE.83.061118">Product of Ginibre matrices : Fuss-Catalan and Raney distribution</a>, Phys. Rev. E 83, 061118, 2011.
%H Dominique Poulalhon and Gilles Schaeffer, <a href="http://www.lix.polytechnique.fr/~poulalho/Articles/PoSc_Algorithmica06.pdf">Optimal Coding and Sampling of Triangulations</a>, in Automata, Languages and Programming, Lecture Notes in Computer Science, Volume 2719, 2003, pp 1080-1094.
%H Sarah J. Selkirk, <a href="http://hdl.handle.net/10019.1/107091">On a generalisation of k-Dyck paths</a>, MSc Thesis, 2019.
%F a(n) = A069270(n+1, n) = A005810(n)*A016813(n)/A060544(n+1)
%F O.g.f. A(x) satisfies 2*x^2*A(x)^3 = 1-2*x*A(x)-sqrt(1-4*x*A(x)). - _Vladimir Kruchinin_, Feb 23 2011
%F a(n) is the sum of top row terms in M^n, where M is the infinite square production matrix with the triangular series in each column as follows, with the rest zeros:
%F 1, 1, 0, 0, 0, 0, ...
%F 3, 3, 1, 0, 0, 0, ...
%F 6, 6, 3, 1, 0, 0, ...
%F 10, 10, 6, 3, 1, 0, ...
%F 15, 15, 10, 6, 3, 1, ...
%F ... - _Gary W. Adamson_, Aug 11 2011
%F Given g.f. A(x) then B(x) = x * A(x^2) satisfies x = B(x) / (1 + B(x)^2)^2. - _Michael Somos_, Mar 28 2012
%F Given g.f. A(x) then A(x) = (1 + x * A(x)^2)^2. - _Michael Somos_, Mar 28 2012
%F a(n) / (n+1) = A000260(n). - _Michael Somos_, Mar 28 2012
%F REVERT transform is A115141. - _Michael Somos_, Mar 28 2012
%F D-finite with recurrence 3*n*(3*n+2)*(3*n+1)*a(n) - 8*(4*n+1)*(2*n-1)*(4*n-1)*a(n-1) = 0. - _R. J. Mathar_, Jun 07 2013
%F a(n) = 2*binomial(4n+1,n-1)/n for n>0, a(0)=1. - _Bruno Berselli_, Jan 19 2014
%F G.f.: hypergeom([1/2, 3/4, 5/4], [4/3, 5/3], (256/27)*x). - _Robert Israel_, Aug 24 2014
%F From _Peter Bala_, Oct 08 2015: (Start)
%F O.g.f. A(x) = (1/x) * series reversion (x/C(x)^2), where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. for the Catalan numbers A000108. Cf. A163456.
%F (1/2)*x*A'(x)/A(x) is the o.g.f. for A224274. (End)
%F E.g.f.: hypergeom([1/2, 3/4, 5/4], [1, 4/3, 5/3], (256/27)*x). - _Karol A. Penson_, Jun 26 2017
%F a(n) = binomial(4*n+2,n)/(2*n+1). - _Alexander Burstein_, Nov 08 2021
%e a(3) = C(4*3+1,3)*2/(3*3+2) = C(13,3)*2/11 = 286*2/11 = 52.
%e a(3) = 52 since the top row of M^3 = (22, 22, 7, 1).
%e 1 + 2*x + 9*x^2 + 52*x^3 + 340*x^4 + 2394*x^5 + 17710*x^6 + 135720*x^7 + ...
%e q + 2*q^3 + 9*q^5 + 52*q^7 + 340*q^9 + 2394*q^11 + 17710*q^13 + 135720*q^15 + ...
%p BB:=[T,{T=Prod(Z,Z,Z,F,F),F=Sequence(B),B=Prod(F,F,F,Z)}, unlabeled]: seq(count(BB,size=i),i=3..23); # _Zerinvary Lajos_, Apr 22 2007
%t f[n_] := 2 Binomial[4 n + 1, n]/(3 n + 2); Array[f, 21, 0] (* _Robert G. Wilson v_ *)
%o (PARI) a(n)=if(n<0,0,polcoeff(serreverse(x/(1+x^2)^2+O(x^(2*n+2))),2*n+1)) /* _Ralf Stephan_ */
%o (PARI) {a(n) = binomial(4*n + 2, n)*2 / (2*n + 1)} /* _Michael Somos_, Mar 28 2012 */
%o (PARI) {a(n) = local(A); if( n<0, 0, A = 1 + O(x); for( k=1, n, A = (1 + x * A^2)^2); polcoeff( A, n))} /* _Michael Somos_, Mar 28 2012 */
%o (Magma) [2*Binomial(4*n+1, n)/(3*n+2): n in [0..20]]; // _Bruno Berselli_, Mar 04 2011
%Y Cf. A002293, A006013, A006632, A069270 for similar generalized Catalan sequences.
%Y Cf. A000260, A115141, A163456, A224274.
%K nonn
%O 0,2
%A _Henry Bottomley_, Mar 12 2002