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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007852 Antichains in rooted plane trees on n nodes. 6
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 (list; graph; refs; listen; history; text; internal format)
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, 2014

G.-S. Cheon, H. Kim, L. W. Shapiro, Mutation effects in ordered trees, arXiv preprint arXiv:1410.1249, 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: A193040 A200755 A132262 * A232971 A110576 A074600

Adjacent sequences:  A007849 A007850 A007851 * A007853 A007854 A007855

KEYWORD

nonn

AUTHOR

Martin Klazar (klazar(AT)kam.mff.cuni.cz), Mar 15 1996

EXTENSIONS

More terms and formulas from Frank Ruskey, Nov 15 1997

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 11 11:31 EST 2017. Contains 295876 sequences.