|
| |
|
|
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).
|
|
14
| |
|
|
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
(list; graph; refs; listen; history; 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. [From Paul Barry (pbarry(AT)wit.ie), Mar 10 2010]
First column of the Riordan matrix A132276. [Emanuele Munarini, May 5 2011]
|
|
|
REFERENCES
| P. Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, Arxiv preprint arXiv:1107.5490, 2011.
W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, A Pascal rhombus, Fibonacci Quarterly, 35 (1997), 318-328.
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 0..100
E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203
|
|
|
FORMULA
| a(n)=Sum(binom(n-j, j)*m(n-2j), j=0..floor(n/2)), 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. Rec. rel.: a(n)=a(n-1)+a(n-2)+Sum(a(j)a(n-2-j), j=0..n-2); 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. [From Paul Barry (pbarry(AT)wit.ie), 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(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). [Emanuele Munarini, May 5 2011]
|
|
|
EXAMPLE
| a(3)=6 because we have hhh, hH, Hh, hUD, UhD and UDh.
|
|
|
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 5 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 5 2011]
|
|
|
CROSSREFS
| Cf. A001006, A128719, A059397, A132276.
Sequence in context: A205770 A018022 A166536 * A096745 A027088 A027102
Adjacent sequences: A128717 A128718 A128719 * A128721 A128722 A128723
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 30 2007, revised Sep 03 2007
|
| |
|
|
