login
Number of steps in all Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1),H=(2,0) and never going below the x-axis) from (0,0) to (2n,0).
1

%I #23 Jul 29 2017 03:50:49

%S 3,19,107,591,3259,18019,99987,556831,3111347,17436915,97981179,

%T 551871087,3114878571,17613879747,99768824355,565962587199,

%U 3214923140707,18284737574611,104110467624075,593397580894351

%N Number of steps in all Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1),H=(2,0) and never going below the x-axis) from (0,0) to (2n,0).

%H Vincenzo Librandi, <a href="/A089164/b089164.txt">Table of n, a(n) for n = 1..200</a>

%F a(n) = (1/n) * Sum_{k=n..2*n} k*C(n, k-n)*C(k, n-1).

%F G.f.: 1/2 - 1/z + (2-7*z+z^2)/(2*z*sqrt(1-6*z+z^2)).

%F Recurrence: 2*(n+1)*(41*n-33)*a(n) = 3*(164*n^2-27*n+11)*a(n-1) - 2*(41*n^2+174*n-374)*a(n-2) + 69*(n-3)*a(n-3). - _Vaclav Kotesovec_, Oct 14 2012

%F a(n) ~ sqrt(48+34*sqrt(2))*(3+2*sqrt(2))^n/(4*sqrt(Pi*n)). - _Vaclav Kotesovec_, Oct 14 2012

%e a(2)=19 because the six Schroeder paths HH,HUD,UDH,UHD,UDUD,UUDD from (0,0) to (4,0) have 19 steps (i.e., letters) altogether.

%t f[n_] := Sum[k* Binomial[n, k - n] Binomial[k, n - 1], {k, n, 2 n}] /n; Array[f, 20] (* Or *)

%t Rest@ CoefficientList[ Series[(x - 2 + (2 - 7 x + x^2)/(Sqrt[1 - 6 x + x^2]))/(2 x), {x, 0, 20}], x] (* _Robert G. Wilson v_, Sep 12 2011 *)

%o (PARI) x='x+O('x^66); Vec(1/2-1/x+(2-7*x+x^2)/(2*x*sqrt(1-6*x+x^2))) \\ _Joerg Arndt_, May 10 2013

%Y Cf. A006318.

%K nonn

%O 1,1

%A _Emeric Deutsch_, Dec 06 2003