|
| |
|
|
A025242
|
|
Generalized Catalan numbers.
|
|
4
| |
|
|
2, 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
| 1,1
|
|
|
COMMENTS
| Number of Dyck paths of semilength n-1 with no UUDD (n>1). Example: a(4)=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
a(n ) = number of Dyck (n-2)-paths with no DDUU (n>2). Example: a(6)=13 counts all 14 Dyck 4-paths except UUDDUUDD which contains a DDUU. There is a simple bijective proof: given a Dyck path that avoids DDUU, for every occurrence of UUDD except the first, the ascent containing this UU must be immediately preceded by a UD (else a DDUU would be present). Transfer the latter UD to the middle of the DD in the UUDD. Then insert a new UD in the middle of the first DD if any; if not, the path is a sawtooth UDUD...UD, in which case insert a UD at the end. This is a bijection from DDUU-avoiding Dyck n-paths to UUDD-avoiding Dyck (n+1)-paths. - David Callan (callan(AT)stat.wisc.edu), Sep 25 2006
|
|
|
REFERENCES
| N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
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, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
|
|
|
LINKS
| Yvan Le Borgne, Counting Upper Interactions in Dyck Paths, Seminaire Lotharingien de Combinatoire, Vol. 54, B54f (2006), 16 pp.
T. Mansour, Restricted 1-3-2 permutations and generalized patterns.
|
|
|
FORMULA
| a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ...+ a(n-3)*a(3) for n >= 4.
G.f.: (1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4))/2 - Michael Somos, Jun 08, 2000.
|
|
|
MATHEMATICA
| a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-1-k ], {k, 2, n-1} ];
|
|
|
PROG
| (PARI) a(n)=polcoeff((1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4+x*O(x^n)))/2, n)
|
|
|
CROSSREFS
| Cf. A000108, A001006, A006318, A004148, A007477, A082582, A086581.
Sequence in context: A159046 A029937 A117848 * A163982 A156588 A113186
Adjacent sequences: A025239 A025240 A025241 * A025243 A025244 A025245
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| Clark Kimberling (ck6(AT)evansville.edu), Olivier Gerard (olivier.gerard(AT)gmail.com)
|
| |
|
|
