A007852 Number of 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

Author

Martin Klazar, Mar 15 1996

Keywords

• nonn

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

a(n) is the moment of order 2*n of the sum of two position operators in the weakly monotonne Fock space - Anna Kula, May 09 2025

a(n) is the moment of order 2*n of the measure with the density defined by g(x) = 1/(4*Pi) * (sqrt(sqrt(100-16x^2)-x^2-10) - sqrt(4-x^2)) if |x|<=2, g(x) = 1/(4*Pi) * sqrt((-2x^2-2|x|sqrt(4-x^2)+20) if 2 <= |x| <= 5/2 and g(x)=0 otherwise - Anna Kula, May 09 2025

Links

• 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, and F. Peschanski, A Quantitative Study of Pure Parallel Processes, arXiv preprint arXiv:1407.1873 [cs.PL], 2014.
• G.-S. Cheon, H. Kim, and L. W. Shapiro, Mutation effects in ordered trees, arXiv preprint arXiv:1410.1249 [math.CO], 2014.
• V. Crismale, M. E. Griseta, and J. Wysoczański, Weakly Monotone Fock Space and Monotone Convolution of the Wigner Law, J Theor Probab 33, 268-294,2020.
• Martin Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
• Frank 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

Crossrefs

Cf. A007440, A153294.

Programs

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 *)

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

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

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

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_{j=1..n-1} (a(j)+b(j))*a(n-j), where b(n) = C(2*n-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..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

Extensions

More terms and formulas from Frank Ruskey, Nov 15 1997