A086581 Number of Dyck paths of semilength n with no DDUU.

1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089

Offset

0,3

Comments

See A025242 for a bijection between paths avoiding UUDD versus DDUU.

Number of lattice paths, never going below the x-axis, from (0,0) to (n,0) consisting of up steps U(k) = (k,1) for every positive integer k, down steps D = (1,-1) and horizontal steps H. - José Luis Ramírez Ramírez, Apr 19 2015

Given a sequence variant with 0 inserted between the two 1's, the INVERT transform of the modified sequence is this sequence. - Gary W. Adamson, Jun 28 2015

Links

Robert Israel, Table of n, a(n) for n = 0..1709

Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.

Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.

Lu, Qing Lin Skew Motzkin paths Acta Math. Sin., Engl. Ser. 33, No. 5, 657-667 (2017) sequence s_n

T. Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.

T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)

L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From N. J. A. Sloane, Jan 03 2013

A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Formula

G.f. A(x) satisfies the equation 0 = 1 - x - (1 - x)^2 * A(x) + (x * A(x))^2.

a(n) = A025242(n+1) = A082582(n+1).

G.f.: (1 - 2*x + x^2 - sqrt(1 - 4*x + 2*x^2 + x^4)) /(2 * x^2).

a(n+2) - 2*a(n+1) + a(n) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0).

G.f.: (1/(1-x))*c(x^2/(1-x)^3), c(x) the g.f. of A000108; a(n)=sum{k=0..floor(n/2), C(n+k,3k)*A000108(k)}. - Paul Barry, May 31 2006

Conjecture: (n+2)*a(n) +(n+3)*a(n-1) +2*(-9*n+4)*a(n-2) +10*(n-2)*a(n-3) +(n-4)*a(n-4) +5*(n-5)*a(n-5)=0. - R. J. Mathar, Nov 26 2012

G.f. satisfies (10*x^3-28*x^2+4*x+2)*A(x) + (5*x^6+x^5+10*x^4-18*x^3+x^2+x)*A'(x) = 5*x^4+x^3-15*x^2+7*x+2. This confirms R. J. Mathar's recurrence equation. - Robert Israel, Jun 29 2015

G.f.: 1 - G(0), where G(k)= 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013

G.f.: 1/G(0) where G(k) = 1 - q/(1 - q - q^2 / G(k+1) ); (continued fraction). - Joerg Arndt, Feb 27 2014

a(n) = 1+sum(k=0..n, sum(i=0..k, C(n-1,k)*C(2i+2,i)*C(i+2,k-2i-1)/(i+1))). - Thomas Baruchel, Jan 19 2015

a(n) = sum(k=0..n, C(2k,k) C(n+k,3k) / (k+1). - Thomas Baruchel, Jan 19 2015

sum(k=0..n, a(k+1) * A108626(n-k)) = sum(k=0..n, sum(i=0..k, binomial(n-k+1,i-1)*binomial(n-k+1,i)*binomial(n-i+1,k-i))). - Thomas Baruchel, Jan 19 2015

Example

a(4) = 13 because of the 14 Dyck 4-paths only UUDDUUDD contains DDUU.

Maple

F:= gfun:-rectoproc({(n+2)*a(n) +(n+3)*a(n-1) +2*(-9*n+4)*a(n-2) +10*(n-2)*a(n-3) +(n-4)*a(n-4) +5*(n-5)*a(n-5)=0, seq(a(n)=[1, 1, 2, 5, 13][n+1], n=0..4)}, a(n), remember):
map(F, [$0..30]); # Robert Israel, Jun 29 2015

Mathematica

CoefficientList[ Series[(1 - 2 x + x^2 - Sqrt[1 - 4 x + 2 x^2 + x^4])/(2 x^2), {x, 0, 27}], x] (* Robert G. Wilson v, Mar 25 2011 *)

Prog

(PARI) {a(n) = polcoeff((1 - 2*x + x^2 - sqrt(1 - 4*x + 2*x^2 + x^4 + x^3 * O(x^n))) / 2, n+2)}
(PARI) a(n)=1+sum(k=0, n, sum(i=0, k, binomial(n-1, k)*binomial(2*i+2, i)*binomial(i+2, k-2*i-1)/(i+1))) \\ Thomas Baruchel, Jan 19 2015

Crossrefs

Cf. A025242, A082582.

Column k=0 of A114492.

Sequence in context: A007689 A085281 A082582 * A059027 A025198 A221205

Adjacent sequences: A086578 A086579 A086580 * A086582 A086583 A086584

Keyword

nonn

Author

Michael Somos, Jul 22 2003

Extensions

Name corrected by David Scambler, Mar 28 2011

Status

approved