A187764 Number of uud-avoiding rooted non-crossing trees of n+1 vertices with the root 1.

1, 1, 3, 11, 45, 198, 919, 4445, 22215, 114000, 597790, 3191070, 17289023, 94845796, 525838005, 2941748627, 16585870501, 94147448172, 537592229784, 3085816136840, 17795391949590, 103051160368120, 598997937352830, 3493575551891610, 20438727738501275, 119911429466179978

Offset

0,3

Links

Table of n, a(n) for n=0..25.

Y. Sun and Z. Wang, Consecutive pattern avoidances in non-crossing trees, Graph. Combinat. 26 (2010) 815-832.

Formula

G.f.: (3-sqrt(5-4*C(x)))/2, where C(x) is the generating function of the Catalan numbers.

a(n) = Sum_(k=1..n, (C(2*k-2,k-1)*Sum_(i=k..n, i*C(i-1,k-1) * C(2*n-i-1,n-1))) /k)/n, n>0, a(0)=1. - Vladimir Kruchinin, Jan 23 2013

D-finite with recurrence 2*n*(2*n+1)*a(n) +3*(-27*n^2+47*n-16)*a(n-1) +30*(17*n^2-63*n+56)*a(n-2) -500*(2*n-5)*(n-3)*a(n-3)=0. - R. J. Mathar, Jan 24 2013

a(n) = Sum_{k=1..n} binomial(2*k-2,k-1)*binomial(2*n,n-k)/n, a(0)=1. - Vladimir Kruchinin, Apr 28 2016

a(n) = Catalan(n)*hypergeom([1/2, 1-n], [n+2], -4) for n>=1. - Peter Luschny, Apr 28 2016

G.f.: A=A(x) satisfies 0 = -x*A^4 + 6*x*A^3 + (-11*x - 1)*A^2 + (6*x + 3)*A + (-x - 2). - Joerg Arndt, Apr 29 2016

G.f.: A(x) = F(G(x)), where F(x) = 1 + x*C(x), G(x) = x*C(x)^2, and C(x) is the Catalan generating function. - Alexander Burstein, Nov 10 2021

Maple

a := n -> `if`(n=0, 1, hypergeom([1/2, 1-n], [n+2], -4)*binomial(2*n, n)/(n+1)):
seq(simplify(a(n)), n=0..25); # Peter Luschny, Apr 28 2016

Mathematica

a[n_] := Sum[Binomial[2k-2, k-1] Binomial[2n, n-k]/n, {k, 1, n}]; a[0] = 1;
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jun 23 2019, after Vladimir Kruchinin *)

Prog

(PARI)
N = 66;  x = 'x + O('x^N);
C=(1-sqrt(1-4*x))/(2*x);
gf = (3-sqrt(5-4*C))/2;
v = Vec(gf)
/* Joerg Arndt, Jan 04 2013 */
(Maxima)
a(n):=if n=0 then 1 else sum((binomial(2*k-2, k-1) * sum(i*binomial(i-1, k-1) * binomial(2*n-i-1, n-1), i, k, n)) / k, k, 1, n) / n; /* Vladimir Kruchinin, Jan 23 2013 */
a(n):=if n=0 then 1 else sum(binomial(2*k-2, k-1)*binomial(2*n, n-k), k, 1, n)/n; /*  Vladimir Kruchinin, Apr 28 2016 */

Crossrefs

Cf. A000108 (Catalan numbers).

Sequence in context: A151131 A151132 A200075 * A372310 A151133 A213333

Adjacent sequences: A187761 A187762 A187763 * A187765 A187766 A187767

Keyword

nonn

Author

R. J. Mathar, Jan 04 2013

Status

approved