

A001764


a(n) = binomial(3*n,n)/(2*n+1) (enumerates ternary trees and also noncrossing trees).
(Formerly M2926 N1174)


356



1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715, 8414640, 50067108, 300830572, 1822766520, 11124755664, 68328754959, 422030545335, 2619631042665, 16332922290300, 102240109897695, 642312451217745, 4048514844039120, 25594403741131680, 162250238001816900
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Smallest number of straight line crossingfree spanning trees on n points in the plane.
Number of dissections of some convex polygon by nonintersecting diagonals into polygons with an odd number of sides and having a total number of 2n+1 edges (sides and diagonals).  Emeric Deutsch, Mar 06 2002
Number of lattice paths of n East steps and 2n North steps from (0,0) to (n,2n) and lying weakly below the line y=2x.  David Callan, Mar 14 2004
With interpolated zeros, this has g.f. 2*sqrt(3)*sin(arcsin(3*sqrt(3)*x/2)/3)/(3*x) and a(n) = C(n+floor(n/2),floor(n/2))*C(floor(n/2),nfloor(n/2))/(n+1). This is the first column of the inverse of the Riordan array (1x^2,x(1x^2)) (essentially reversion of yy^3).  Paul Barry, Feb 02 2005
Number of 12312avoiding matchings on [2n].
Number of complete ternary trees with n internal nodes, or 3n edges.
Number of rooted plane trees with 2n edges, where every vertex has even outdegree ("even trees").
a(n) = number of noncrossing partitions of [2n] with all blocks of even size. E.g.: a(2)=3 counts 1234, 1423, 1234.  David Callan, Mar 30 2007
PfaffFussCatalan sequence C^{m}_n for m=3, see the Graham et al. reference, p. 347. eq. 7.66.
Also 3Raney sequence, see the Graham et al. reference, p. 3467.
The number of lattice paths from (0,0) to (2n,0) using an Upstep=(1,1) and a Downstep=(0,2) and staying above the xaxis. E.g., a(2) = 3; UUUUDD, UUUDUD, UUDUUD.  Charles Moore (chamoore(AT)howard.edu), Jan 09 2008
a(n) is (conjecturally) the number of permutations of [n+1] that avoid the patterns 4231 and 42513 and end with an ascent. For example, a(4)=55 counts all 60 permutations of [5] that end with an ascent except 42315, 52314, 52413, 53412, all of which contain a 4231 pattern and 42513.  David Callan, Jul 22 2008
Central terms of pendular triangle A167763.  Philippe Deléham, Nov 12 2009
With B(x,t)=x+t*x^3, the comp. inverse in x about 0 is A(x,t) = Sum_{j>=0} a(j) (t)^j x^(2j+1). Let U(x,t)=(xA(x,t))/t. Then DU(x,t)/Dt=dU/dt+U*dU/dx=0 and U(x,0)=x^3, i.e., U is a solution of the inviscid Burgers's, or Hopf, equation. Also U(x,t)=U(xt*U(x,t),0) and dB(x,t)/dt = U(B(x,t),t) = x^3 = U(x,0). The characteristics for the Hopf equation are x(t) = x(0) + t*U(x(t),t) = x(0) + t*U(x(0),0) = x(0) + t*x(0)^3 = B(x(0),t). These results apply to all the FussCatalan sequences with 3 replaced by n>0 and 2 by n1 (e.g., A000108 with n=2 and A002293 with n=4), see also A086810, which can be generalized to A133437, for associahedra.  Tom Copeland, Feb 15 2014
a(n) = A258708(2*n,n) for n > 0.  Reinhard Zumkeller, Jun 23 2015
Number of intervals (i.e., ordered pairs (x,y) such that x<=y) in the Kreweras lattice (noncrossing partitions ordered by refinement) of size n, see the Bernardi & Bonichon (2009) and Kreweras (1972) references.  Noam Zeilberger, Jun 01 2016
Number of sumindecomposable (4231,42513)avoiding permutations. Conjecturally, number of sumindecomposable (2431,45231)avoiding permutations.  Alexander Burstein, Oct 19 2017
a(n) is the number of topologically distinct endstates for the game Planted Brussels Sprouts on n vertices, see Ji and Propp link.  Caleb Ji, May 14 2018
Number of complete quadrillages of 2n+2gons. See Baryshnikov p. 12. See also Nov. 10 2014 comments in A134264.  Tom Copeland, Jun 04 2018
a(n) is the number of 2regular words on the alphabet [n] that avoid the patterns 231 and 221. Equivalently, this is the number of 2regular tortoisesortable words on the alphabet [n] (see the Defant and Kravitz link).  Colin Defant, Sep 26 2018
a(n) is the number of Motzkin paths of length 3n with n steps of each type, with the condition that (1, 0) and (1, 1) steps alternate (starting with (1, 0)).  Helmut Prodinger, Apr 08 2019
a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the patterns 312 and 1342.  Colin Defant, Jun 08 2019
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.  Tom Copeland, Dec 13 2019
The sequences of FussCatalan numbers, of which this is the first after the Catalan numbers A000108 (the next is A002293), appear in articles on random matrices and quantum physics. See Banica et al., Collins et al., and Mlotkowski et al. Interpretations of these sequences in terms of the cardinality of specific sets of noncrossing partitions are provided by A134264.  Tom Copeland, Dec 21 2019
a(n) is the total number of down steps before the first up step in all 2_1Dyck paths of length 3*n for n > 0. A 2_1Dyck path is a lattice path with steps (1,2), (1,1) that starts and ends at y = 0 and does not go below the line y = 1.  Sarah Selkirk, May 10 2020


