|
%I #60 Apr 05 2019 11:59:29
%S 1,2,7,29,131,625,3099,15818,82595,439259,2371632,12967707,71669167,
%T 399751019,2247488837,12723799989,72474333715,415046380767,
%U 2388355096446,13803034008095,80082677184820,466263828731640,2723428895205210,15954063529603565,93711351580424391
%N Antichains in rooted plane trees on n nodes.
%C Setting both offsets to zero, this is the Catalan transform of A007317. - _R. J. Mathar_, Jun 29 2009
%C a(n) is also the cumulated sizes of admissible cuts of general rooted trees of size n. - _Antoine Genitrini_, Mar 14 2013
%H O. Bodini, A. Genitrini and F. Peschanski, <a href="http://www-apr.lip6.fr/~genitrini/doc_ens/are/article1.pdf">Enumeration and Random Generation of Concurrent Computations</a> 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.
%H O. Bodini, A. Genitrini and F. Peschanski, <a href="http://www-apr.lip6.fr/~pesch/datas/bogepe-pure-merge-13-preprint.pdf">A Quantitative Study of Pure Parallel Processes</a>, Preprint, 2013.
%H O. Bodini, A. Genitrini, F. Peschanski, <a href="http://arxiv.org/abs/1407.1873">A Quantitative Study of Pure Parallel Processes</a>, arXiv preprint arXiv:1407.1873 [cs.PL], 2014.
%H G.-S. Cheon, H. Kim, L. W. Shapiro, <a href="http://arxiv.org/abs/1410.1249">Mutation effects in ordered trees</a>, arXiv preprint arXiv:1410.1249 [math.CO], 2014.
%H M. Klazar, <a href="http://dx.doi.org/10.1006/eujc.1995.0095">Twelve countings with rooted plane trees</a>, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
%H F. Ruskey, <a href="http://dx.doi.org/10.1137/0210011">Listing and Counting Subtrees of a Tree</a>, SIAM J. Computing, 10 (1981) 141-150.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Res#revert">Index entries for reversions of series</a>
%F G.f.: A(z) = (1-B(z)-sqrt(1-5*z-B(z)))/2, where B(z) = (1-sqrt(1-4*z))/2.
%F 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).
%F Also REVERT[A(x)] = x + 2*x^2 + x^3*(A007440(x) (Reversion of Fibonacci). - _Olivier Gérard_, Jul 05 2001
%F a(n+1) = Sum_{k, 0<=k<=n} A039599(n,k) * A000108(k). - _Philippe Deléham_, Mar 12 2007
%F 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
%F a(n) ~ (25/4)^n / (sqrt(15*Pi) * n^(3/2)). - _Vaclav Kotesovec_, Mar 08 2014
%F 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
%F 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
%t 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 *)
%o (Python)
%o def a(n):
%o l = [0,1,2,7]
%o if n < 4:
%o return l[n]
%o for i in range(n-3):
%o 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)
%o return l[i%4]
%o # _Antoine Genitrini_, Mar 14 2013
%o (PARI)
%o N = 33; x = 'x + O('x^N);
%o B = (1-sqrt(1-4*x))/2;
%o gf = (1-B-sqrt(1-5*x-B))/2;
%o v = Vec(gf)
%o \\ _Joerg Arndt_, Mar 14 2013
%o (Maxima)
%o 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 */
%Y Cf. A007440, A153294.
%K nonn
%O 1,2
%A _Martin Klazar_, Mar 15 1996
%E More terms and formulas from _Frank Ruskey_, Nov 15 1997
| 