cp's OEIS Frontend

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

%I A086581 #80 Aug 24 2024 20:38:06
%S A086581 1,1,2,5,13,35,97,275,794,2327,6905,20705,62642,190987,586219,1810011,
%T A086581 5617914,17518463,54857506,172431935,543861219,1720737981,5459867166,
%U A086581 17369553427,55391735455,177040109419,567019562429,1819536774089
%N A086581 Number of Dyck paths of semilength n with no DDUU.
%C A086581 See A025242 for a bijection between paths avoiding UUDD versus DDUU.
%C A086581 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
%C A086581 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
%H A086581 Robert Israel, <a href="/A086581/b086581.txt">Table of n, a(n) for n = 0..1709</a>
%H A086581 Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry3/barry93.html">Continued fractions and transformations of integer sequences</a>, JIS 12 (2009) 09.7.6.
%H A086581 Paul Barry, <a href="https://arxiv.org/abs/1910.00875">Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials</a>, arXiv:1910.00875 [math.CO], 2019.
%H A086581 Lu, Qing Lin <a href="https://doi.org/10.1007/s10114-016-5292-y">Skew Motzkin paths</a> Acta Math. Sin., Engl. Ser. 33, No. 5, 657-667 (2017) sequence s_n
%H A086581 T. Mansour, <a href="http://arXiv.org/abs/math.CO/0110039">Restricted 1-3-2 permutations and generalized patterns</a>, arXiv:math/0110039 [math.CO], 2001.
%H A086581 T. Mansour, <a href="http://dx.doi.org/10.1007/s00026-002-8031-2">Restricted 1-3-2 permutations and generalized patterns</a>, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
%H A086581 L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a> (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013
%H A086581 A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Tsikouras/tsikouras67.html">On the Dominance Partial Ordering of Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
%H A086581 A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%H A086581 Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.
%F A086581 G.f. A(x) satisfies the equation 0 = 1 - x - (1 - x)^2 * A(x) + (x * A(x))^2.
%F A086581 a(n) = A025242(n+1) = A082582(n+1).
%F A086581 G.f.: (1 - 2*x + x^2 - sqrt(1 - 4*x + 2*x^2 + x^4))  /(2 * x^2).
%F A086581 a(n+2) - 2*a(n+1) + a(n) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0).
%F A086581 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
%F A086581 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
%F A086581 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
%F A086581 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
%F A086581 G.f.: 1/G(0) where G(k) = 1 - q/(1 - q - q^2 / G(k+1) ); (continued fraction). - _Joerg Arndt_, Feb 27 2014
%F A086581 From _Thomas Baruchel_, Jan 19 2015: (Start)
%F A086581 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).
%F A086581 a(n) = Sum_{k=0..n} C(2k,k)*C(n+k,3k)/(k+1).
%F A086581 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)
%e A086581 a(4) = 13 because of the 14 Dyck 4-paths only UUDDUUDD contains DDUU.
%p A086581 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):
%p A086581 map(F, [$0..30]); # _Robert Israel_, Jun 29 2015
%t A086581 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 *)
%o A086581 (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)}
%o A086581 (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
%Y A086581 Cf. A025242, A082582.
%Y A086581 Column k=0 of A114492.
%K A086581 nonn
%O A086581 0,3
%A A086581 _Michael Somos_, Jul 22 2003
%E A086581 Name corrected by _David Scambler_, Mar 28 2011