login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A187764 Number of uud-avoiding rooted non-crossing trees of n+1 vertices with the root 1. 0
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

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

Y. Sun, 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

Conjecture: 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

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

Sequence in context: A151131 A151132 A200075 * A151133 A213333 A083886

Adjacent sequences:  A187761 A187762 A187763 * A187765 A187766 A187767

KEYWORD

nonn

AUTHOR

R. J. Mathar, Jan 04 2013

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 01:14 EDT 2019. Contains 326136 sequences. (Running on oeis4.)