This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A002293 Number of dissections of a polygon: binomial(4n,n)/(3n+1). (Formerly M3587 N1454) 135

%I M3587 N1454

%S 1,1,4,22,140,969,7084,53820,420732,3362260,27343888,225568798,

%T 1882933364,15875338990,134993766600,1156393243320,9969937491420,

%U 86445222719724,753310723010608,6594154339031800,57956002331347120,511238042454541545

%N Number of dissections of a polygon: binomial(4n,n)/(3n+1).

%C The number of rooted loopless n-edge maps in the plane (planar with a distinguished outside face). - _Valery A. Liskovets_, Mar 17 2005

%C Number of lattice paths from (1,0) to (3n+1,n) which, starting from (1,0), only utilize the steps +(1,0) and +(0,1) and additionally, the paths lie completely below the line y = 1/3x (i.e., if (a,b) is in the path, then b < a/3). - Joseph Cooper (jecooper(AT)mit.edu), Feb 07 2006

%C Number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k)<=s(k-1)+3, see fxtbook link below. - _Joerg Arndt_, Apr 08 2011

%C From _Wolfdieter Lang_, Sep 14 2007: (Start)

%C a(n), n>=1, enumerates quartic trees (rooted, ordered, incomplete) with n vertices (including the root).

%C Pfaff-Fuss-Catalan sequence C^{m}_n for m=4. See the Graham et al. reference, p. 347. eq. 7.66. See also the Pólya-Szegő reference.

%C Also 4-Raney sequence. See the Graham et al. reference, pp. 346-347.

%C (End)

%C Bacher: "We describe the statistics of checkerboard triangulations obtained by coloring black every other triangle in triangulations of convex polygons." The current sequence (A002293) occurs on p. 12 as one of two "extremal sequences" of an array of coefficients of polynomials, whose generating functions are given in terms of hypergeometric functions. - _Jonathan Vos Post_, Oct 05 2007

%C From _Karol A. Penson_, Apr 02 2010: (Start)

%C Integral representation as n-th Hausdorff power moment of a positive function on the interval [0, 256/27], in Maple notation:

%C a(n) = int(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)), x=0..256/27), n=0,1,... .

%C This representation is unique as it represents the solution of the Hausdorff moment problem.

%C O.g.f.: hypergeom([1/4, 1/2, 3/4], [2/3, 4/3], (256/27)*x);

%C E.g.f.: hypergeom([1/4, 1/2, 3/4], [2/3, 1, 4/3], (256/27)*x). (End)

%C 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

%C A generating function in terms of a (labyrinthine) solution to a depressed quartic equation is given in the Copeland link for signed A005810. With D(z,t) that g.f., a g.f. for signed A002293 is {[-1+1/D(z,t)]/(4t)}^(1/3). - _Tom Copeland_, Oct 10 2012

%C For a relation to the inviscid Burgers's equation, see A001764. - _Tom Copeland_, Feb 15 2014

%C For relations to compositional inversion, the Legendre transform, and convex geometry, see the Copeland, the Schuetz and Whieldon, and the Gross (p. 58) links. - _Tom Copeland_, Feb 21 2017

%C This is the number of A'Campo bi-colored forests of degree n and co-dimension 0. This can be shown using generating functions or a combinatorial approach. See Combe and Jugé link below. - _Noemie Combe_, Feb 28 2017

%C Conjecturally, a(n) is the number of 3-uniform words over the alphabet [n] that avoid the patterns 231 and 221 (see the Defant and Kravitz link). - _Colin Defant_, Sep 26 2018

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 23.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347.

%D V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

%D 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.

%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 G. C. Greubel, <a href="/A002293/b002293.txt">Table of n, a(n) for n = 0..1000</a>[Terms 0 to 100 computed by T. D. Noe; terms 101 to 1000 by G. C. Greubel, Jan 14 2017]

%H Norbert A'Campo, <a href="https://arxiv.org/abs/1702.05885">Signatures of monic polynomials</a>, arXiv:1702.05885 [math.AG], 2017.

%H V. E. Adler, A. B. Shabat, <a href="https://arxiv.org/abs/1810.13198">Volterra chain and Catalan numbers</a>, arXiv:1810.13198 [nlin.SI], 2018.

%H M. Almeida, N. Moreira, R. Reis, <a href="http://dx.doi.org/10.1016/j.tcs.2007.07.029">Enumeration and generation with a string automata representation</a>, Theor. Comp. Sci. 387 (2007) 93-102, Theor. 6

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 337-338

%H J. Arndt, <a href="http://arxiv.org/abs/1405.6503">Subset-lex: did we miss an order?</a>, arXiv:1405.6503 [math.CO], 2014-2015.

%H Roland Bacher, <a href="http://arXiv.org/abs/0710.0960">Fair Triangulations</a>, arXiv:0710.0960 [math.CO], 2007.

%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating Functions for Generating Trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

%H M. Bernstein and N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0205301">Some canonical sequences of integers</a>, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.

%H M. Bernstein and N. J. A. Sloane, <a href="/A003633/a003633_1.pdf">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]

