A002293 Number of dissections of a polygon: binomial(4*n, n)/(3*n + 1).
1, 1, 4, 22, 140, 969, 7084, 53820, 420732, 3362260, 27343888, 225568798, 1882933364, 15875338990, 134993766600, 1156393243320, 9969937491420, 86445222719724, 753310723010608, 6594154339031800, 57956002331347120, 511238042454541545
Offset: 0
Examples
There are a(2) = 4 quartic trees (vertex degree <= 4 and 4 possible branchings) with 2 vertices (one of them the root). Adding one more branch (one more vertex) to these four trees yields 4*4 + 6 = 22 = a(3) such trees.
References
- Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 23.
- R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347.
- Peter Hilton and Jean Pedersen, Catalan numbers, their generalization, and their uses, Math. Intelligencer 13 (1991), no. 2, 64-75.
- V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.
- G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, Heidelberg, New York, 2 vols., 1972, Vol. 1, problem 211, p. 146 with solution on p. 348.
- 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
- G. C. Greubel, Table of n, a(n) for n = 0..1000[Terms 0 to 100 computed by T. D. Noe; terms 101 to 1000 by G. C. Greubel, Jan 14 2017]
- Norbert A'Campo, Signatures of monic polynomials, arXiv:1702.05885 [math.AG], 2017.
- V. E. Adler and A. B. Shabat, Volterra chain and Catalan numbers, arXiv:1810.13198 [nlin.SI], 2018.
- Francesca Aicardi, Catalan triangle and tied arc diagrams, arXiv:2011.14628 [math.CO], 2020.
- Francesca Aicardi, Diego Arcis, and Jesús Juyumaya, Ramified inverse and planar monoids, Mosc Math J, 24(3):321-355, 9 2024.
- M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007) 93-102, Theor. 6
- T. Anderson, T. B. McLean, H. Pajoohesh, and C. Smith, The combinatorics of all regular flexagons, Eu. J. Combinat. 31 (2010) 72-80, Theorem 2.
- Joerg Arndt, Matters Computational (The Fxtbook), pp. 337-338
- Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014-2015.
- A. Asinowski, B. Hackl, and S. Selkirk, Down step statistics in generalized Dyck paths, arXiv:2007.15562 [math.CO], 2020.
- Roland Bacher, Fair Triangulations, arXiv:0710.0960 [math.CO], 2007.
- P. Balduf, The propagator and diffeomorphisms of an interacting field theory, Master's thesis, submitted to the Institut für Physik, Mathematisch-Naturwissenschaftliche Fakultät, Humboldt-Universtät, Berlin, 2018.
- C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics, 246(1-3) (2002), 29-55.
- Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
- Paul Barry, On the Gap-sum and Gap-product Sequences of Integer Sequences, arXiv:2104.05593 [math.CO], 2021.
- Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 2.
- M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
- M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
- D. Bevan, D. Levin, P. Nugent, J. Pantone, and L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510:08036 [math.CO], 2015.
- Michel Bousquet and Cédric Lamathe, On symmetric structures of order two, Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176.
- T. Daniel Brennan, Christian Ferko, and Savdeep Sethi, A Non-Abelian Analogue of DBI from T₸, arXiv:1912.12389 [hep-th], 2019. See also SciPost Phys. Vol. 8 (2020), 052.
- Wun-Seng Chou, Tian-Xiao He, and Peter J.-S. Shiue, On the Primality of the Generalized Fuss-Catalan Numbers, J. Int. Seqs., 21 (2018), #18.2.1.
- Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
- J. Cigler, Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results, 2013.
- N. Combe and V. Jugé, Counting bi-colored A'Campo forests, arXiv:1702.07672 [math.AG], 2017.
- Tom Copeland, Discriminating Deltas, Depressed Equations, and Generalized Catalan Numbers, 2012.
- Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See p. 25.
- C. Defant and N. Kravitz, Stack-sorting for words, arXiv:1809.09158 [math.CO], 2018.
- Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
- Bryan Ek, Lattice Walk Enumeration, arXiv:1803.10920 [math.CO], 2018.
- Bryan Ek, Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics, arXiv:1804.05933 [math.CO], 2018.
- Jishe Feng, The Hessenberg matrices and Catalan and its generalized numbers, arXiv:1810.09170 [math.CO], 2018. See p. 4.
- M. Gross, Mirror symmetry and the Strominger-Yau-Zaslow conjecture, arXiv:1212.4220 [math.AG], p. 58, 2013.
- F. Harary, E. M. Palmer, and R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974.
- F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
- Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k, arXiv:2204.14023 [math.CO], 2022.
- Forrest M. Hilton, Finite Dynamical Laminations, arXiv:2408.01353 [math.DS], 2024. See p. 7.
- V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
- V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.
- Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
- Ionut E. Iacob, T. Bruce McLean and Hua Wang, The V-flex, Triangle Orientation, and Catalan Numbers in Hexaflexagons, The College Mathematics Journal, Vol. 43, No. 1 (January 2012), pp. 6-10.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 286.
- V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36 No. 4 (2006), 364-387.
- R. P. Loh, A. G. Shannon, and A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, preprint, 1980.
- D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (T_n for s=4).
- Henri Muehle and Philippe Nadeau, A Poset Structure on the Alternating Group Generated by 3-Cycles, arXiv:1803.00540 [math.CO], 2018.
- J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv:1403.5962 [math.CO], 2014.
- C. O. Oakley and R. J. Wisner, Flexagons, Am. Math. Monthly 64 (3) (1957) 143-154, u_{3k+1}.
- C. B. Pah and M. Saburov, Single Polygon Counting on Cayley Tree of Order 4: Generalized Catalan Numbers, Middle-East Journal of Scientific Research 13 (Mathematical Applications in Engineering): 01-05, 2013, ISSN 1990-9233.
- Karol A. Penson and Karol Zyczkowski, Product of Ginibre matrices : Fuss-Catalan and Raney distribution, Phys. Rev. E 83, 061118, 15 June 2011.
- Karol A. Penson and Karol Zyczkowski, Product of Ginibre matrices : Fuss-Catalan and Raney distribution, arXiv:1103.3453 [math-ph], 2011.
- Yuan (Friedrich) Qiu, Joe Sawada, and Aaron Williams, Maximize the Rightmost Digit: Gray Codes for Restricted Growth Strings, WALCOM 2025. See p. 5.
- Alison Schuetz and Gwyneth Whieldon, Polygonal Dissections and Reversions of Series, arXiv:1401.7194 [math.CO], 2014.
- B. Sury, Generalized Catalan numbers: linear recursion and divisibility, JIS 12 (2009), Article 09.7.5.
- L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).
- Wikipedia, Fuss-Catalan number
- N. J. Wildberger and Dean Rubine, A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode, Amer. Math. Monthly (2025). See section 12.
- Sophia Yakoubov, Pattern Avoidance in Extensions of Comb-Like Posets, arXiv:1310.2979 [math.CO], 2013-2014.
- Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 7.
- Jian Zhou, Fat and Thin Emergent Geometries of Hermitian One-Matrix Models, arXiv:1810.03883 [math-ph], 2018.
Crossrefs
Cf. A000260, A002295, A002296, A027836, A062994, A346646 (binomial transform), A346664 (inverse binomial transform).
Cf. A006632, A006633, A006634, A025174, A069271, A196678, A224274, A233658, A233666, A233667, A277877, A283049, A283101, A283102, A283103.
Polyominoes: A005038 (oriented), A005040 (unoriented), A369471 (chiral), A369472 (achiral), A001764 {4,oo}, A002294 {6,oo}.
Cf. A130564 (for generalized Catalan C(k, n), for = 4).
Programs
-
GAP
List([0..22],n->Binomial(4*n,n)/(3*n+1)); # Muniru A Asiru, Nov 01 2018
-
Magma
[ Binomial(4*n,n)/(3*n+1): n in [0..50]]; // Vincenzo Librandi, Apr 19 2011
-
Maple
series(RootOf(g = 1+x*g^4, g),x=0,20); # Mark van Hoeij, Nov 10 2011 seq(binomial(4*n, n)/(3*n+1),n=0..20); # Robert FERREOL, Apr 02 2015 # Using the integral representation above: Digits:=6; R:=proc(x)((I + sqrt(3))*(4*sqrt(256 - 27*x) - 12*I*sqrt(3)*sqrt(x))^(1/3))/16 - ((I - sqrt(3))*(4*sqrt(256 - 27*x) + 12*I*sqrt(3)*sqrt(x))^(1/3))/16;end; W:=proc(x) x^(-3/4) * sqrt(4*R(x) - 3^(3/4)*x^(1/4)/sqrt(R(x)))/(2*3^(1/4)*Pi);end; # Attention: W(x) is singular at x = 0. Integration is done from a very small positive x to x = 256/27. # For a(8): ... gives 420732 evalf(int(x^8*W(x),x=0.000001..256/27)); # Karol A. Penson, Jul 05 2024
-
Mathematica
CoefficientList[InverseSeries[ Series[ y - y^4, {y, 0, 60}], x], x][[Range[2, 60, 3]]] Table[Binomial[4n,n]/(3n+1),{n,0,25}] (* Harvey P. Dale, Apr 18 2011 *) CoefficientList[1 + InverseSeries[Series[x/(1 + x)^4, {x, 0, 60}]], x] (* Gheorghe Coserea, Aug 12 2015 *) terms = 22; A[] = 0; Do[A[x] = 1 + x*A[x]^4 + O[x]^terms, terms]; CoefficientList[A[x], x] (* Jean-François Alcover, Jan 13 2018 *) -
PARI
a(n)=binomial(4*n,n)/(3*n+1) /* Charles R Greathouse IV, Jun 16 2011 */
-
PARI
my(x='x+O('x^33)); Vec(1 + serreverse(x/(1+x)^4)) \\ Gheorghe Coserea, Aug 12 2015 -
Python
A002293_list, x = [1], 1 for n in range(100): x = x*4*(4*n+3)*(4*n+2)*(4*n+1)//((3*n+2)*(3*n+3)*(3*n+4)) A002293_list.append(x) # Chai Wah Wu, Feb 19 2016
Formula
O.g.f. satisfies: A(x) = 1 + x*A(x)^4 = 1/(1 - x*A(x)^3).
a(n) = binomial(4*n,n-1)/n, n >= 1, a(0) = 1. From the Lagrange series of the o.g.f. A(x) with its above given implicit equation.
From Karol A. Penson, Apr 02 2010: (Start)
Integral representation as n-th Hausdorff power moment of a positive function on the interval [0, 256/27]:
a(n) = Integral_{x=0..256/27}(x^n((3/256) * sqrt(2) * sqrt(3) * ((2/27) * 3^(3/4) * 27^(1/4) * 256^(/4) * hypergeom([-1/12, 1/4, 7/12], [1/2, 3/4], (27/256)*x)/(sqrt(Pi) * x^(3/4)) - (2/27) * sqrt(2) * sqrt(27) * sqrt(256) * hypergeom([1/6, 1/2, 5/6], [3/4, 5/4], (27/256)*x)/ (sqrt(Pi) * sqrt(x)) - (1/81) * 3^(1/4) * 27^(3/4) * 256^(1/4) * hypergeom([5/12, 3/4, 13/12], [5/4, 3/2], (27/256)*x/(sqrt(Pi)*x^(1/4)))/sqrt(Pi))).
This representation is unique as it represents the solution of the Hausdorff moment problem.
O.g.f.: hypergeom([1/4, 1/2, 3/4], [2/3, 4/3], (256/27)*x);
E.g.f.: hypergeom([1/4, 1/2, 3/4], [2/3, 1, 4/3], (256/27)*x). (End)
a(n) = upper left term in M^n, M = the production matrix:
1, 1
3, 3, 1
6, 6, 3, 1
...
(where 1, 3, 6, 10, ...) is the triangular series. - Gary W. Adamson, Jul 08 2011
O.g.f. satisfies g = 1+x*g^4. If h is the series reversion of x*g, so h(x*g)=x, then (x-h(x))/x^2 is the o.g.f. of A006013. - Mark van Hoeij, Nov 10 2011
a(n) = binomial(4*n+1, n)/(4*n+1) = A062993(n+2,2). - Robert FERREOL, Apr 02 2015
a(n) = Sum_{i=0..n-1} Sum_{j=0..n-1-i} Sum_{k=0..n-1-i-j} a(i)*a(j)*a(k)*a(n-1-i-j-k) for n>=1; and a(0) = 1. - Robert FERREOL, Apr 02 2015
a(n) ~ 2^(8*n+1/2) / (sqrt(Pi) * n^(3/2) * 3^(3*n+3/2)). - Vaclav Kotesovec, Jun 03 2015
From Peter Bala, Oct 16 2015: (Start)
D-finite with recurrence: a(n+1) = a(n)*4*(4*n + 3)*(4*n + 2)*(4*n + 1)/((3*n + 2)*(3*n + 3)*(3*n + 4)). - Chai Wah Wu, Feb 19 2016
E.g.f.: F([1/4, 1/2, 3/4], [2/3, 1, 4/3], 256*x/27), where F is the generalized hypergeometric function. - Stefano Spezia, Dec 27 2019
x*A'(x)/A(x) = (A(x) - 1)/(- 3*A(x) + 4) = x + 7*x^2 + 55*x^3 + 455*x^4 + ... is the o.g.f. of A224274. Cf. A001764 and A002294 - A002296. - Peter Bala, Feb 04 2022
a(n) = hypergeom([1 - n, -3*n], [2], 1). Row sums of A173020. - Peter Bala, Aug 31 2023
G.f.: t*exp(4*t*hypergeom([1, 1, 5/4, 3/2, 7/4], [4/3, 5/3, 2, 2], (256*t)/27))+1. - Karol A. Penson, Dec 20 2023
From Karol A. Penson, Jul 03 2024: (Start)
a(n) = Integral_{x=0..256/27} x^(n)*W(x)dx, n>=0, where W(x) = x^(-3/4) * sqrt(4*R(x) - 3^(3/4)*x^(1/4)/sqrt(R(x)))/(2*3^(1/4)*Pi), with R(x) = ((i + sqrt(3))*(4*sqrt(256 - 27*x) -12*i*sqrt(3*x))^(1/3))/16 - ((i - sqrt(3))*(4*sqrt(256 - 27*x) + 12*i* sqrt(3*x))^(1/3))/16, where i is the imaginary unit.
The elementary function W(x) is positive on the interval x = (0, 256/27) and is equal to the combination of hypergeometric functions in my formula from 2010; see above.
(Pi*W(x))^6 satisfies an algebraic equation of order 6, with integer polynomials as coefficients. (End)
G.f.: (Sum_{n >= 0} binomial(4*n+1, n)*x^n) / (Sum_{n >= 0} binomial(4*n, n)*x^n). - Peter Bala, Dec 14 2024
G.f. A(x) satisfies A(x) = 1/A(-x*A(x)^7). - Seiichi Manyama, Jun 16 2025
Comments