|
| |
|
|
A025242
|
|
Generalized Catalan numbers.
|
|
7
|
|
|
|
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) is the 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
For n>1, a(n) is the number of cyclic permutations of [n-1] that avoid the vincular pattern 13-4-2, i.e., the pattern 1342 where the 1 and 3 must be adjacent. By the trivial Wilf equivalence, the same applies for 24-3-1, 31-2-4, and 42-1-3. - Rupert Li, Jul 27 2021
|
|
|
LINKS
|
Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Yvan Le Borgne, Counting Upper Interactions in Dyck Paths, Séminaire Lotharingien de Combinatoire, Vol. 54, B54f (2006), 16 pp.
V. Jelinek, T. Mansour and M. Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.1, without the leading 2.
Rupert Li, Vincular Pattern Avoidance on Cyclic Permutations, arXiv:2107.12353 [math.CO], 2021.
T. Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.
T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
T. Mansour and M. Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From N. J. A. Sloane, Oct 13 2012
L. Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
L. Pudwell and A. Baxter, Ascent sequences avoiding pairs of patterns, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
|
|
|
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: A273488 A334955 A117848 * A356696 A163982 A246661
Adjacent sequences: A025239 A025240 A025241 * A025243 A025244 A025245
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
Clark Kimberling, Olivier Gérard
|
|
|
STATUS
|
approved
|
| |
|
|