%H D. Bevan, D. Levin, P. Nugent, J. Pantone, L. Pudwell, <a href="http://arxiv.org/abs/1510.08036">Pattern avoidance in forests of binary shrubs</a>, arXiv preprint arXiv:1510:08036 [math.CO], 2015.

%H Michel Bousquet and Cédric Lamathe, <a href="http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1003">On symmetric structures of order two</a>, Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176.

%H Wun-Seng Chou, Tian-Xiao He, Peter J.-S. Shiue, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/He/he61.html">On the Primality of the Generalized Fuss-Catalan Numbers</a>, J. Int. Seqs., Vol. 21 (2018), #18.2.1.

%H J. Cigler, <a href="http://homepage.univie.ac.at/Johann.Cigler/preprints/chebyshev-survey.pdf">Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results</a>, 2013.

%H N. Combe, V. Jugé, <a href="https://arxiv.org/abs/1702.07672">Counting bi-colored A'Campo forests</a> arxiv:1702.07672 [math.AG], 2017.

%H T. Copeland, <a href="http://tcjpn.wordpress.com/2012/06/13/depressed-equations-and-generalized-catalan-numbers/">Discriminating Deltas, Depressed Equations, and Generalized Catalan Numbers</a>, 2012.

%H C. Defant and N. Kravitz, <a href="https://arxiv.org/abs/1809.09158">Stack-sorting for words</a>, arXiv:1809.09158 [math.CO], 2018.

%H Bryan Ek, <a href="https://arxiv.org/abs/1803.10920">Lattice Walk Enumeration</a>, arXiv:1803.10920 [math.CO], 2018.

%H Bryan Ek, <a href="https://arxiv.org/abs/1804.05933">Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics</a>, arXiv:1804.05933 [math.CO], 2018.

%H Jishe Feng, <a href="https://arxiv.org/abs/1810.09170">The Hessenberg matrices and Catalan and its generalized numbers</a>, arXiv:1810.09170 [math.CO], 2018. See p. 4.

%H M. Gross, <a href="http://arxiv.org/abs/11212.4220">Mirror symmetry and the Strominger-Yau-Zaslow conjecture</a>, arXiv preprint arXiv:1212.4220 [math.AG], p. 58, 2013.

%H F. Harary, E. M. Palmer, R. C. Read, <a href="/A000108/a000108_20.pdf">On the cell-growth problem for arbitrary polygons, computer printout, circa 1974</a>

%H F. Harary, E. M. Palmer and R. C. Read, <a href="http://dx.doi.org/10.1016/0012-365X(75)90041-2">On the cell-growth problem for arbitrary polygons</a>, Discr. Math. 11 (1975), 371-389.

%H V. E. Hoggatt, Jr., <a href="/A005676/a005676.pdf">7-page typed letter to N. J. A. Sloane with suggestions for new sequences</a>, circa 1977.

%H V. E. Hoggatt, Jr. and M. Bicknell, <a href="http://www.fq.math.ca/Scanned/14-5/hoggatt1.pdf">Catalan and related sequences arising from inverses of Pascal's triangle matrices</a>, Fib. Quart., 14 (1976), 395-405.

%H Hsien-Kuei Hwang, Mihyun Kang, Guan-Huei Duh, <a href="https://doi.org/10.4230/LIPIcs.AofA.2018.29">Asymptotic Expansions for Sub-Critical Lagrangean Forms</a>, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.

%H Ionut E. Iacob, T. Bruce McLean and Hua Wang, <a href="http://www.jstor.org/stable/10.4169/college.math.j.43.1.006">The V-flex, Triangle Orientation, and Catalan Numbers in Hexaflexagons</a>, The College Mathematics Journal, Vol. 43, No. 1 (January 2012), pp. 6-10.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=286">Encyclopedia of Combinatorial Structures 286</a>

%H V. A. Liskovets and T. R. Walsh, <a href="http://dx.doi.org/10.1016/j.aam.2005.03.006">Counting unrooted maps on the plane</a>, Advances in Applied Math., 36 No. 4 (2006), 364-387.

%H R. P. Loh, A. G. Shannon, A. F. Horadam, <a href="/A000969/a000969.pdf">Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients</a>, Preprint, 1980.

%H D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://dx.doi.org/10.1006/jcta.2002.3273">The tennis ball problem</a>, J. Combin. Theory, A 99 (2002), 307-344 (T_n for s=4).

%H Henri Muehle, Philippe Nadeau, <a href="https://arxiv.org/abs/1803.00540">A Poset Structure on the Alternating Group Generated by 3-Cycles</a>, arXiv:1803.00540 [math.CO], 2018.

%H J.-C. Novelli, J.-Y. Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962 [math.CO], 2014.

%H C. B. Pah and M. Saburov, <a href="http://dx.doi.org/10.5829/idosi.mejsr.2013.13.mae.9991">Single Polygon Counting on Cayley Tree of Order 4: Generalized Catalan Numbers</a>, Middle-East Journal of Scientific Research 13 (Mathematical Applications in Engineering): 01-05, 2013, ISSN 1990-9233.