REFERENCES

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 23.
I. M. H. Etherington, On nonassociative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 193839), 153162.
I. M. H. Etherington, Some problems of nonassociative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. ivi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages viixiv of the same issue.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley, Reading, MA, 1990, pp. 200, 347. See also the PólyaSzegő reference.
W. Kuich, Languages and the enumeration of planted plane trees. Nederl. Akad. Wetensch. Proc. Ser. A 73 = Indag. Math. 32, (1970), 268280.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, p. 98.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, SpringerVerlag, New York, Heidelberg, Berlin, 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 13 2017]
V. E. Adler, A. B. Shabat, Volterra chain and Catalan numbers, arXiv:1810.13198 [nlin.SI], 2018.
A. Aggarwal, Armstrong's Conjecture for (k, mk+1)Core Partitions, arXiv:1407.5134 [math.CO], 2014.
O. Aichholzer and H. Krasser, The point set order type data base: a collection of applications and results, pp. 1720 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 1315, 2001.
M. H. Albert, R. E. L. Allred, M. D. Atkinson, H. P. van Ditmarsch, C. C. Handley, and D. A. Holton, Restricted permutations and queue jumping, Discrete Math. 287 (2004), 129133.
N. Alexeev and A. Tikhomirov, Singular Values Distribution of Squares of Elliptic Random Matrices and typeB Narayana Polynomials, arXiv:1501.04615 [math.PR], 2015.
N. V. Alexeev, Number of trees in a random graph, Probabilistic methods in discrete mathematics, Extended abstracts of the 10th International Petrozavodsk Conference (Russia, 2019), 1213. (in Russian)
M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007), 93102, Theorem 6.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 337338.
Joerg Arndt, Subsetlex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014.
A. Asinowski, B. Hackl, and S. Selkirk, Down step statistics in generalized Dyck paths, arXiv:2007.15562 [math.CO], 2020.
JeanChristophe Aval, Multivariate FussCatalan numbers, arXiv:0711.0906 [math.CO], 2007.
JeanChristophe Aval, Multivariate FussCatalan numbers, Discrete Math., 308 (2008), 46604669.
I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765785.
P. Balduf, The propagator and diffeomorphisms of an interacting field theory, Master's thesis, submitted to the Institut für Physik, MathematischNaturwissenschaftliche Fakultät, HumboldtUniverstität, Berlin, 2018.
Christian Ballot, Lucasnomial FussCatalan Numbers and Related Divisibility Questions, J. Int. Seq., 21 (2018), Article 18.6.5.
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.
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
T. Banica, S. Belinschi, M. Capitaine, and B. Collins, Free Bessel laws, arXiv:0710.5931 [math.PR], 2008.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016), 343385.
Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Y. Baryshnikov, On Stokes sets, New developments in singularity theory (Cambridge, 2000): 6586. Kluwer Acad. Publ., Dordrecht, 2001.
L. W. Beineke and R. E. Pippert, Enumerating labeled kdimensional trees and ball dissections, pp. 1226 of Proceedings of Second Chapel Hill Conference on Combinatorial Mathematics and Its Applications, University of North Carolina, Chapel Hill, 1970. Reprinted in Math. Annalen, 191 (1971), 8798.
L. W. Beineke and R. E. Pippert, Enumerating dissectable polyhedra by their automorphism groups, Canad. J. Math., 26 (1974), 5067.
Francois Bergeron, Combinatorics of rDyck paths, rParking functions, and the rTamari lattices, arXiv:1202.6269 [math.CO], 2012.
Olivier Bernardi and Nicolas Bonichon, Intervals in Catalan lattices and realizers of triangulations, Journal of Combinatorial Theory, Series A 116:1 (2009), pp. 5575. See also Bernardi's slides, Catalan lattices and realizers of triangulations (April 2007).
D. Bevan, D. Levin, P. Nugent, J. Pantone, and L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv:1510:08036 [math.CO], 2015.
D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv:1503.05242 [math.CO], 2015.
Michel Bousquet and Cédric Lamathe, On symmetric structures of order two, Discrete Math. Theor. Comput. Sci. 10 (2008), 153176.
M. BousquetMélou and M. Petkovšek, Walks confined in a quadrant are not always Dfinite, arXiv:math/0211432 [math.CO], 2002.
Włodzimierz Bryc, Raouf Fakhfakh, and Wojciech Młotkowski, CauchyStieltjes families with polynomial variance functions and generalized orthogonality, arXiv:1708.05343 [math.PR], 20172019. Also in Probability and Mathematical Statistics 39(2) (2019), 237258.
N. T. Cameron, Random walks, trees and extensions of Riordan group techniques, Dissertation, Howard University, 2002.
Naiomi Cameron and J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
L. Carlitz, Enumeration of twoline arrays, Fib. Quart., 11(2) (1973), 113130.
F. Cazals, Combinatorics of NonCrossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns, arXiv:math/0504342 [math.CO], 2005.
J. Cigler, Some remarks about qChebyshev polynomials and qCatalan numbers and related results, arXiv:1312.2767 [math.CO], 2013.
B. Collins, I. Nechita, and K. Zyczkowski, Random graph states, maximal flow and FussCatalan distributions, arXiv:1003.3075 [quantph], 2010.
T. C. Copeland, Compositional inverse pairs, the BurgersHopf equation, and the Stasheff associahedra, 2014.
T. C. Copeland, Discriminating Deltas, Depressed Equations, and Generalized Catalan Numbers, 2012.
S. J. Cyvin, Jianji Wang, J. Brunvoll, Shiming Cao, Ying Li, B. N. Cyvin, and Yugang Wang, Staggered conformers of alkanes: complete solution of the enumeration problem, J. Molec. Struct. 413414 (1997), 227239.
S. J. Cyvin et al., Enumeration of staggered conformers of alkanes and monocyclic cycloalkanes, J. Molec. Struct., 445 (1998), 12713.
Colin Defant, Catalan Intervals and Uniquely Sorted Permutations, arXiv:1904.02627 [math.CO], 2019.
C. Defant and N. Kravitz, Stacksorting for words, arXiv:1809.09158 [math.CO], 2018.
E. Deutsch, S. Feretic and M. Noy, Diagonally convex directed polyominoes and even trees: a bijection and related issues, Discrete Math., 256 (2002), 645654.
S. Dulucq, Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy)
Jins de Jong, Alexander Hock, and Raimar Wulkenhaar, Catalan tables and a recursion relation in noncommutative quantum field theory, arXiv:1904.11231 [mathph], 2019.
E. Deutsch and M. Noy, Statistics on noncrossing trees, Discrete Math., 254 (2002), 7587.
R. Dickau, FussCatalan Numbers. Figures of various interpretations.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341358.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341358. (Annotated scanned copy)
C. Domb and A. J. Barrett, Notes on Table 2 in "Enumeration of ladder graphs", Discrete Math. 9 (1974), 55. (Annotated scanned copy)
J. A. Eidswick, Short factorizations of permutations into transpositions, Disc. Math. 73 (1989) 239243
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.
I. M. H. Etherington, Nonassociate powers and a functional equation, Math. Gaz. 21 (1937), 3639; addendum 21 (1937), 153.
I. M. H. Etherington, Some problems of nonassociative combinations, Edinburgh Math. Notes, 32 (1940), 16.
I. M. H. Etherington, Some problems of nonassociative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. ivi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and it is on pages viixiv of the same issue.
Jishe Feng, The Hessenberg matrices and Catalan and its generalized numbers, arXiv:1810.09170 [math.CO], 2018. See p. 4.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486.
N. Gabriel, K. Peske, L. Pudwell, and S. Tay, Pattern Avoidance in Ternary Trees, J. Int. Seq. 15 (2012), #12.1.5
I. Gessel and G. Xin, The generating function of ternary trees and continued fractions, arXiv:math/0505217 [math.CO], 2005.
S. Goldstein, J. L. Lebowitz, E. R. Speer, The DiscreteTime Facilitated Totally Asymmetric Simple Exclusion Process, arXiv:2003.04995 [mathph], 2020.
N. S. S. Gu, N. Y. Li and T. Mansour, 2Binary trees: bijections and related issues, Discr. Math., 308 (2008), 12091221.
Nancy S.S. Gu and Helmut Prodinger, A bijection between two subfamilies of Motzkin paths, arXiv:2007.02142 [math.CO], 2020.
F. Harary, E. M. Palmer, R. C. Read, On the cellgrowth problem for arbitrary polygons, computer printout, circa 1974
T.X. He, L. W. Shapiro, FussCatalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Lin. Alg. Applic. 532 (2017) 2541, FussCatalan Number (F_3)_n
V. E. Hoggatt, Jr., Letters to N. J. A. Sloane, 19741975.
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.
Vera M. Hur, M. A. Johnson, and J. L. Martin, Oscillation estimates of eigenfunctions via the combinatorics of noncrossing partitions, arXiv:1609.02189 [math.SP], 2016.
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.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 53.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 285.
C. Ji and J. Propp, Brussels Sprouts, Noncrossing Trees, and Parking Functions, arXiv:1805.03608 [math.CO], 2018.
J. Jong, A. Hock, and R. Wulkenhaar Catalan tables and a recursion relation in noncommutative quantum field theory, arXiv:1904.11231 [mathph], 2019.
A. V. Kitaev, Meromorphic Solution of the Degenerate Third Painlevé Equation Vanishing at the Origin, arXiv:1809.00122 [math.CA], 2018.
S. Kitaev and A. de Mier, Enumeration of fixed points of an involution on beta(1, 0)trees, arXiv:1210.2618 [math.CO], 2012.
Don Knuth, 20th Anniversary Christmas Tree Lecture.
G. Kreweras, Sur les partitions non croisées d'un cycle, (French) Discrete Math. 1(4) (1972), 333350. MR0309747 (46 #8852).
D. V. Kruchinin, On solving some functional equations, Advances in Difference Equations (2015), 2015:17.
Dmitry V. Kruchinin and Vladimir V. Kruchinin, A Generating Function for the Diagonal T_{2n,n} in Triangles, Journal of Integer Sequences, 18 (2015), Article 15.4.6.
Markus Kuba and Alois Panholzer, Enumeration formulas for pattern restricted Stirling permutations, Discrete Math. 312(21) (2012), 31793194. MR2957938.  From N. J. A. Sloane, Sep 25 2012
Woldieter Lang, Ternary trees with n = 1, 2, 3 and 4 vertices.
HoHon Leung, Thotsaporn "Aek" Thanatipanonda, A Probabilistic TwoPile Game, arXiv:1903.03274 [math.CO], 2019.
R. P. Loh, A. G. Shannon, and A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, preprint, 1980.
Lun Lv and Sabrina X.M. Pang, Reduced Decompositions of Matchings, Electronic Journal of Combinatorics 18 (2011), #P107.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307344, (T_n for s=3).
W. Mlotkowski, M. Nowak, K. Penson, and K. Zyczkowski, Spectral density of generalized Wishart matrices and free multiplicative convolution, arXiv preprint arXiv:1407.1282 [mathph], 2015.
W. Mlotkowski and K. A. Penson, The probability measure corresponding to 2plane trees, arXiv:1304.6544 [math.PR], 2013.
Hanna Mularczyk, Lattice Paths and PatternAvoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
Emanuele Munarini, Shifting Property for Riordan, Sheffer and Connection Constants Matrices, Journal of Integer Sequences, 20 (2017), Article 17.8.2.
H. Niederhausen, Catalan Traffic at the Beach, Electronic Journal of Combinatorics, 9 (2002), #R33.
J.C. Novelli, J.Y. Thibon, Hopf Algebras of mpermutations,(m+1)ary trees, and mparking functions, arXiv:1403.5962 [math.CO], 2014.
M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180 (1998), 301313.
A. Panholzer and H. Prodinger, Bijections for ternary trees and noncrossing trees, Discrete Math., 250 (2002), 181195.
K. A. Penson and A. I. Solomon, Coherent states from combinatorial sequences, arXiv:quantph/0111151, 2001.
K. H. Pilehrood and T. H. Pilehrood, Jacobi Polynomials and Congruences Involving Some HigherOrder Catalan Numbers and Binomial Coefficients, J. Int. Seq. 18 (2015), #15.11.7.
Helmut Prodinger, A simple bijection between a subclass of 2binary trees and ternary trees, Discrete Mathematics 309(4) (2009), 959961.
Helmut Prodinger, Generating functions for a lattice path model introduced by Deutsch, arXiv:2004.04215 [math.CO], 2020.
H. Prodinger, S. J. Selkirk, and S. Wagner, On two subclasses of Motzkin paths and their relation to ternary trees, arXiv:1902.01681 [math.CO], 2019; in: Algorithmic Combinatorics  Enumerative Combinatorics, Special Functions and Computer Algebra, Springer. To appear.
Jocelyn Quaintance, Combinatoric Enumeration of TwoDimensional Proper Arrays, Discrete Math., 307 (2007), 18441864.
J. Riordan, Letter, Jul 06 1978.
B. Rittaud, On the Average Growth of Random Fibonacci Sequences, Journal of Integer Sequences, 10 (2007), Article 07.2.4.
A. Schuetz and G. Whieldon, Polygonal Dissections and Reversions of Series, arXiv:1401.7194 [math.CO], 2014.
Makoto Sekiyama, Toshiya Ohtsuki, and Hiroshi Yamamoto, Analytical Solution of Smoluchowski Equations in AggregationFragmentation Processes, Journal of the Physical Society of Japan, 86.10, id 104003 (2017).
M. Somos, Number Walls in Combinatorics.
B. Sury, Generalized Catalan numbers: linear recursion and divisibility, JIS 12 (2009), #09.7.5
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 110, esp. Eq. (5).
S. Yakoubov, Pattern Avoidance in Extensions of CombLike Posets, arXiv:1310.2979 [math.CO], 2013.
ShengLiang Yang, L.J. Wang, Taylor expansions for the mCatalan numbers, Australasian Journal of Combinatorics, 64(3) (2016), 420431.
Anssi YliJyra, On Dependency Analysis via Contractions and Weighted FSTs, in Shall We Play the Festschrift Game?, Springer, 2012, pp. 133158.
S.n. Zheng and S.l. Yang, On theShifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.
Jian Zhou, Fat and Thin Emergent Geometries of Hermitian OneMatrix Models, arXiv:1810.03883 [mathph], 2018.
Index entries for "core" sequences
Index entries for sequences related to trees


