|
| |
|
|
A086581
|
|
Number of Dyck paths of semilength n with no DDUU.
|
|
5
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| G.f. A(x) satisfies the equation 0=1-x-(1-x)^2*A(x)+(xA(x))^2.
See A025242 for a bijection between paths avoiding UUDD versus DDUU.
|
|
|
REFERENCES
| T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
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.
|
|
|
LINKS
| T. Mansour, Restricted 1-3-2 permutations and generalized patterns.
|
|
|
FORMULA
| G.f.: (1-2x+x^2-sqrt(1-4x+2x^2+x^4))/(2x^2).
a(n+2)-2a(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 (pbarry(AT)wit.ie), May 31 2006
|
|
|
EXAMPLE
| a(4) = 13 because of the 14 Dyck 4-paths only UUDDUUDD contains DDUU.
|
|
|
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)
|
|
|
CROSSREFS
| a(n)=A025242(n+1)=A082582(n+1).
Sequence in context: A007689 A085281 A082582 * A059027 A025198 A037247
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
|
| |
|
|