%H Karol A. Penson and Karol Zyczkowski, <a href="http://dx.doi.org/10.1103/PhysRevE.83.061118">Product of Ginibre matrices : Fuss-Catalan and Raney distribution</a>, Phys. Rev. E 83, 061118, 15 June 2011.

%H Karol A. Penson and Karol Zyczkowski, <a href="http://arxiv.org/abs/1103.3453">Product of Ginibre matrices : Fuss-Catalan and Raney distribution</a>, arXiv:1103.3453 [math-ph], 2011.

%H Alison Schuetz and Gwyneth Whieldon, <a href="http://arxiv.org/abs/1401.7194">Polygonal Dissections and Reversions of Series</a>, arXiv:1401.7194 [math.CO], 2014.

%H B. Sury, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Sury/sury31.html">Generalized Catalan numbers: linear recursion and divisibility</a>, JIS 12 (2009), Article 09.7.5.

%H L. Takacs, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/18_1_1.pdf">Enumeration of rooted trees and forests</a>, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Fuss%E2%80%93Catalan_number">Fuss-Catalan number</a>

%H S. Yakoubov, <a href="http://arxiv.org/abs/1310.2979">Pattern Avoidance in Extensions of Comb-Like Posets</a>, arXiv preprint arXiv:1310.2979 [math.CO], 2013-2014.

%H Jian Zhou, <a href="https://arxiv.org/abs/1810.03883">Fat and Thin Emergent Geometries of Hermitian One-Matrix Models</a>, arXiv:1810.03883 [math-ph], 2018.

%F O.g.f. satisfies: A(x)= 1 + x*A(x)^4 = 1/(1-x*A(x)^3).

%F 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.

%F a(n) = upper left term in M^n, M = the production matrix:

%F 1, 1

%F 3, 3, 1

%F 6, 6, 3, 1

%F ...

%F (where 1, 3, 6, 10, ...) is the triangular series. - _Gary W. Adamson_, Jul 08 2011

%F a(n) = binomial(4*n+1, n)/(4*n+1) = A062993(n+2,2). - _Robert FERREOL_, Apr 02 2015

%F a(n) = Sum_{i=0..n-1, j=0..n-1-i, 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

%F a(n) ~ 2^(8*n+1/2) / (sqrt(Pi) * n^(3/2) * 3^(3*n+3/2)). - _Vaclav Kotesovec_, Jun 03 2015

%F From Peter Bala, Oct 16 2015: (Start)

%F A(x)^2 is o.g.f. for A069271; A(x)^3 is o.g.f. for A006632;

%F A(x)^5 is o.g.f. for A196678; A(x)^6 is o.g.f. for A006633;

%F A(x)^7 is o.g.f. for A233658; A(x)^8 is o.g.f. for A233666;

%F A(x)^9 is o.g.f. for A006634; A(x)^10 is o.g.f. for A233667. (End)

%F 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 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.

%p series(RootOf(g = 1+x*g^4, g),x=0,20); # _Mark van Hoeij_, Nov 10 2011

%p seq(binomial(4*n, n)/(3*n+1),n=0..20); # _Robert FERREOL_, Apr 02 2015

%t CoefficientList[InverseSeries[ Series[ y - y^4, {y, 0, 60}], x], x][[Range[2, 60, 3]]]

%t Table[Binomial[4n,n]/(3n+1),{n,0,25}] (* _Harvey P. Dale_, Apr 18 2011 *)

%t CoefficientList[1 + InverseSeries[Series[x/(1 + x)^4, {x, 0, 60}]], x] (* _Gheorghe Coserea_, Aug 12 2015 *)

%t terms = 22; A[_] = 0; Do[A[x_] = 1 + x*A[x]^4 + O[x]^terms, terms];

%t CoefficientList[A[x], x] (* _Jean-François Alcover_, Jan 13 2018 *)

%o (MAGMA) [ Binomial(4*n,n)/(3*n+1): n in [0..50]]; // _Vincenzo Librandi_, Apr 19 2011

%o (PARI) a(n)=binomial(4*n,n)/(3*n+1) /* _Charles R Greathouse IV_, Jun 16 2011 */

%o (PARI) my(x='x+O('x^33)); Vec(1 + serreverse(Ser(x/(1+x)^4))) \\ _Gheorghe Coserea_, Aug 12 2015

%o (Python)

%o from __future__ import division

%o A002293_list, x = , 1

%o for n in range(100):

%o x = x*4*(4*n+3)*(4*n+2)*(4*n+1)//((3*n+2)*(3*n+3)*(3*n+4))

%o A002293_list.append(x) # _Chai Wah Wu_, Feb 19 2016

%o (GAP) List([0..22],n->Binomial(4*n,n)/(3*n+1)); # _Muniru A Asiru_, Nov 01 2018

%Y Cf. A001764, A002294, A000260, A027836.

%Y Third column of triangle A062993.

%Y Cf. A006632, A006633, A006634, A069271, A196678, A233658, A233666, A233667, A277877, A283049, A283101, A283102, A283103.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_

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

Last modified October 23 16:46 EDT 2019. Contains 328373 sequences. (Running on oeis4.)