|
Search: id:A086581
|
|
|
| A086581 |
|
Number of Dyck paths of semilength n with no UUDD. |
|
+0
4
|
|
| 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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
G.f. A(x) satisfies the equation 0=1-x-(1-x)^2*A(x)+(xA(x))^2.
|
|
REFERENCES
|
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
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.
|
|
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)C(k)}; - Paul Barry (pbarry(AT)wit.ie), May 31 2006
|
|
EXAMPLE
|
a(3)=2 because the only Dyck paths of semilength 3 with no UUDD in them are UDUDUD and UUDUDD (the nonqualifying ones being UDUUDD, UUDDUD, and UUUDDD). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 27 2003
|
|
PROGRAM
|
(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 this_sequence A059027 A025198 A037247
Adjacent sequences: A086578 A086579 A086580 this_sequence A086582 A086583 A086584
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Michael Somos, Jul 22 2003
|
|
|
Search completed in 0.002 seconds
|
