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!)
A128720 Number of paths in the first quadrant from (0,0) to (n,0) using steps U=(1,1), D=(1,-1), h=(1,0) and H=(2,0). 18
1, 1, 3, 6, 16, 40, 109, 297, 836, 2377, 6869, 20042, 59071, 175453, 524881, 1579752, 4780656, 14536878, 44394980, 136107872, 418757483, 1292505121, 4001039563, 12418772656, 38641790001, 120510911885, 376628460529, 1179376013552, 3699860515924, 11626784875214 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Points of two kinds are placed on a line: light points having weight 1 and heavy points having weight 2. Number of configurations of points of total weight n, with some of the light points being paired off by nonintersecting arcs.
Number of skew Dyck paths of semilength n having no UUU's. A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of its steps. Example: a(3)=6 because we have UDUDUD, UDUUDD, UDUUDL, UUDDUD, UUDUDD and UUDUDL. a(n)=A128719(n,0). a(n)=A059397(n,n). a(n)=A132276(n,0).
Hankel transform is the (1,3) Somos-4 sequence A174168. - Paul Barry, Mar 10 2010
First column of the Riordan matrix A132276. - Emanuele Munarini, May 05 2011
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000 (first 101 terms from Vincenzo Librandi)
Paul Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, arXiv:1107.5490 [math.CO], 2011.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
E. Deutsch, E. Munarini, and S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, A Pascal rhombus, Fibonacci Quarterly, 35 (1997), 318-328.
P. Rajkovic, P. Barry, and N. Savic, Number Sequences in an Integral Form with a Generalized Convolution Property and Somos-4 Hankel Determinants, Math. Balkanica, Vol. 26 (2012), Fasc. 1-2.
FORMULA
a(n) = Sum_{j=0..floor(n/2)} binomial(n-j, j)*m(n-2j), where m(k)=A001006(k) are the Motzkin numbers.
G.f. = G satisfies z^2*G^2 - (1-z-z^2)*G + 1 = 0.
G.f. = c(z^2/(1-z-z^2)^2)/(1-z-z^2), where c(z) = (1-sqrt(1-4z))/(2z) is the Catalan function.
a(n) = a(n-1) + a(n-2) + Sum_{j=0..n-2} a(j)*a(n-2-j), a(0) = a(1) = 1.
G.f.: (1/(1-x-x^2))*c(x^2/(1-x-x^2)^2) = (1/(1-x^2))*m(x/(1-x^2)), c(x) the g.f. of A000108, m(x) the g.f. of A001006. - Paul Barry, Mar 18 2010
Let A(x) be the g.f., then B(x) = 1 + x*A(x) = 1 + 1*x + 1*x^2 + 3*x^3 + 6*x^4 + ... = 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1+x-x^2) (continued fraction); more generally B(x)=C(x/(1+x-x^2)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011
a(n) = Sum_{k=0..floor(n/2)} (binomial(2*k,k)/(k+1))*Sum_{j=0..floor(n/2)} binomial(n-j, 2*k)*binomial(n-j-2*k, j). - Emanuele Munarini, May 05 2011
D-finite with recurrence: (n+2)*a(n) + (-2*n-1)*a(n-1) + 5*(-n+1)*a(n-2) + (2*n-5)*a(n-3) + (n-4)*a(n-4) = 0. - R. J. Mathar, Dec 03 2012
G.f.: (1 - x - x^2 - sqrt(1 - 2*x - 5*x^2 + 2*x^3 + x^4))/(2*x^2) = 1/Q(0), where Q(k) = 1 - x - x^2 - x^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 04 2013
a(n) ~ sqrt(78+22*sqrt(13)) * ((3+sqrt(13))/2)^n / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 13 2014
EXAMPLE
a(3)=6 because we have hhh, hH, Hh, hUD, UhD and UDh.
G.f. = 1 + x + 3*x^2 + 6*x^3 + 16*x^4 + 40*x^5 + 109*x^6 + 297*x^7 + ...
MAPLE
a[0]:=1: a[1]:=1: for n from 2 to 30 do a[n]:=a[n-1]+a[n-2]+add(a[j]*a[n-2-j], j=0..n-2) end do: seq(a[n], n=0..30); G:=((1-z-z^2-sqrt((1+z-z^2)*(1-3*z-z^2)))*1/2)/z^2: Gser:=series(G, z=0, 33): seq(coeff(Gser, z, n), n=0..30);
MATHEMATICA
Table[Sum[Binomial[2k, k]/(k+1)Sum[Binomial[n-j, 2k]Binomial[n-j-2k, j], {j, 0, n/2}], {k, 0, n/2}], {n, 0, 12}] (* Emanuele Munarini, May 05 2011 *)
PROG
(Maxima) makelist(sum(binomial(2*k, k)/(k+1)*sum(binomial(n-j, 2*k)*binomial(n-j-2*k, j), j, 0, n/2), k, 0, n/2), n, 0, 12); // Emanuele Munarini, May 05 2011
CROSSREFS
Sequence in context: A301959 A018022 A166536 * A096745 A293949 A027088
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Mar 30 2007, revised Sep 03 2007
STATUS
approved

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 February 21 03:52 EST 2024. Contains 370219 sequences. (Running on oeis4.)