login
This site is supported by donations 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). 53

%I

%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 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

%H Vincenzo Librandi, <a href="/A027307/b027307.txt">Table of n, a(n) for n = 0..200</a>

%H Gi-Sang Cheon, S.-T. Jin, 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 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 J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, <a href="http://oai.cwi.nl/oai/asset/21313/21313A.pdf">Context-free coalgebras</a>, 2013.

%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.

%F G.f.: (2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3. a(n)=(Sum_{i=0..n-1} 2^(i+1)*binomial(2*n, i)*binomial(n, i+1))/n, 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 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

%e a(3) = 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; Table[a[n], {n, 0, 19}] (* _Jean-François Alcover_, Nov 14 2011, after Pari *)

%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.

%K nonn

%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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 16 18:45 EDT 2019. Contains 327117 sequences. (Running on oeis4.)