

A002293


Number of dissections of a polygon: binomial(4*n, n)/(3*n + 1).
(Formerly M3587 N1454)


148



1, 1, 4, 22, 140, 969, 7084, 53820, 420732, 3362260, 27343888, 225568798, 1882933364, 15875338990, 134993766600, 1156393243320, 9969937491420, 86445222719724, 753310723010608, 6594154339031800, 57956002331347120, 511238042454541545
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The number of rooted loopless nedge maps in the plane (planar with a distinguished outside face).  Valery A. Liskovets, Mar 17 2005
Number of lattice paths from (1,0) to (3*n+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/3)*x (i.e., if (a,b) is in the path, then b < a/3).  Joseph Cooper (jecooper(AT)mit.edu), Feb 07 2006
Number of lengthn restricted growth strings (RGS) [s(0), s(1), ..., s(n1)] where s(0) = 0 and s(k) <= s(k1) + 3, see fxtbook link below.  Joerg Arndt, Apr 08 2011
From Wolfdieter Lang, Sep 14 2007: (Start)
a(n), n >= 1, enumerates quartic trees (rooted, ordered, incomplete) with n vertices (including the root).
PfaffFussCatalan sequence C^{m}_n for m = 4. See the Graham et al. reference, p. 347. eq. 7.66. See also the PólyaSzegő reference.
Also 4Raney sequence. See the Graham et al. reference, pp. 346347.
(End)
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
From Karol A. Penson, Apr 02 2010: (Start)
Integral representation as nth Hausdorff power moment of a positive function on the interval [0, 256/27], in Maple notation:
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.
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)
O.g.f. satisfies g = 1+x*g^4. If h is the series reversion of x*g, so h(x*g)=x, then (xh(x))/x^2 is the o.g.f. of A006013.  Mark van Hoeij, Nov 10 2011
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
For a relation to the inviscid Burgers's equation, see A001764.  Tom Copeland, Feb 15 2014
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 (See also Gross et al. in A062994.  Tom Copeland, Dec 24 2019)
This is the number of A'Campo bicolored forests of degree n and codimension 0. This can be shown using generating functions or a combinatorial approach. See Combe and Jugé link below.  Noemie Combe, Feb 28 2017
Conjecturally, a(n) is the number of 3uniform words over the alphabet [n] that avoid the patterns 231 and 221 (see the Defant and Kravitz link).  Colin Defant, Sep 26 2018
The compositional inverse o.g.f. pair in Copeland's comment above are related to a pair of quantum fields in Balduf's thesis by Theorem 4.2 on p. 92. Cf. A001764.  Tom Copeland, Dec 13 2019
a(n) is the total number of down steps before the first up step in all 3_1Dyck paths of length 4*n. A 3_1Dyck path is a lattice path with steps (1, 3), (1, 1) that starts and ends at y = 0 and stays above the line y = 1.  Sarah Selkirk, May 10 2020


