1,1

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

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

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.)

T. Mansour, Restricted 1-3-2 permutations and generalized patterns.

Yvan Le Borgne, Counting Upper Interactions in Dyck Paths, Seminaire Lotharingien de Combinatoire, Vol. 54, B54f (2006), 16 pp.

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.

a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-1-k ], {k, 2, n-1} ];

(PARI) a(n)=polcoeff((1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4+x*O(x^n)))/2, n)

Cf. A000108, A001006, A006318, A004148, A007477, A082582.

Sequence in context: A159046 A029937 A117848 this_sequence A163982 A156588 A113186

Adjacent sequences: A025239 A025240 A025241 this_sequence A025243 A025244 A025245

nonn,easy

Clark Kimberling (ck6(AT)evansville.edu), Olivier Gerard (olivier.gerard(AT)gmail.com)