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

Author

Michael Somos, Jul 22 2003

Keywords

• nonn

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

Examples

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

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.

Crossrefs

Cf. A025242, A082582.

Column k=0 of A114492.

Programs

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 *)

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

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

From Thomas Baruchel, Jan 19 2015: (Start)

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).

a(n) = Sum_{k=0..n} C(2k,k)*C(n+k,3k)/(k+1).

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). (End)

Extensions

Name corrected by David Scambler, Mar 28 2011