|
| |
|
|
A086581
|
|
Number of Dyck paths of semilength n with no DDUU.
|
|
10
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
P Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6
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.
|
|
|
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
|
| |
|
|
