login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 72

%I #118 Nov 22 2023 22:21:03

%S 1,2,10,66,498,4066,34970,312066,2862562,26824386,255680170,

%T 2471150402,24161357010,238552980386,2375085745978,23818652359682,

%U 240382621607874,2439561132029314,24881261270812490,254892699352950850

%N 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 These are the 3-Schroeder numbers according to Yang-Jiang (2021). - _N. J. A. Sloane_, Mar 28 2021

%C 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 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 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 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 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 Vincenzo Librandi, <a href="/A027307/b027307.txt">Table of n, a(n) for n = 0..200</a>

%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="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 Emeric Deutsch, <a href="http://www.jstor.org/stable/2589192">Problem 10658</a>, American Math. Monthly, 107, 2000, 368-370.

%H 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 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 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 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 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 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 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 G.f.: (2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3.

%F a(n) = (1/n) * Sum_{i=0..n-1} 2^(i+1)*binomial(2*n, i)*binomial(n, i+1)), n>0.

%F a(n) = 2*A034015(n-1), n>0.

%F 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 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 Series reversion of x(Sum_{k>=0} a(k)x^k) is x(Sum_{k>=0} A085403(k)x^k).

%F G.f. A(x) satisfies A(x)=A006318(x*A(x)). - _Vladimir Kruchinin_, Apr 18 2011

%F 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 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 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 a(n) = 2*hypergeom([1 - n, -2*n], [2], 2) for n >= 1. - _Peter Luschny_, Nov 08 2021

%F From _Peter Bala_, Jun 16 2023: (Start)

%F 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 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 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 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 a(2) = 10. Internal vertices colored either b(lack) or w(hite); 5 uncolored leaf vertices shown as o.

%e ........b...........b.............w...........w.....

%e ......./|\........./|\.........../|\........./|\....

%e ....../.|.\......./.|.\........./.|.\......./.|.\...

%e .....b..o..o.....o..b..o.......w..o..o.....o..w..o..

%e ..../|\............/|\......../|\............/|\....

%e .../.|.\........../.|.\....../.|.\........../.|.\...

%e ..o..o..o........o..o..o....o..o..o........o..o..o..

%e ....................................................

%e ........b...........b.............w...........w.....

%e ......./|\........./|\.........../|\........./|\....

%e ....../.|.\......./.|.\........./.|.\......./.|.\...

%e .....w..o..o.....o..w..o.......b..o..o.....o..b..o..

%e ..../|\............/|\......../|\............/|\....

%e .../.|.\........../.|.\....../.|.\........../.|.\...

%e ..o..o..o........o..o..o....o..o..o........o..o..o..

%e ....................................................

%e ........b...........w..........

%e ......./|\........./|\.........

%e ....../.|.\......./.|.\........

%e .....o..o..w.....o..o..b.......

%e ........../|\........./|\......

%e ........./.|.\......./.|.\.....

%e ........o..o..o.....o..o..o....

%e ...............................

%t a[n_] := ((n+1)*(2n)!*Hypergeometric2F1[-n, 2n+1, n+2, -1]) / (n+1)!^2;

%t Table[a[n], {n, 0, 19}] (* _Jean-François Alcover_, Nov 14 2011, after Pari *)

%t a[n_] := If[n == 0, 1, 2*Hypergeometric2F1[1 - n, -2 n, 2, 2]];

%t Table[a[n], {n, 0, 19}] (* _Peter Luschny_, Nov 08 2021 *)

%o (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 (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 (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 Cf. A104978. A196201.

%Y 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 Apart from first term, this is 2*A034015. - _N. J. A. Sloane_, Mar 28 2021

%K nonn,easy

%O 0,2

%A _Emeric Deutsch_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:55 EDT 2024. Contains 371241 sequences. (Running on oeis4.)