FORMULA

From Karol A. Penson, Nov 08 2001: (Start)
G.f.: (2/sqrt(3*x))*sin((1/3)*arcsin(sqrt(27*x/4))).
E.g.f.: hypergeom([1/3, 2/3], [1, 3/2], 27/4*x).
Integral representation as nth moment of a positive function on [0, 27/4]: a(n) = Integral_{x=0..6.75} (x^n*((1/12) * 3^(1/2) * 2^(1/3) * (2^(1/3)*(27 + 3 * sqrt(81  12*x))^(2/3)  6 * x^(1/3))/(Pi * x^(2/3)*(27 + 3 * sqrt(81  12*x))^(1/3)))), n >= 0. This representation is unique. (End)
G.f. A(x) satisfies A(x) = 1+x*A(x)^3 = 1/(1x*A(x)^2) [Cyvin (1998)].  Ralf Stephan, Jun 30 2003
a(n) = nth coefficient in expansion of power series P(n), where P(0) = 1, P(k+1) = 1/(1  x*P(k)^2).
G.f. Rev(x/c(x))/x, where c(x) is the g.f. of A000108 (Rev=reversion of).  Paul Barry, Mar 26 2010
From Gary W. Adamson, Jul 07 2011: (Start)
Let M = the production matrix:
1, 1
2, 2, 1
3, 3, 2, 1
4, 4, 3, 2, 1
5, 5, 4, 3, 2, 1
...
a(n) = upper left term in M^n. Top row terms of M^n = (n+1)th row of triangle A143603, with top row sums generating A006013: (1, 2, 7, 30, 143, 728, ...). (End)
Recurrence: a(0)=1; a(n) = Sum_{i=0..n1, j=0..n1i} a(i)a(j)a(n1ij) for n >= 1 (counts ternary trees by subtrees of the root).  David Callan, Nov 21 2011
G.f.: 1 + 6*x/(Q(0)  6*x); Q(k) = 3*x*(3*k + 1)*(3*k + 2) + 2*(2*(k^2) + 5*k +3)  6*x*(2*(k^2) + 5*k + 3)*(3*k + 4)*(3*k + 5)/Q(k+1); (continued fraction).  Sergei N. Gladkovskii, Nov 27 2011
Dfinite with recurrence: 2*n*(2n+1)*a(n)  3*(3n1)*(3n2)*a(n1) = 0.  R. J. Mathar, Dec 14 2011
REVERT transform of A115140. BINOMIAL transform is A188687. SUMADJ transform of A188678. HANKEL transform is A051255. INVERT transform of A023053. INVERT transform is A098746.  Michael Somos, Apr 07 2012
(n + 1) * a(n) = A174687(n).
G.f.: F([2/3,4/3], [3/2], 27/4*x) / F([2/3,1/3], [1/2], 27/4*x) where F() is the hypergeometric function.  Joerg Arndt, Sep 01 2012
a(n) = binomial(3*n+1, n)/(3*n+1) = A062993(n+1,1).  Robert FERREOL, Apr 03 2015
0 = a(n)*(3188646*a(n+2) + 20312856*a(n+3)  11379609*a(n+4) + 1437501*a(n+5)) + a(n+1)*(177147*a(n+2)  2247831*a(n+3) + 1638648*a(n+4)  238604*a(n+5)) + a(n+2)*(243*a(n+2) + 31497*a(n+3)  43732*a(n+4) + 8288*a(n+5)) for all integer n.  Michael Somos, Jun 03 2016
a(n) ~ 3^(3*n + 1/2)/(sqrt(Pi)*4^(n+1)*n^(3/2)).  Ilya Gutkovskiy, Nov 21 2016
Given g.f. A(x), then A(1/8) = 1 + sqrt(5), A(2/27) = (1 + sqrt(3))*3/2, A(4/27) = 3/2, A(3/64) = 2 + 2*sqrt(7/3), A(5/64) = (1 + sqrt(5))*2/sqrt(5), etc. A(n^2/(n+1)^3) = (n+1)/n if n > 1.  Michael Somos, Jul 17 2018


