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.
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)
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
KEYWORD
nonn
AUTHOR
Michael Somos, Jul 22 2003
EXTENSIONS
Name corrected by David Scambler, Mar 28 2011
STATUS
approved