%I M2852 N1146 #147 Apr 11 2023 07:19:31
%S 1,1,3,10,38,154,654,2871,12925,59345,276835,1308320,6250832,30142360,
%T 146510216,717061938,3530808798,17478955570,86941210950,434299921440,
%U 2177832612120,10959042823020,55322023332420,280080119609550,1421744205767418,7234759677699954
%N Number of dissections of a convex (n+2)-gon into triangles and quadrilaterals by nonintersecting diagonals.
%C a(n+1) is number of (2,3)-rooted trees on n nodes.
%C This sequence appears to be a transform of the Fibonacci numbers A000045. This sequence is to the Fibonacci numbers as the Catalan numbers A000108 is to the all ones sequence. See link to Mathematica program. - _Mats Granvik_, Dec 30 2017
%C a(n) is the number of parking functions of size n avoiding the patterns 231, 312, and 321. - _Lara Pudwell_, Apr 10 2023
%D F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 211 (3.2.73-74)
%D I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
%D I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A001002/b001002.txt">Table of n, a(n) for n = 0..1372</a> (first 101 terms from T. D. Noe)
%H Ayomikun Adeniran and Lara Pudwell, <a href="https://doi.org/10.54550/ECA2023V3S3R17">Pattern avoidance in parking functions</a>, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry3/barry132.html">On the Central Coefficients of Bell Matrices</a>, J. Int. Seq. 14 (2011) # 11.4.3, example 7.
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="http://arxiv.org/abs/1503.05242">Colored partitions of a convex polygon by noncrossing diagonals</a>, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
%H I. M. H. Etherington, <a href="http://www.jstor.org/stable/3605743">Non-associate powers and a functional equation</a>, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
%H I. M. H. Etherington, <a href="http://dx.doi.org/10.1017/S0950184300002639">Some problems of non-associative combinations</a>, Edinburgh Math. Notes, 32 (1940), 1-6.
%H I. M. H. Etherington, <a href="/A000108/a000108_14.pdf">Some problems of non-associative combinations (I)</a>, Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
%H Mats Granvik, <a href="/A001002/a001002.txt">Mathematica program to compute the sequence as a transform of the Fibonacci numbers.</a>
%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=395">Encyclopedia of Combinatorial Structures 395</a>
%H Elżbieta Liszewska and Wojciech Młotkowski, <a href="https://arxiv.org/abs/1907.10725">Some relatives of the Catalan sequence</a>, arXiv:1907.10725 [math.CO], 2019.
%H T. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1945-08486-9">The hypersurface cross ratio</a>, Bull. Amer. Math. Soc., 51 (1945), 976-984.
%H T. S. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1948-09002-4">Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products</a>, Bull. Amer. Math. Soc., 54 (1948), 352-360.
%H Thomas M. Richardson, <a href="http://arxiv.org/abs/1609.01193">The three 'R's and Dual Riordan Arrays</a>, arXiv:1609.01193 [math.CO], 2016.
%H A. Schuetz and G. Whieldon, <a href="http://arxiv.org/abs/1401.7194">Polygonal Dissections and Reversions of Series</a>, arXiv preprint arXiv:1401.7194 [math.CO], 2014.
%H <a href="/index/Res#revert">Index entries for reversions of series</a>
%F G.f. (offset 1) is series reversion of x - x^2 - x^3.
%F a(n) = (1/(n+1))*Sum_{k=ceiling(n/2)..n} binomial(n+k, k)*binomial(k, n-k). - _Len Smiley_
%F D-finite with recurrence 5*n*(n+1) * a(n) = 11*n*(2*n-1) * a(n-1) + 3*(3*n-2)*(3*n-4) * a(n-2). - _Len Smiley_
%F G.f.: (4*sin(asin((27*x+11)/16)/3)-1)/(3*x). - _Paul Barry_, Feb 02 2005
%F G.f. satisfies: A(x) = 1 + x*A(x)^2 + x^2*A(x)^3. - _Paul D. Hanna_, Jun 22 2012
%F Antidiagonal sums of triangle A104978 which has g.f. F(x,y) that satisfies: F = 1 + x*F^2 + x*y*F^3. - _Paul D. Hanna_, Mar 30 2005
%F a(n) = Sum_{k=0..floor(n/2)} C(2*n-k, n+k)*C(n+k, k)/(n+1). - _Paul D. Hanna_, Mar 30 2005
%F G.f. satisfies: x = Sum_{n>=1} 1/(1+x*A(x))^(2*n) * Product_{k=1..n} (1 - 1/(1+x*A(x))^k). - _Paul D. Hanna_, Apr 05 2012
%F G.f.: 1 + (1/x)*Sum_{n>=1} d^(n-1)/dx^(n-1) (x^2+x^3)^n/n!. - _Paul D. Hanna_, Jun 22 2012
%F G.f.: exp( Sum_{n>=1} d^(n-1)/dx^(n-1) ((x^2+x^3)^n/x)/n! ). - _Paul D. Hanna_, Jun 22 2012
%F Logarithmic derivative yields A213684. - _Paul D. Hanna_, Jun 22 2012
%F a(n) ~ 3^(3*n+3/2) / (2 * sqrt(2*Pi) * 5^(n+1/2) * n^(3/2)). - _Vaclav Kotesovec_, Mar 09 2014
%F a(n) = Catalan(n)*hypergeom([1/2-n/2, -n/2], [-2*n], -4) for n>0. - _Peter Luschny_, Oct 03 2014
%F a(n) = [x^n] 1/(1 - x - x^2)^(n+1)/(n + 1). - _Ilya Gutkovskiy_, Mar 29 2018
%e a(3)=10 because a convex pentagon can be dissected in 5 ways into triangles (draw 2 diagonals from any of the 5 vertices) and in 5 ways into a triangle and a quadrilateral (draw any of the 5 diagonals).
%p a:= proc(n) option remember; `if`(n<2, 1, (n*(22*n-11)*
%p a(n-1) + (9*n-6)*(3*n-4)*a(n-2))/(5*n*(n+1)))
%p end:
%p seq(a(n), n=0..25); # _Alois P. Heinz_, Jan 21 2021
%t Rest[CoefficientList[InverseSeries[Series[y - y^2 - y^3, {y, 0, 30}], x], x]]
%t a[n_] := CatalanNumber[n]*Hypergeometric2F1[1/2-n/2, -n/2, -2n, -4]; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jan 20 2015, after _Peter Luschny_ *)
%t a[n_] := a[n] = If[n == 0, 1, Sum[a[i] a[n - 1 - i], {i, 0, n - 1}] + Sum[a[i] a[j] a[n - 2 - i - j], {i, 0, n - 2}, {j, 0, n - 2 - i}]];
%t Table[a[n], {n, 0, 30}] (* _Li Han_, Jan 02 2021 *)
%o (PARI) a(n)=if(n<0,0,polcoeff(serreverse(x-x^2-x^3+x^2*O(x^n)),n+1))
%o (PARI) a(n)=if(n<0,0,sum(k=0,n\2,(2*n-k)!/k!/(n-2*k)!)/(n+1)!)
%o (PARI) a(n)=sum(k=0,n\2,binomial(2*n-k,n+k)*binomial(n+k,k))/(n+1) \\ Hanna
%o (PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
%o {a(n)=local(A=1); A=1+(1/x)*sum(m=1, n+1, Dx(m-1, (x^2+x^3 +x^2*O(x^n))^m/m!)); polcoeff(A, n)} \\ _Paul D. Hanna_, Jun 22 2012
%o (PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
%o {a(n)=local(A=1); A=exp(sum(m=1, n+1, Dx(m-1, (x^2+x^3 +x^2*O(x^n))^m/x/m!)+x*O(x^n))); polcoeff(A, n)} \\ _Paul D. Hanna_, Jun 22 2012
%o (Maxima)
%o T(n,k):=if n<0 or k<0 then 0 else if n<k then 0 else if n=k then 1 else if k=0 then 0 else T(n-1,k-1)+T(n,k+1)+T(n,k+2);
%o makelist(T(n,1),n,1,10); /* _Vladimir Kruchinin_, Oct 03 2014 */
%o (Sage)
%o A001002 = lambda n: catalan_number(n)*hypergeometric([1/2-n/2, -n/2], [-2*n], -4) if n>0 else 1
%o [A001002(n).n(100).round() for n in range(24)] # _Peter Luschny_, Oct 03 2014
%o (GAP) List([0..25], n->Sum([0..Int(n/2)],k->Binomial(2*n-k,n+k)*Binomial(n+k,k)/(n+1))); # _Muniru A Asiru_, Mar 30 2018
%Y n*a(n) = A038112(n-1), n > 0.
%Y Cf. A104978, A181997, A181998, A209441, A209442, A213684 (log).
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E Revised by _Emeric Deutsch_ and _Len Smiley_, Jun 05 2005