A007852 Antichains in rooted plane trees on n nodes.

1, 2, 7, 29, 131, 625, 3099, 15818, 82595, 439259, 2371632, 12967707, 71669167, 399751019, 2247488837, 12723799989, 72474333715, 415046380767, 2388355096446, 13803034008095, 80082677184820, 466263828731640, 2723428895205210, 15954063529603565, 93711351580424391

Offset

1,2

Comments

Setting both offsets to zero, this is the Catalan transform of A007317. - R. J. Mathar, Jun 29 2009

a(n) is also the cumulated sizes of admissible cuts of general rooted trees of size n. - Antoine Genitrini, Mar 14 2013

Links

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

O. Bodini, A. Genitrini and F. Peschanski, Enumeration and Random Generation of Concurrent Computations In proc. 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'12), Discrete Mathematics and Theoretical Computer Science, pp 83-96, 2012.

O. Bodini, A. Genitrini and F. Peschanski, A Quantitative Study of Pure Parallel Processes, Preprint, 2013.

O. Bodini, A. Genitrini, F. Peschanski, A Quantitative Study of Pure Parallel Processes, arXiv preprint arXiv:1407.1873 [cs.PL], 2014.

G.-S. Cheon, H. Kim, L. W. Shapiro, Mutation effects in ordered trees, arXiv preprint arXiv:1410.1249 [math.CO], 2014.

M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.

F. Ruskey, Listing and Counting Subtrees of a Tree, SIAM J. Computing, 10 (1981) 141-150.

Index entries for sequences related to rooted trees

Index entries for reversions of series

Formula

G.f.: A(z) = (1-B(z)-sqrt(1-5*z-B(z)))/2, where B(z) = (1-sqrt(1-4*z))/2.

a(1) = 1 and for n > 1 a(n) = sum( (a(j)+b(j))*a(n-j), j=1..n-1 ), where b(n) = C(2n-2, n-1)/n (Catalan number).

Also REVERT[A(x)] = x + 2*x^2 + x^3*(A007440(x) (Reversion of Fibonacci). - Olivier Gérard, Jul 05 2001

a(n+1) = Sum_{k, 0<=k<=n} A039599(n,k) * A000108(k). - Philippe Deléham, Mar 12 2007

P-recurrence: (-500*n+2000*n^3)*a(n)+(120-220*n-1380*n^2-920*n^3)*a(n+1)+(-1488-1626*n-387*n^2+21*n^3)*a(n+2)+(1088*n+1104+351*n^2+37*n^3)*a(n+3)+(-42*n^2-146*n-168-4*n^3)*a(n+4); a(0)=0; a(1)=1; a(2)=2; a(3)=7. - Antoine Genitrini, Mar 14 2013

a(n) ~ (25/4)^n / (sqrt(15*Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 08 2014

a(n) = sum(i=0..n, binomial(2*i+1,i)*binomial(2*n-1,n-i-1))/((2*n-1)). - Vladimir Kruchinin, Jun 09 2014

1 + 1/z*A(z)^2 = 1 + z + 4*z^2 + 18*z^3 + 86*z^4 + ... is the o.g.f. for A153294. - Peter Bala, Jul 21 2015

Mathematica

Rest[CoefficientList[Series[(1-(1-Sqrt[1-4*x])/2-Sqrt[1-5*x-(1-Sqrt[1-4*x])/2])/2, {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 08 2014 *)

Prog

(Python)
def a(n):
   l = [0, 1, 2, 7]
   if n < 4:
      return l[n]
   for i in range(n-3):
      l[i%4] = ( (-500*i+2000*i**3)*l[i%4]+(120-220*i-1380*i**2-920*i**3)*l[(i+1)%4]+(-1488-1626*i-387*i**2+21*i**3)*l[(i+2)%4]+(1088*i+1104+351*i**2+37*i**3)*l[(i+3)%4] ) / (+42*i**2+146*i+168+4*i**3)
   return l[i%4]
# Antoine Genitrini, Mar 14 2013
(PARI)
N = 33;  x = 'x + O('x^N);
B = (1-sqrt(1-4*x))/2;
gf = (1-B-sqrt(1-5*x-B))/2;
v = Vec(gf)
\\ Joerg Arndt, Mar 14 2013
(Maxima)
a(n):=sum(binomial(2*i+1, i)*binomial(2*n-1, n-i-1), i, 0, n)/((2*n-1)); /* Vladimir Kruchinin, Jun 09 2014 */

Crossrefs

Cf. A007440, A153294.

Sequence in context: A200755 A132262 A371431 * A300048 A232971 A366084

Adjacent sequences: A007849 A007850 A007851 * A007853 A007854 A007855

Keyword

nonn

Author

Martin Klazar, Mar 15 1996

Extensions

More terms and formulas from Frank Ruskey, Nov 15 1997

Status

approved