REFERENCES

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 23.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley, Reading, MA, 1990, pp. 200, 347.
Peter Hilton and Jean Pedersen, Catalan numbers, their generalization, and their uses, Math. Intelligencer 13 (1991), no. 2, 6475.
V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 200501, Montreal, Canada, 2005.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, SpringerVerlag, 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.
M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007) 93102, Theor. 6
T. Anderson, T. B. McLean, H. Pajoohesh, C. Smith, The combinatorics of all regular flexagons, Eu. J. Combinat. 31 (2010) 7280, Theorem 2.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 337338
Joerg Arndt, Subsetlex: did we miss an order?, arXiv:1405.6503 [math.CO], 20142015.
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, MathematischNaturwissenschaftliche Fakultät, HumboldtUniverstät, Berlin, 2018.
C. Banderier, M. BousquetMélou, A. Denise, P. Flajolet, D. Gardy and D. GouyouBeauchamps, Generating Functions for Generating Trees, Discrete Mathematics, 246(13) (2002), 2955.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226228 (1995), 5772; erratum 320 (2000), 210.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226228 (1995), 5772; 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), 153176.
T. Daniel Brennan, Christian Ferko, and Savdeep Sethi, A NonAbelian Analogue of DBI from T₸, arXiv:1912.12389 [hepth], 2019. See also SciPost Phys. Vol. 8 (2020), 052.
WunSeng Chou, TianXiao He, and Peter J.S. Shiue, On the Primality of the Generalized FussCatalan Numbers, J. Int. Seqs., 21 (2018), #18.2.1.
J. Cigler, Some remarks about qChebyshev polynomials and qCatalan numbers and related results, 2013.
N. Combe and V. Jugé, Counting bicolored A'Campo forests, arXiv:1702.07672 [math.AG], 2017.
T. Copeland, Discriminating Deltas, Depressed Equations, and Generalized Catalan Numbers, 2012.
C. Defant and N. Kravitz, Stacksorting 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 StromingerYauZaslow conjecture, arXiv:1212.4220 [math.AG], p. 58, 2013.
F. Harary, E. M. Palmer, and R. C. Read, On the cellgrowth problem for arbitrary polygons, computer printout, circa 1974.
F. Harary, E. M. Palmer and R. C. Read, On the cellgrowth problem for arbitrary polygons, Discr. Math. 11 (1975), 371389.
V. E. Hoggatt, Jr., 7page 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), 395405.
HsienKuei Hwang, Mihyun Kang, and GuanHuei Duh, Asymptotic Expansions for SubCritical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss DagstuhlLeibnizZentrum für Informatik, 2018.
Ionut E. Iacob, T. Bruce McLean and Hua Wang, The Vflex, Triangle Orientation, and Catalan Numbers in Hexaflexagons, The College Mathematics Journal, Vol. 43, No. 1 (January 2012), pp. 610.
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), 364387.
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), 307344 (T_n for s=4).
Henri Muehle, Philippe Nadeau, A Poset Structure on the Alternating Group Generated by 3Cycles, arXiv:1803.00540 [math.CO], 2018.
J.C. Novelli and J.Y. Thibon, Hopf Algebras of mpermutations,(m+1)ary trees, and mparking functions, arXiv:1403.5962 [math.CO], 2014.
C. O. Oakley, R. J. Wisner, Flexagons, Am. Math. Monthly 64 (3) (1957) 143154, u_{3k+1}
C. B. Pah and M. Saburov, Single Polygon Counting on Cayley Tree of Order 4: Generalized Catalan Numbers, MiddleEast Journal of Scientific Research 13 (Mathematical Applications in Engineering): 0105, 2013, ISSN 19909233.
Karol A. Penson and Karol Zyczkowski, Product of Ginibre matrices : FussCatalan and Raney distribution, Phys. Rev. E 83, 061118, 15 June 2011.
Karol A. Penson and Karol Zyczkowski, Product of Ginibre matrices : FussCatalan and Raney distribution, arXiv:1103.3453 [mathph], 2011.
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), 110, esp. Eq. (5).
Wikipedia, FussCatalan number
S. Yakoubov, Pattern Avoidance in Extensions of CombLike Posets, arXiv:1310.2979 [math.CO], 20132014.
Jian Zhou, Fat and Thin Emergent Geometries of Hermitian OneMatrix Models, arXiv:1810.03883 [mathph], 2018.


FORMULA

O.g.f. satisfies: A(x) = 1 + x*A(x)^4 = 1/(1  x*A(x)^3).
a(n) = binomial(4*n,n1)/n, n >= 1, a(0) = 1. From the Lagrange series of the o.g.f. A(x) with its above given implicit equation.
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
a(n) = binomial(4*n+1, n)/(4*n+1) = A062993(n+2,2).  Robert FERREOL, Apr 02 2015
a(n) = Sum_{i=0..n1} Sum_{j=0..n1i} Sum_{k=0..n1ij} a(i)*a(j)*a(k)*a(n1ijk) 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)
A(x)^2 is o.g.f. for A069271; A(x)^3 is o.g.f. for A006632;
A(x)^5 is o.g.f. for A196678; A(x)^6 is o.g.f. for A006633;
A(x)^7 is o.g.f. for A233658; A(x)^8 is o.g.f. for A233666;
A(x)^9 is o.g.f. for A006634; A(x)^10 is o.g.f. for A233667. (End)
Dfinite 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


EXAMPLE

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.


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


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] (* JeanFrançois Alcover, Jan 13 2018 *)


PROG

(MAGMA) [ Binomial(4*n, n)/(3*n+1): n in [0..50]]; // Vincenzo Librandi, Apr 19 2011
(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(Ser(x/(1+x)^4))) \\ Gheorghe Coserea, Aug 12 2015
(Python)
from __future__ import division
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
(GAP) List([0..22], n>Binomial(4*n, n)/(3*n+1)); # Muniru A Asiru, Nov 01 2018


CROSSREFS

Column k=3 of triangle A062993 and A070914.
Cf. A001764, A002294, A000260, A027836, A062994.
Cf. A006632, A006633, A006634, A069271, A196678, A233658, A233666, A233667, A277877, A283049, A283101, A283102, A283103.
Sequence in context: A325453 A216712 A240586 * A181784 A003287 A077056
Adjacent sequences: A002290 A002291 A002292 * A002294 A002295 A002296


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


STATUS

approved