EXAMPLE

a(2) = 3 because the only dissections with 5 edges are given by a square dissected by any of the two diagonals and the pentagon with no dissecting diagonal.
G.f. = 1 + x + 3*x^2 + 12*x^3 + 55*x^4 + 273*x^5 + 1428*x^6 + 7752*x^7 + 43263*x^8 + ...


MAPLE

A001764 := n>binomial(3*n, n)/(2*n+1): seq(A001764(n), n=0..25);
with(combstruct): BB:=[T, {T=Prod(Z, F), F=Sequence(B), B=Prod(F, Z, F)}, unlabeled]:seq(count(BB, size=i), i=0..22); # Zerinvary Lajos, Apr 22 2007
with(combstruct):BB:=[S, {B = Prod(S, S, Z), S = Sequence(B)}, labelled]: seq(count(BB, size=n)/n!, n=0..21); # Zerinvary Lajos, Apr 25 2008
n:=30:G:=series(RootOf(g = 1+x*g^3, g), x=0, n+1):seq(coeff(G, x, k), k=0..n); # Robert FERREOL, Apr 03 2015


MATHEMATICA

InverseSeries[Series[yy^3, {y, 0, 24}], x] (* then a(n)=y(2n+1)=ways to place noncrossing diagonals in convex (2n+4)gon so as to create only quadrilateral tiles *) (* Len Smiley, Apr 08 2000 *)
Table[Binomial[3n, n]/(2n+1), {n, 0, 25}] (* Harvey P. Dale, Jul 24 2011 *)


