|
%I #70 Feb 01 2024 12:10:23
%S 2,1,1,2,5,13,35,97,275,794,2327,6905,20705,62642,190987,586219,
%T 1810011,5617914,17518463,54857506,172431935,543861219,1720737981,
%U 5459867166,17369553427,55391735455,177040109419,567019562429,1819536774089
%N Generalized Catalan numbers.
%C 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
%C 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
%C 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
%H Vincenzo Librandi, <a href="/A025242/b025242.txt">Table of n, a(n) for n = 1..1000</a>
%H Petr Gregor, Torsten Mütze, and Namrata, <a href="https://arxiv.org/abs/2306.08420">Combinatorial generation via permutation languages. VI. Binary trees</a>, arXiv:2306.08420 [cs.DM], 2023.
%H Petr Gregor, Torsten Mütze, and Namrata, <a href="https://doi.org/10.4230/LIPIcs.ISAAC.2023.33">Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections</a>, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See p. 33.13.
%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.
%H Jia Huang and Erkko Lehtonen, <a href="https://arxiv.org/abs/2401.15786">Associative-commutative spectra for some varieties of groupoids</a>, arXiv:2401.15786 [math.CO], 2024. See p. 18.
%H Vít Jelínek, Toufik Mansour and Mark Shattuck, <a href="http://dx.doi.org/10.1016/j.aam.2012.09.002">On multiple pattern avoiding set partitions</a>, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.1, without the leading 2.
%H Yvan Le Borgne, <a href="http://www.emis.de/journals/SLC/wpapers/s54leborgne.html">Counting Upper Interactions in Dyck Paths</a>, Séminaire Lotharingien de Combinatoire, Vol. 54, B54f (2006), 16 pp.
%H Rupert Li, <a href="https://arxiv.org/abs/2107.12353">Vincular Pattern Avoidance on Cyclic Permutations</a>, arXiv:2107.12353 [math.CO], 2021.
%H Toufik Mansour, <a href="https://arxiv.org/abs/math/0110039">Restricted 1-3-2 permutations and generalized patterns</a>, arXiv:math/0110039 [math.CO], 2001.
%H Toufik Mansour, <a href="http://dx.doi.org/10.1007/s00026-002-8031-2">Restricted 1-3-2 permutations and generalized patterns</a>, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
%H Toufik Mansour and Mark Shattuck, <a href="http://puma.dimai.unifi.it/22_2/mansour_shattuck.pdf">Restricted partitions and generalized Catalan numbers</a>, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From _N. J. A. Sloane_, Oct 13 2012
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, 2015.
%H Lara Pudwell and Andrew Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.
%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%F a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-3)*a(3) for n >= 4.
%F G.f.: (1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4))/2. - _Michael Somos_, Jun 08 2000
%F 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
%F 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
%t a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-1-k ], {k, 2, n-1} ];
%o (PARI) a(n)=polcoeff((1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4+x*O(x^n)))/2,n)
%Y Cf. A000108, A001006, A006318, A004148, A007477, A082582, A086581.
%K nonn,easy
%O 1,1
%A _Clark Kimberling_, _Olivier Gérard_
|
