A121873 Number of non-crossing plants in the (n+1)-sided regular polygon (contains non-crossing trees).

1, 3, 14, 80, 510, 3479, 24848, 183465, 1389090, 10726452, 84150858, 668825768, 5373971036, 43580383095, 356234802952, 2932097981824, 24279982680870, 202134854855973, 1690839212784240, 14204198452365180, 119784707913644598, 1013675671656956976

Offset

1,2

Links

Table of n, a(n) for n=1..22.

R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.

F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.

J.-L. Loday, Inversion of integral series enumerating planar trees, Séminaire Lotharingien de Combinatoire 53, Art. B53d, 16 pp, 2005. See example (g).

Formula

x = (y - y^2 - y^3)/(1+y)^2 is the inverse of the generating function.

a(n) = sum(j=0..n-1, (sum(i=0..n-j-1, binomial(i+n-1,n-1) *binomial(i+n,n-j-i-1))) *binomial(n,j))/n, n>0, a(0)=0. - Vladimir Kruchinin, Oct 12 2011

Example

a(2)=3 because the non-crossing plants in a triangle are the three non-crossing trees, made of two sides.
G.f. = x + 3*x^2 + 14*x^3 + 80*x^4 + 510*x^5 + 3479*x^6 + 25848*x^7 + ...

Mathematica

a[n_] := If[n==0, 0, Sum[Sum[Binomial[i+n-1, n-1]*Binomial[i+n, n-j-i-1], {i, 0, n-j-1}]*Binomial[n, j], {j, 0, n-1}]/n]; Table[a[n], {n, 1, 16}] (* Jean-François Alcover, Feb 20 2017, after Vladimir Kruchinin *)

Prog

(Maxima)
a(n):=if n=0 then 0 else sum((sum(binomial(i+n-1, n-1)*binomial(i+n, n-j-i-1), i, 0, n-j-1))*binomial(n, j), j, 0, n-1)/n; /* Vladimir Kruchinin, Oct 12 2011 */
(PARI) {a(n) = if( n<1, 0, polcoeff( serreverse( (x - x^2 + x^3) / (1 + x)^2 + x * O(x^n)), n))}; /* Michael Somos, Dec 31 2014 */

Crossrefs

Cf. A006013.

Sequence in context: A027614 A306040 A168592 * A361770 A107596 A212391

Adjacent sequences: A121870 A121871 A121872 * A121874 A121875 A121876

Keyword

nonn

Author

F. Chapoton, Aug 31 2006

Status

approved