PROG

(PARI) {a(n) = if( n<0, 0, (3*n)! / n! / (2*n + 1)!)};
(PARI) {a(n) = if( n<0, 0, polcoeff( serreverse( x  x^3 + O(x^(2*n + 2))), 2*n + 1))};
(PARI) {a(n) = my(A); if( n<0, 0, A = 1 + O(x); for( m=1, n, A = 1 + x * A^3); polcoeff(A, n))};
(PARI) b=vector(22); b[1]=1; for(n=2, 22, for(i=1, n1, for(j=1, n1, for(k=1, n1, if((i1)+(j1)+(k1)(n2), NULL, b[n]=b[n]+b[i]*b[j]*b[k]))))); a(n)=b[n+1]; print1(a(0)); for(n=1, 21, print1(", ", a(n))) \\ Gerald McGarvey, Oct 08 2008
(PARI) Vec(1 + serreverse(x / (1+x)^3 + O(x^30))) \\ Gheorghe Coserea, Aug 05 2015
(Sage)
def A001764_list(n) :
D = [0]*(n+1); D[1] = 1
R = []; b = false; h = 1
for i in range(2*n) :
for k in (1..h) : D[k] += D[k1]
if not b : R.append(D[h])
else : h += 1
b = not b
return R
A001764_list(22) # Peter Luschny, May 03 2012
(MAGMA) [Binomial(3*n, n)/(2*n+1): n in [0..30]]; // Vincenzo Librandi, Sep 04 2014
(Haskell)
a001764 n = a001764_list !! n
a001764_list = 1 : [a258708 (2 * n) n  n < [1..]]
 Reinhard Zumkeller, Jun 23 2015
(GAP) List([0..25], n>Binomial(3*n, n)/(2*n+1)); # Muniru A Asiru, Oct 31 2018


CROSSREFS

Cf. A000108, A001762, A001763, A002293, A006013, A063548, A064017, A072247, A072248, A134264, A143603, A258708, A256311.
A column of triangle A102537.
Bisection of A047749 and A047761.
Row sums of triangle A108410.
Second column of triangle A062993.
Mod 3 = A113047.
Sequence in context: A024038 A007199 A179848 * A171780 A216493 A216494
Adjacent sequences: A001761 A001762 A001763 * A001765 A001766 A001767


KEYWORD

easy,nonn,nice,core


AUTHOR

N. J. A. Sloane


STATUS

approved



