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

%I #54 Nov 11 2021 11:06:15

%S 1,1,3,11,45,198,919,4445,22215,114000,597790,3191070,17289023,

%T 94845796,525838005,2941748627,16585870501,94147448172,537592229784,

%U 3085816136840,17795391949590,103051160368120,598997937352830,3493575551891610,20438727738501275,119911429466179978

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

%H Y. Sun and Z. Wang, <a href="http://dx.doi.org/10.1007/s00373-010-0950-9">Consecutive pattern avoidances in non-crossing trees</a>, Graph. Combinat. 26 (2010) 815-832.

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

%F 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

%F 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

%F 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

%F a(n) = Catalan(n)*hypergeom([1/2, 1-n], [n+2], -4) for n>=1. - _Peter Luschny_, Apr 28 2016

%F 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

%F 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

%p a := n -> `if`(n=0,1,hypergeom([1/2, 1-n], [n+2], -4)*binomial(2*n,n)/(n+1)):

%p seq(simplify(a(n)), n=0..25); # _Peter Luschny_, Apr 28 2016

%t a[n_] := Sum[Binomial[2k-2, k-1] Binomial[2n, n-k]/n, {k, 1, n}]; a[0] = 1;

%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Jun 23 2019, after _Vladimir Kruchinin_ *)

%o (PARI)

%o N = 66; x = 'x + O('x^N);

%o C=(1-sqrt(1-4*x))/(2*x);

%o gf = (3-sqrt(5-4*C))/2;

%o v = Vec(gf)

%o /* _Joerg Arndt_, Jan 04 2013 */

%o (Maxima)

%o 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 */

%o 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 */

%Y Cf. A000108 (Catalan numbers).

%K nonn

%O 0,3

%A _R. J. Mathar_, Jan 04 2013