|
| |
|
|
A166300
|
|
Number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having no UUDD's starting at level 0.
|
|
6
|
|
|
|
1, 0, 0, 1, 1, 2, 5, 10, 22, 50, 113, 260, 605, 1418, 3350, 7967, 19055, 45810, 110637, 268301, 653066, 1594980, 3907395, 9599326, 23643751, 58374972, 144442170, 358136905, 889671937, 2214015802, 5518884019, 13778312440, 34448765740
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
COMMENTS
|
a(n) is the number of peakless Motzkin paths of length n with no (1,0)-steps at level 0. Example: a(5)=2 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have UHHHD and UUHDD. - Emeric Deutsch, May 03 2011
The Hankel transform of a(n+3) is A188444(n+1).
a(n+3) gives the diagonal sums of the triangle A100754.
a(n+3) has g.f. 1/(1-x-x^2/(1-2x+3x^2/(1+2x+x^2/(1-2x-(1/3)x^2/(1-x-(2/3)x^2/(1-2x+(5/2)x^2/(1+2x+(3/2)x^2/(1-...)))))))) (continued fraction) where the coefficients of x^2 have denominators A188442 and numerators A188443. (End)
The Ca1 triangle sums of triangle A175136 lead to this sequence (n>=3). For the definitions of the Ca1 and other triangle sums see A180662. - Johannes W. Meijer, May 06 2011
a(n) is the number of closed Deutsch paths of n steps with all peaks at even height. A Deutsch path is a lattice path of up-steps (1,1) and down-steps (1,-j), j>=1, starting at the origin that never goes below the x-axis, and it is closed if it ends on the x-axis. For example a(5) = 2 counts UUUU4, UU1U2, where U denotes an up-step and a down-step is denoted by its length, and a(6) = 5 counts UUUU13, UUUU22, UUUU31, UU1U11, UU2UU2. - David Callan, Dec 08 2021
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f. = G(z)=2/(1 + z + z^2 + sqrt((1 + z + z^2)*(1 - 3*z + z^2))).
G.f.: 1 / (1 - x^3 / (1 - x / (1 - x / (1 - x^3 / (1 - x / (1 - x / ...)))))). - Michael Somos, May 12 2012
G.f. A(x) satisfies A(x) = 1 / (1 - x^3 / (1 - x / (1 - x *A(x)))). - Michael Somos, May 12 2012
Conjecture: (n+1)*a(n) +2*(-n+1)*a(n-1) +(-n+1)*a(n-2) +2*(-n+1)*a(n-3) +(n-3)*a(n-4)=0. - R. J. Mathar, Nov 24 2012
a(n) ~ (3+sqrt(5))^(n+2) * sqrt(7*sqrt(5)-15) / (2 * sqrt(Pi) * n^(3/2) * 2^(n+9/2)). - Vaclav Kotesovec, Feb 12 2014. Equivalently, a(n) ~ 5^(1/4) * phi^(2*n + 2) / (8 * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021
a(n) = Sum_{j=0..n}((j+1)*Sum_{i=0..n-j}((binomial(j+2*i+1,i)*Sum_{k=0..n-j-2*i}(binomial(k,n-k-j-2*i)*binomial(k+j+2*i,k)*(-1)^(n-k)))/(j+2*i+1))). - Vladimir Kruchinin, Mar 07 2016
|
|
|
EXAMPLE
|
a(5)=2 because we have UUUDDUUDDD and UUUUUDDDDD.
G.f. = 1 + x^3 + x^4 + 2*x^5 + 5*x^6 + 10*x^7 + 22*x^8 + 50*x^9 + 113*x^10 + ...
|
|
|
MAPLE
|
G := 2/(1+z+z^2+sqrt((1+z+z^2)*(1-3*z+z^2))): Gser := series(G, z = 0, 35): seq(coeff(Gser, z, n), n = 0 .. 32);
|
|
|
MATHEMATICA
|
CoefficientList[Series[2/(1+x+x^2+Sqrt[(1+x+x^2)*(1-3*x+x^2)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)
|
|
|
PROG
|
(PARI) {a(n) = local(A); A = 1 + O(x); for( k=1, ceil(n / 5), A = 1 / (1 - x^3 / (1 - x / (1 - x * A)))); polcoeff( A, n)}; /* Michael Somos, May 12 2012 */
(PARI) x='x+O('x^40); Vec(2/(1+x+x^2+((1+x+x^2)*(1-3*x+x^2))^(1/2))) \\ Altug Alkan, Sep 23 2018
(Maxima)
a(n):=sum((j+1)*sum((binomial(j+2*i+1, i)*sum(binomial(k, n-k-j-2*i)*binomial(k+j+2*i, k)*(-1)^(n-k), k, 0, n-j-2*i))/(j+2*i+1), i, 0, n-j), j, 0, n); /* Vladimir Kruchinin, Mar 07 2016 */
(Magma) m:=40; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!(2/(1+x+x^2+Sqrt((1+x+x^2)*(1-3*x+x^2))))); // G. C. Greubel, Sep 22 2018
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
