login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001002 Number of dissections of a convex (n+2)-gon into triangles and quadrilaterals by nonintersecting diagonals.
(Formerly M2852 N1146)
30
1, 1, 3, 10, 38, 154, 654, 2871, 12925, 59345, 276835, 1308320, 6250832, 30142360, 146510216, 717061938, 3530808798, 17478955570, 86941210950, 434299921440, 2177832612120, 10959042823020, 55322023332420, 280080119609550, 1421744205767418, 7234759677699954 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
a(n+1) is number of (2,3)-rooted trees on n nodes.
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
a(n) is the number of parking functions of size n avoiding the patterns 231, 312, and 321. - Lara Pudwell, Apr 10 2023
REFERENCES
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 211 (3.2.73-74)
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1372 (first 101 terms from T. D. Noe)
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Paul Barry, On the Central Coefficients of Bell Matrices, J. Int. Seq. 14 (2011) # 11.4.3, example 7.
D. Birmajer, J. B. Gil, and M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.
I. M. H. Etherington, Some problems of non-associative combinations (I), 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.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
Thomas M. Richardson, The three 'R's and Dual Riordan Arrays, arXiv:1609.01193 [math.CO], 2016.
A. Schuetz and G. Whieldon, Polygonal Dissections and Reversions of Series, arXiv preprint arXiv:1401.7194 [math.CO], 2014.
FORMULA
G.f. (offset 1) is series reversion of x - x^2 - x^3.
a(n) = (1/(n+1))*Sum_{k=ceiling(n/2)..n} binomial(n+k, k)*binomial(k, n-k). - Len Smiley
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
G.f.: (4*sin(asin((27*x+11)/16)/3)-1)/(3*x). - Paul Barry, Feb 02 2005
G.f. satisfies: A(x) = 1 + x*A(x)^2 + x^2*A(x)^3. - Paul D. Hanna, Jun 22 2012
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
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
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
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
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
Logarithmic derivative yields A213684. - Paul D. Hanna, Jun 22 2012
a(n) ~ 3^(3*n+3/2) / (2 * sqrt(2*Pi) * 5^(n+1/2) * n^(3/2)). - Vaclav Kotesovec, Mar 09 2014
a(n) = Catalan(n)*hypergeom([1/2-n/2, -n/2], [-2*n], -4) for n>0. - Peter Luschny, Oct 03 2014
a(n) = [x^n] 1/(1 - x - x^2)^(n+1)/(n + 1). - Ilya Gutkovskiy, Mar 29 2018
EXAMPLE
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).
MAPLE
a:= proc(n) option remember; `if`(n<2, 1, (n*(22*n-11)*
a(n-1) + (9*n-6)*(3*n-4)*a(n-2))/(5*n*(n+1)))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Jan 21 2021
MATHEMATICA
Rest[CoefficientList[InverseSeries[Series[y - y^2 - y^3, {y, 0, 30}], x], x]]
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 *)
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}]];
Table[a[n], {n, 0, 30}] (* Li Han, Jan 02 2021 *)
PROG
(PARI) a(n)=if(n<0, 0, polcoeff(serreverse(x-x^2-x^3+x^2*O(x^n)), n+1))
(PARI) a(n)=if(n<0, 0, sum(k=0, n\2, (2*n-k)!/k!/(n-2*k)!)/(n+1)!)
(PARI) a(n)=sum(k=0, n\2, binomial(2*n-k, n+k)*binomial(n+k, k))/(n+1) \\ Hanna
(PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{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
(PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{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
(Maxima)
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);
makelist(T(n, 1), n, 1, 10); /* Vladimir Kruchinin, Oct 03 2014 */
(Sage)
A001002 = lambda n: catalan_number(n)*hypergeometric([1/2-n/2, -n/2], [-2*n], -4) if n>0 else 1
[A001002(n).n(100).round() for n in range(24)] # Peter Luschny, Oct 03 2014
(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
CROSSREFS
n*a(n) = A038112(n-1), n > 0.
Sequence in context: A151061 A109085 A259690 * A151062 A000902 A151063
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Revised by Emeric Deutsch and Len Smiley, Jun 05 2005
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 21 06:38 EDT 2024. Contains 373540 sequences. (Running on oeis4.)