This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A025242 Generalized Catalan numbers. 6
 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; text; 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, 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, Sep 25 2006 REFERENCES A. M. Baxter, L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014, http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf 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 and M. Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251; http://www.mat.unisi.it/newsito/puma/public_html/22_2/mansour_shattuck.pdf. - From N. J. A. Sloane, Oct 13 2012 T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.) L. Pudwell, A. Baxter, Ascent sequences avoiding pairs of patterns, http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf, 2014 A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924. LINKS Vincenzo Librandi, Table of n, a(n) for n = 1..1000 Yvan Le Borgne, Counting Upper Interactions in Dyck Paths, Seminaire Lotharingien de Combinatoire, Vol. 54, B54f (2006), 16 pp. V. Jelinek, T. Mansour, M. Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.1, without the leading 2. T. Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math.CO/0110039. L. Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015; http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf. 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. Conjecture: n*(n+1)*a(n) +(n^2+n+2)*a(n-1) +2*(-9*n^2+15*n+17)*a(n-2) +2*(5*n+4)*(n-4)*a(n-3) +(n+1)*(n-6)*a(n-4) +(5*n+4)*(n-7)*a(n-5)=0. - R. J. Mathar, Jan 12 2013 G.f.: 2 + x - x*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 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: A216396 A273488 A117848 * A163982 A246661 A246660 Adjacent sequences:  A025239 A025240 A025241 * A025243 A025244 A025245 KEYWORD nonn,easy AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 21 03:23 EDT 2019. Contains 321359 sequences. (Running on oeis4.)