cp's OEIS Frontend

A027307 Number of paths from (0,0) to (3n,0) that stay in first quadrant (but may touch horizontal axis) and where each step is (2,1), (1,2) or (1,-1).

%I A027307 #131 Feb 23 2025 11:25:23
%S A027307 1,2,10,66,498,4066,34970,312066,2862562,26824386,255680170,
%T A027307 2471150402,24161357010,238552980386,2375085745978,23818652359682,
%U A027307 240382621607874,2439561132029314,24881261270812490,254892699352950850
%N A027307 Number of paths from (0,0) to (3n,0) that stay in first quadrant (but may touch horizontal axis) and where each step is (2,1), (1,2) or (1,-1).
%C A027307 These are the 3-Schroeder numbers according to Yang-Jiang (2021). - _N. J. A. Sloane_, Mar 28 2021
%C A027307 Equals row sums of triangle A104978 which has g.f. F(x,y) that satisfies: F = 1 + x*F^2 + x*y*F^3. - _Paul D. Hanna_, Mar 30 2005
%C A027307 a(n) counts ordered complete ternary trees with 2*n + 1 leaves, where the internal vertices come in two colors and such that each vertex and its rightmost child have different colors. See [Drake, Example 1.6.9]. An example is given below. - _Peter Bala_, Sep 29 2011
%C A027307 a(n) for n >= 1 is the number of compact coalescent histories for matching lodgepole gene trees and species trees with n cherries and 2n+1 leaves. - _Noah A Rosenberg_, Jun 21 2022
%C A027307 a(n) is the maximum number of distinct sets that can be obtained as complete parenthesizations of “S_1 union S_2 intersect S_3 union S_4 intersect S_5 union ... union S_{2*n} intersect S_{2*n+1}”, where n union and n intersection operations alternate, starting with a union, and S_1, S_2, ... , S_{2*n+1} are sets. - _Alexander Burstein_, Nov 22 2023
%D A027307 Sheng-Liang Yang and Mei-yang Jiang, The m-Schröder paths and m-Schröder numbers, Disc. Math. (2021) Vol. 344, Issue 2, 112209. doi:10.1016/j.disc.2020.112209. See Table 1.
%H A027307 Vincenzo Librandi, <a href="/A027307/b027307.txt">Table of n, a(n) for n = 0..200</a>
%H A027307 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 A027307 Gi-Sang Cheon, S.-T. Jin and L. W. Shapiro, <a href="http://dx.doi.org/10.1016/j.laa.2015.03.015">A combinatorial equivalence relation for formal power series</a>, Linear Algebra and its Applications, Available online 30 March 2015.
%H A027307 Emeric Deutsch, <a href="http://www.jstor.org/stable/2589192">Problem 10658</a>, American Math. Monthly, 107, 2000, 368-370.
%H A027307 F. Disanto and N. A. Rosenberg, <a href="https://doi.org/10.1007/s00285-018-1271-5">Enumeration of compact coalescent histories for matching gene trees and species trees</a>, J. Math. Biol 78 (2019), 155-188.
%H A027307 B. Drake, <a href="http://people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf">An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.6.9)</a>, A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
%H A027307 Elżbieta Liszewska and Wojciech Młotkowski, <a href="https://arxiv.org/abs/1907.10725">Some relatives of the Catalan sequence</a>, arXiv:1907.10725 [math.CO], 2019.
%H A027307 Zhen-ji Tian and Shu-ping Dou, <a href="https://journal.lut.edu.cn/EN/abstract/abstract771.shtml">Enumerations of 3 di-sk trees</a>, J. Lanzhou Univ. Tech. (2024) Vol. 50, No. 6, 144-149. See p. 146.
%H A027307 J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, <a href="https://ir.cwi.nl/pub/21313">Context-free coalgebras</a>, 2013.
%H A027307 Jun Yan, <a href="https://arxiv.org/abs/2501.01152">Lattice paths enumerations weighted by ascent lengths</a>, arXiv:2501.01152 [math.CO], 2025. See p. 11.
%H A027307 Sheng-liang Yang and Mei-yang Jiang, <a href="https://journal.lut.edu.cn/EN/abstract/abstract528.shtml">Pattern avoiding problems on the hybrid d-trees</a>, J. Lanzhou Univ. Tech., (China, 2023) Vol. 49, No. 2, 144-150. (in Mandarin)
%H A027307 Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, <a href="https://arxiv.org/abs/1706.03357">Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing</a>, arXiv:1706.03357 [cs.CL], 2017.
%H A027307 Jian Zhou, <a href="https://arxiv.org/abs/2108.10514">On Some Mathematics Related to the Interpolating Statistics</a>, arXiv:2108.10514 [math-ph], 2021.
%F A027307 G.f.: (2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3.
%F A027307 a(n) = (1/n) * Sum_{i=0..n-1} 2^(i+1)*binomial(2*n, i)*binomial(n, i+1), n>0.
%F A027307 a(n) = 2*A034015(n-1), n>0.
%F A027307 a(n) = Sum_{k=0..n} C(2*n+k, n+2*k)*C(n+2*k, k)/(n+k+1). - _Paul D. Hanna_, Mar 30 2005
%F A027307 Given g.f. A(x), y=A(x)x satisfies 0=f(x, y) where f(x, y)=x(x-y)+(x+y)y^2 . - _Michael Somos_, May 23 2005
%F A027307 Series reversion of x(Sum_{k>=0} a(k)x^k) is x(Sum_{k>=0} A085403(k)x^k).
%F A027307 G.f. A(x) satisfies A(x)=A006318(x*A(x)). - _Vladimir Kruchinin_, Apr 18 2011
%F A027307 The function B(x) = x*A(x^2) satisfies B(x) = x+x*B(x)^2+B(x)^3 and hence B(x) = compositional inverse of x*(1-x^2)/(1+x^2) = x+2*x^3+10*x^5+66*x^7+.... Let f(x) = (1+x^2)^2/(1-4*x^2+x^4) and let D be the operator f(x)*d/dx. Then a(n) equals 1/(2*n+1)!*D^(2*n)(f(x)) evaluated at x = 0. For a refinement of this sequence see A196201. - _Peter Bala_, Sep 29 2011
%F A027307 D-finite with recurrence: 2*n*(2*n+1)*a(n) = (46*n^2-49*n+12)*a(n-1) - 3*(6*n^2-26*n+27)*a(n-2) - (n-3)*(2*n-5)*a(n-3). - _Vaclav Kotesovec_, Oct 08 2012
%F A027307 a(n) ~ sqrt(50+30*sqrt(5))*((11+5*sqrt(5))/2)^n/(20*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 08 2012. Equivalently, a(n) ~ phi^(5*n + 1) / (2 * 5^(1/4) * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, Dec 07 2021
%F A027307 a(n) = 2*hypergeom([1 - n, -2*n], [2], 2) for n >= 1. - _Peter Luschny_, Nov 08 2021
%F A027307 From _Peter Bala_, Jun 16 2023: (Start)
%F A027307 P-recursive: n*(2*n + 1)*(5*n - 7)*a(n) = (110*n^3 - 264*n^2 + 181*n - 36)*a(n-1) + (n - 2)*(2*n - 3)*(5*n - 2)*a(n-2) with a(0) = 1 and a(1) = 2.
%F A027307 The g.f. A(x) = 1 + 2*x + 10*x^2 + 66*x^3 + ... satisfies A(x)^2 = (1/x) * the series reversion of x*((1 - x)/(1 + x))^2.
%F A027307 Define b(n) = [x^(2*n)] ( (1 + x)/(1 - x) )^n = (1/2) * [x^n] ((1 + x)/(1 - x))^(2*n) = A103885(n). Then A(x) = exp( Sum_{n >= 1} b(n)*x^n/n ). (End)
%F A027307 a(n) = (1/n) * Sum_{k=0..n-1} (-1)^k * 2^(n-k) * binomial(n,k) * binomial(3*n-k,n-1-k) for n > 0. - _Seiichi Manyama_, Aug 09 2023
%e A027307 a(2) = 10. Internal vertices colored either b(lack) or w(hite); 5 uncolored leaf vertices shown as o.
%e A027307 ........b...........b.............w...........w.....
%e A027307 ......./|\........./|\.........../|\........./|\....
%e A027307 ....../.|.\......./.|.\........./.|.\......./.|.\...
%e A027307 .....b..o..o.....o..b..o.......w..o..o.....o..w..o..
%e A027307 ..../|\............/|\......../|\............/|\....
%e A027307 .../.|.\........../.|.\....../.|.\........../.|.\...
%e A027307 ..o..o..o........o..o..o....o..o..o........o..o..o..
%e A027307 ....................................................
%e A027307 ........b...........b.............w...........w.....
%e A027307 ......./|\........./|\.........../|\........./|\....
%e A027307 ....../.|.\......./.|.\........./.|.\......./.|.\...
%e A027307 .....w..o..o.....o..w..o.......b..o..o.....o..b..o..
%e A027307 ..../|\............/|\......../|\............/|\....
%e A027307 .../.|.\........../.|.\....../.|.\........../.|.\...
%e A027307 ..o..o..o........o..o..o....o..o..o........o..o..o..
%e A027307 ....................................................
%e A027307 ........b...........w..........
%e A027307 ......./|\........./|\.........
%e A027307 ....../.|.\......./.|.\........
%e A027307 .....o..o..w.....o..o..b.......
%e A027307 ........../|\........./|\......
%e A027307 ........./.|.\......./.|.\.....
%e A027307 ........o..o..o.....o..o..o....
%e A027307 ...............................
%e A027307 From _Alexander Burstein_, Feb 14 2025: (Start)
%e A027307 a(2) = 10 as the maximum number of distinct sets obtained as complete parenthesizations of S_1 u(nion) S_2 (i)n(tersect) S_3 u(nion) S_4 (i)n(tersect) S_5:
%e A027307 S_1 u (S_2 n (S_3 u (S_4 n S_5))),
%e A027307 S_1 u (S_2 n ((S_3 u S_4) n S_5)) = S_1 u ((S_2 n (S_3 u S_4)) n S_5),
%e A027307 S_1 u ((S_2 n S_3) u (S_4 n S_5)) = (S_1 u (S_2 n S_3)) u (S_4 n S_5),
%e A027307 S_1 u (((S_2 n S_3) u S_4) n S_5),
%e A027307 (S_1 u S_2) n (S_3 u (S_4 n S_5)),
%e A027307 (S_1 u S_2) n ((S_3 u S_4) n S_5) = ((S_1 u S_2) n (S_3 u S_4)) n S_5,
%e A027307 ((S_1 u S_2) n S_3) u (S_4 n S_5),
%e A027307 (S_1 u (S_2 n (S_3 u S_4))) n S_5,
%e A027307 (S_1 u ((S_2 n S_3) u S_4)) n S_5 = ((S_1 u (S_2 n S_3)) u S_4) n S_5,
%e A027307 (((S_1 u S_2) n S_3) u S_4) n S_5. (End)
%t A027307 a[n_] := ((n+1)*(2n)!*Hypergeometric2F1[-n, 2n+1, n+2, -1]) / (n+1)!^2;
%t A027307 Table[a[n], {n, 0, 19}] (* _Jean-François Alcover_, Nov 14 2011, after Pari *)
%t A027307 a[n_] := If[n == 0, 1, 2*Hypergeometric2F1[1 - n, -2 n, 2, 2]];
%t A027307 Table[a[n], {n, 0, 19}]  (* _Peter Luschny_, Nov 08 2021 *)
%o A027307 (PARI) a(n)=if(n<1,n==0,sum(i=0,n-1,2^(i+1)*binomial(2*n,i)*binomial(n,i+1))/n)
%o A027307 (PARI) a(n)=sum(k=0,n,binomial(2*n+k,n+2*k)*binomial(n+2*k,k)/(n+k+1)) \\ _Paul D. Hanna_
%o A027307 (PARI) a(n)=sum(k=0,n, binomial(n,k)*binomial(2*n+k+1,n)/(2*n+k+1) ) /* _Michael Somos_, May 23 2005 */
%Y A027307 Cf. A104978. A196201.
%Y A027307 The sequences listed in Yang-Jiang's Table 1 appear to be A006318, A001003, A027307, A034015, A144097, A243675, A260332, A243676. - _N. J. A. Sloane_, Mar 28 2021
%Y A027307 Apart from first term, this is 2*A034015. - _N. J. A. Sloane_, Mar 28 2021
%K A027307 nonn,easy
%O A027307 0,2
%A A027307 _Emeric Deutsch_