0,3

The solution to Schroeder's first problem. A very large number of combinatorial interpretations are known - see references, esp. Stanley, Enumerative Combinatorics, Volume 2.

Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g. for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).

Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths which never go never below the x-axis is C(n) [Chung-Feller]

a(n) is the number of ordered rooted trees with n nodes, not including the root. See the Conway-Guy reference where these rooted ordered trees are called plane bushes. See also the Bergeron et al. reference, Example 4, p. 167. W. Lang Aug 07 2007.

Shifts one place left when convolved with itself.

For n >= 1 a(n) is also the number of rooted bicolored unicellular maps of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 15 2001

Ways of joining 2n points on a circle to form n nonintersecting chords. (If no such restriction imposed, then ways of forming n chords is given by (2n-1)!!=(2n)!/n!2^n=A001147(n).)

Arises in Schubert calculus - see Sottile reference.

Inverse Euler transform of sequence is A022553.

With interpolated zeros, the inverse binomial transform of the Motzkin numbers A001006. - Paul Barry (pbarry(AT)wit.ie), Jul 18 2003

The Hankel transforms of this sequence or of this sequence with the first term omitted give A000012 = 1, 1, 1, 1, 1, 1, ...; example : Det([1, 1, 2, 5; 1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132]) = 1 and Det([1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132; 14, 42, 132, 429]) = 1 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Mar 04 2004

c(n) = C(2*n-2,n-1)/n = (1/n!) * [ n^(n-1) + { C(n-2,1) +C(n-2,2) }*n^(n-2) + { 2*C(n-3,1) +7*C(n-3,2) +8*C(n-3,3) +3*C(n-3,4) }*n^(n-3) + { 6*C(n-4,1) +38*C(n-4,2) +93*C(n-4,3) +111*C(n-4,4) +65*C(n-4,5) +15*C(n-4,6) }*n^(n-4) + ..... ]. - Andre F. Labossiere (boronali(AT)laposte.net), Nov 10 2004

Sum_{n=0..infinity} 1/a(n) = 2 + 4*Pi/3^(5/2) = F(1,2;1/2;1/4) = 2.806133050770763... (see L'Universe de Pi link) - Gerald McGarvey and Benoit Cloitre, Feb 13 2005

a(n) equals sum of squares of terms in row n of triangle A053121, which is formed from successive self-convolutions of the Catalan sequence. - Paul D. Hanna (pauldhanna(AT)juno.com), Apr 23 2005

Comment from Donald D. Cross (cosinekitty(AT)hotmail.com), Feb 04 2005: Also coefficients of the Mandelbrot polynomial M iterated an infinite number of times. Examples: M(0) = 0 = 0*c^0 = [0], M(1) = c = c^1 + 0*c^0 = [1 0], M(2) = c^2 + c = c^2 + c^1 + 0*c^0 = [1 1 0], M(3) = (c^2 + c)^2 + c = [0 1 1 2 1], ... ... M(5) = [0 1 1 2 5 14 26 44 69 94 114 116 94 60 28 8 1], ...

The multiplicity with which a prime p divides C_n can be determined by first expressing n+1 in base p. For p=2, the multiplicity is the number of 1 digits minus 1. For p an odd prime, count all digits greater than (p+1)/2; also count digits equal to (p+1)/2 unless final; and count digits equal to (p-1)/2 if not final and the next digit is counted. For example, n=62, n+1 = 223_5, so C_62 is not divisible by 5. n=63, n+1 = 224_5, so 5^3 | C_63. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Feb 08 2006

Koshy and Salmassi give an elementary proof that the only prime Catalan numbers are a(2) = 2 and a(3) = 5. Is the only semiprime Catalan number a(4) = 14? - Jonathan Vos Post (jvospost3(AT)gmail.com), Mar 06 2006

Comment from Franklin T. Adams-Watters, Apr 14 2006: The answer is yes. Using the formula C_n = C(2n,n)/(n+1), it is immediately clear that C_n can have no prime factor greater than 2n. For n >= 7, C_n > (2n)^2, so it cannot be a semiprime. Given that the Catalan numbers grow exponentially, the above consideration implies that the number of prime divisors of C_n, counted with multiplicity, must grow without limit. The number of distinct prime divisors must also grow without limit, but this is more difficult. Any prime between n+1 and 2n (exclusive) must divide C_n. That the number of such primes grows without limit follows from the prime number theorem.

The number of ways to place n indistinguishable balls in n numbered boxes B1,...,Bn such that at most a total of k balls are placed in boxes B1,...,Bk for k=1,...,n. For example, a(3)=5 since there are 5 ways to distribute 3 balls among 3 boxes such that (i) box 1 gets at most 1 ball and (ii)box 1 and box 2 together get at most 2 balls:(O)(O)(O), (O)()(OO), ()(OO)(O), ()(O)(OO), ()()(OOO). - Dennis P. Walsh (dwalsh(AT)mtsu.edu), Dec 04 2006

a(n) is also the order of the semigroup of order-decreasing and order-preserving full transformations (of an n-element chain) - now known as the Catalan monoid [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

a(n) is the number of trivial representations in the direct product of 2n spinor (the smallest) representations of the group SU(2) (A(1)). [From Rutger Boels (boels(AT)nbi.dk), Aug 26 2008]

The invert transform appears to converge to the catalan numbers when applied infinitely many times to any starting sequence. [From Mats O. Granvik, Gary W. Adamson and Roger L. Bagula (mgranvik(AT)abo.fi), Sep 09 2008, Sep 12 2008]

lim(a(n)/a(n-1): n->infinity) = 4 [From Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008]

Starting with offset 1 = row sums of triangle A154559 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 11 2009]

Contribution from Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009: (Start)

C(n) is the degree of the Grassmanian G(1,n+1): the set of lines in

(n+1)-dimensional projective space, or the set of planes through the origin in

(n+2)-dimensional affine space. The Grassmanian is considered a subset of

N-dimensional projective space, N = binomial(n+2,2) - 1. If we choose 2n

general (n-1)-planes in projective (n+1)-space, then there are C(n) lines that

meet all of them. (End)

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 01 2009: (Start)

Starting with offset 1 = A068875: (1, 2, 4, 10, 18, 84,...) convolved with

Fine numbers, A000957: (1, 0, 1, 2, 6, 18,...). a(6) = 132 =

(1, 2, 4, 10, 28, 84) dot (18, 6, 2, 1, 0, 1) = (18 + 12 + 8 + 10 + 0 + 84) = 132. (End)

Convolved with A032443: (1, 3, 11, 42, 163,...) = powers of 4, A000302: (1, 4, 16,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 15 2009]

Sum{k=1...Infinity,c(k-1)/2^(2k-1)}=1. The kth term in the summation is the probability that a random walk on the integers (begining at the origin) will arrive at positive one (for the first time) in exactly (2k-1) steps. [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Sep 12 2009]

The large number of references and links demonstrates the ubiquity of the Catalan numbers.

R. Alter, Some remarks and results on Catalan numbers, pp. 109-132 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 2, edited R. C. Mullin et al., 1971.

R. Alter and K. K. Kubota, Prime and prime power divisibility of Catalan numbers, J. Combinatorial Theory, Ser. A, 15 (1973), 243-256.

D. F. Bailey, Counting Arrangements of 1's and -1's, Mathematics Magazine 69(2) 128-131 1996.

I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences, Discrete Mathematics and Theoretical Computer Science 4, 2000, 31-44.

E. Barcucci, A. Frosini and S. Rinaldi, On directed-convex polyominoes in a rectangle, Discr. Math., 298 (2005). 62-78.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-like Structures, EMA vol.67, Cambridge, 1998, p. 163, 167, 168, 252, 256, 291.

F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.

A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, preprint, 2007.

M. Bona and B. E. Sagan, On Divisibility of Narayana Numbers by Primes, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.4.

W. G. Brown, Historical note on a recurrent combinatorial problem, Amer. Math. Monthly, 72 (1965), 973-977.

D. Callan, A combinatorial interpretation of a Catalan numbers identity, Math. Mag., 72 (1999), 295-298.

D. Callan, The maximum associativeness of division, Problem 11091, Amer. Math. Monthly, 113 (#5, 2006), 462-463.

David Callan, A Combinatorial Interpretation for a Super-Catalan Recurrence, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.8.

David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.

Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

Chung, Kai Lai; Feller, W., On fluctuations in coin-tossing. Proc. Nat. Acad. Sci. U. S. A. 35, (1949). 605-608.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 53.

J. H. Conway and R. K. Guy, The Book of Numbers, New York: Springer-Verlag, 1995, ch. 4, pp 96-106.

S. J. Cyvin and I. Gutman, Kekule structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see pp. 183, 196, etc.).

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 167-202, 1999.

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001.

S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105.

A. Errara, Analysis situs: une probleme d'enumeration, Memoires Acad. Bruxelles, Series 2, Vol. 11, No. 6, 26pp.

K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167.

Philippe Flajolet, Eric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, arXiv:math.CO/0606370

D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.

H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.

J. R. Gaggins, Constructing the Centroid of a Polygon, Math. Gaz., 61 (1988), 211-212.

M. Gardner, Time Travel and Other Mathematical Bewilderments, Chap. 20 pp. 253-266 W. H. Freeman NY 1988.

James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).

H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.

Alain Goupil and Gilles Schaeffer, Factoring N-Cycles and Counting Maps of Given Genus . Europ. J. Combinatorics (1998) 19 819-834.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 530.

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.23).

B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 513, Eq. (7.282).

M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.6.

Thomas Koshy and Mohammad Salmassi, "Parity and Primality of Catalan Numbers", College Mathematics Journal, Vol. 37, No. 1 (Jan 2006), pp. 52-53.

M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.

Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

P. J. Larcombe, On pre-Catalan Catalan numbers: Kotelnikow (1766), Mathematics Today, 35 (1999), p. 25.

P. J. Larcombe, On the history of the Catalan numbers: a first record in China, Mathematics Today, 35 (1999), p. 89.

P. J. Larcombe, The 18th century Chinese discovery of the Catalan numbers, Math. Spectrum, 32 (1999/2000), 5-7.

P. J. Larcombe and P. D. C. Wilson, On the trail of the Catalan sequence, Mathematics Today, 34 (1998), 114-117.

P. J. Larcombe and P. D. C. Wilson, On the generating function of the Catalan sequence: a historical perspective, Congress. Numer., 149 (2001), 97-108.

G. S. Lueker, Some techniques for solving recurrences, Computing Surveys, 12 (1980), 419-436.

J. J. Luo, Antu Ming, the first inventor of Catalan numbers in the world [in Chinese], Neimenggu Daxue Xuebao, 19 (1998), 239-245.

Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.

D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344.

C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly, 64 (1957), 143-154.

A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).

Robert Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

S. G. Penrice, Stacks, bracketings and CG-arrangements, Math. Mag., 72 (1999), 321-324.

C. A. Pickover, Wonders of Numbers, Chap. 71, Oxford Univ. Press NY 2000.

R. Read, "Counting Binary Trees" in 'The Mathematical Gardner', D. A. Klarner Ed. pp. 331-334, Wadsworth CA 1989.

J.-L. Remy, Un procede iteratif de denombrement d'arbres binaires et son application a leur generation aleatoire, RAIRO Inform. Theor. 19 (1985), 179-195.

J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.

J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.

T. Santiago Costa Oliveira, "Catalan traffic" and integrals on the Grassmannian of lines, Discr. Math., 308 (2007), 148-152.

A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.

J. A. von Segner, Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula, Novi Comm. Acad. Scient. Imper. Petropolitanae, 7 (1758/1759), 203-209.

L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory, A 20 (1976), 375-376.

L. W. Shapiro, W.-J. Woan and S. Getu, The Catalan numbers via the World Series, Math. Mag., 66 (1993), 20-22.

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).

Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, Vol. 2, 1999; see especially Chapter 6.

R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.

Zhi-Wei Sun and Roberto Tauraso, Congruences involving Catalan numbers, arXiv:0709.1665v5.

I. Vun and P. Belcher, Catalan numbers, Mathematical Spectrum, 30 (1997/1998), 3-5.

D. Wells, Penguin Dictionary of Curious and Interesting Numbers, Entry 42 p 121, Penguin Books, 1987.

Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6.

Wen-jin Woan, A Relation Between Restricted and Unrestricted Weighted Motzkin Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.7.

Wen-jin Woan, Animals and 2-Motzkin Paths, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.6.

F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.

Liviu I. Nicolaescu, Counting Morse functions on the 2-sphere, arXiv:math/0512496.

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.

A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.

Higgins, Peter M. Combinatorial results for semigroups of order-preserving mappings. Math. Proc. Camb. Phil. Soc. (1993), 113: 281-296. [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200 [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

Solomon, A. Catalan monoids, monoids of local endomorphisms and their presentations. Semigroup Forum 53 (1996), 351--368 [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.

Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.

Dominique Foata and Guo-Niu Han, Dimers and new q-tangent numbers, Preprint, 2008.

Dominique Foata and Guo-Niu Han, The dimer polynomial triangle, Preprint, 2008.

S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964.

R. H. Jeurissen, Raney and Catalan, Discrete Math., 308 (2008), 6298-6307.

J. Harris, Algebraic Geometry: A First Course (GTM 133), Springer-Verlag, 1992, pages 245-247. [From Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009]

M. Griffiths, The Backbone of Pascal's Triangle, United Kingdom Mathematics Trust (2008), 53-63 and 85-93. [From Martin Griffiths (griffm(AT)essex.ac.uk), Mar 28 2009]

N. J. A. Sloane, The first 200 Catalan numbers

Joerg Arndt, Fxtbook

M. Azaola and F. Santos, The number of triangulations of the cyclic polytope C(n,n-4), Discrete Comput. Geom., 27 (2002), 29-48. (C(n) = number of triangulations of cyclic polytope C(n,2).)

John Baez, This week's finds in mathematical physics, Week 202

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences

M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.

D. Bill, Durango Bill's Enumeration of Binary Trees

H. Bottomley, Catalan Space Invaders

H. Bottomley, Illustration for A000108, A001147, A002694, A067310 and A067311

T. Bourgeron, Montagnards et polygones

M. Bousquet-Melou and Gilles Schaeffer, Walks on the slit plane, Probability Theory and Related Fields, Vol. 124, no. 3 (2002), 305-344.

K. S. Brown's Mathpages, The Meanings of Catalan Numbers

B. Bukh, PlanetMath.org, Catalan numbers

Alexander Burstein, Sergi Elizalde and Toufik Mansour, Restricted Dumont permutations, Dyck paths and noncrossing partitions, arXiv math.CO/0610234.

N. T. Cameron, Random walks, trees and extensions of Riordan group techniques

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).

Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seqs., Vol. 6, 2003.

T. Davis, Catalan Numbers

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.

R. M. Dickau, Catalan numbers

R. M. Dickau, Catalan Numbers (another copy)

D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence

I. Galkin, Enumeration of the Binary Trees(Catalan Numbers)

H. W. Gould, Congr. Numer. 165 (2003) p 33-38.

B. Gourevitch, L'univers de Pi (click Mathematiciens, Gosper)

R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 48

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 52

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 71

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 76

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 284

I. Jensen, Series exapansions for self-avoiding polygons

S. Johnson, The Catalan Numbers

A. Karttunen, Illustration of initial terms up to size n=7

C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.

A. F. Labossiere, Sobalian Coefficients.

A. F. Labossiere, Miscellaneous.

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Colin L. Mallows and Lou Shapiro, Balls on the Lawn, J. Integer Sequences, Vol. 2, 1999, #5.

Toufik Mansour, Counting Peaks at Height k in a Dyck Path, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.1

R. J. Marsh and P. P. Martin, Pascal arrays: counting Catalan sets

D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001.

A. Panayotopoulos and P. Tsikouras, Meanders and Motzkin Words, J. Integer Seqs., Vol. 7, 2004.

A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).

P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

P. Peart and W.-J. Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, 4 (2001), #01.1.3.

K. A. Penson and J.-M. Sixdeniers, Integral Representations of Catalan and Related Numbers, J. Integer Sequences, 4 (2001), #01.2.5.

A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.5.

N. J. A. Sloane, Illustration of initial terms

Frank Sottile, The Schubert Calculus of Lines (a section of Enumerative Real Algebraic Geometry)

R. P. Stanley, Hipparchus, Plutarch, Schr"oder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.

R. P. Stanley, Exercises on Catalan and Related Numbers

R. P. Stanley, Catalan Addendum

Zhi-Wei Sun, A combinatorial identity with application to Catalan numbers

D. Taylor, Catalan Structures(up to C(7))

G. Villemin's Almanac of Numbers, Nombres De Catalan

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (3).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (4).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (5).

Eric Weisstein's World of Mathematics, Dyck Path

W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2.

Index entries for "core" sequences

Index entries for sequences related to rooted trees

Index entries for sequences related to parenthesizing

Index entries for sequences related to necklaces

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18, 35

a(n) = binomial(2n, n)/(n+1) = (2n)!/(n!(n+1)!).

a(n) = binomial(2n, n)-binomial(2n, n-1)

a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).

G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x). G.f. A(x) satisfies A = 1 + x*A^2.

a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i) - Touchard.

2(2n-1)a(n-1) = (n+1)a(n).

It is known that a(n) is odd if and only if n=2^k-1, k=1, 2, 3, ... - Emeric Deutsch, Aug 04 2002.

Using the Stirling approximation in A000142 we get the asymptotic expansion a(n) ~ 4^n / (sqrt(Pi * n) * (n + 1)). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 13 2001

Integral representation: a(n)=int(x^n*sqrt((4-x)/x), x=0..4)/(2*Pi). - Karol A. Penson (penson(AT)lptl.jussieu.fr), Apr 12 2001

E.g.f.: exp(2x) (I_0(2x)-I_1(2x)), where I_n is Bessel function. - Karol A. Penson (penson(AT)lptl.jussieu.fr), Oct 07 2001

Polygorial(n, 6)/Polygorial(n, 3) - Daniel Dockery (peritus(AT)gmail.com) Jun 24, 2003

G.f. A(x) satisfies ((A(x)+A(-x))/2)^2 = A(4*x^2). - Michael Somos, Jun 27, 2003

G.f. A(x) satisfies Sum_{k>=1} k(A(x)-1)^k = Sum_{n >= 1} 4^{n-1} x^n. - Shapiro, Woan, Getu

a(n+m) = Sum_{k} A039599(n, k)*A039599(m, k). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Dec 22 2003

a(n+1) = (1/(n+1))*sum_{k=0..n} a(n-k)*binomial(2k+1, k+1) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jan 24 2004

a(n) = Sum_{k>=0} A008313(n, k)^2 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 14 2004

a(m+n+1) = Sum_{k>=0} A039598(m, k)*A039598(n, k) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 15 2004

a(n)=sum{k=0..n, (-1)^k*2^(n-k)*binomial(n, k)*binomial(k, floor(k/2))} - Paul Barry (pbarry(AT)wit.ie), Jan 27 2005

a(n) = Sum_{k=0..[n/2]} ((n-2*k+1)*C(n, n-k)/(n-k+1))^2, which is equivalent to: a(n) = Sum_{k=0..n} A053121(n, k)^2, for n>=0. - Paul D. Hanna (pauldhanna(AT)juno.com), Apr 23 2005

a((m+n)/2) = Sum_{k>=0} A053121(m, k)*A053121(n, k) if m+n is even . - Philippe DELEHAM, May 26 2005

E.g.f. Sum_{n>=0} a(n)*x^(2n)/(2n)! = BesselI(1, 2x)/x . - Michael Somos Jun 22 2005

Given g.f. A(x), then B(x)=x*A(x^3) satisfies 0=f(x, B(X)) where f(u, v)=u-v+(uv)^2 or B(x)=x+(x*B(x))^2 which implies B(-B(x))=-x and also (1+B^3)/B^2 = (1-x^3)/x^2 . - Michael Somos Jun 27 2005

a(n) = a(n-1)*(4-6/(n+1)). a(n) = 2a(n-1)*(8a(n-2)+a(n-1))/(10a(n-2)-a(n-1)). - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Feb 08 2006

Sum_{k=1}^{infinity} a(k)/4^k = 1. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Jun 28 2006

a(n) = A047996(2*n+1,n) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jul 25 2006

Binomial transform of A005043 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 20 2006

a(n)=Sum_{k, 0<=k<=n}(-1)^k*A116395(n,k) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 07 2006

a(n)=[1/(s-n)]*sum_{k=0..n} (-1)^k (k+s-n)*binomial(s-n,k)*binomial(s+n-k,s) with s a nonnegative free integer [H. W. Gould].

a(k) = Sum_{i=1..k} |A008276(i,k)| * (k-1)^(k-i) / k! - Andre F. Labossiere (boronali(AT)laposte.net), May 29 2007

a(n)=Sum_{k, 0<=k<=n}A129818(n,k)*A007852(k+1). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 20 2007

a(n)=Sum_{k, 0<=k<=n}A109466(n,k)*A127632(k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 20 2007

Row sums of triangle A124926 - Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 22 2007

For G.f. A(x), g(x)= x*A(x) is the compositional inverse of f(x) = x*(1-x) and this relates the Catalan numbers to the row sums of A125181. - Tom Copeland (tcjpn(AT)msn.com), Jan 13 2008

lim(1+Sum(a(k)/A004171(k): 0<=k<=n): n->infinity) = 4/pi. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Aug 26 2008]

a(n)=Sum_{k, 0<=k<=n}A120730(n,k)^2 and a(k+1)=Sum_{n, n>=k}A120730(n,k). [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 18 2008]

Comment from Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 27 2008: Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example the present sequence is Phi([1]) (also Phi([1,1])).

Formula from Thomas Wieder (wieder.thomas(AT)t-online.de), Feb 25 2009:

a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1}

delta(l_1,l_2,...,l_i,...,l_n)

where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i < l_(i+1) and l_(i+1) <> 0

for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise.

a(n) = C(2*n,n)-C(2*n,n-1) . [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 17 2009]

A000108 := n->binomial(2*n, n)/(n+1); G000108 := (1 - sqrt(1 - 4*x)) / (2*x);

spec := [ A, {A=Prod(Z, Sequence(A))}, unlabeled ]: [ seq(combstruct[count](spec, size=n), n=0..42) ];

with(combstruct):bin := {B=Union(Z, Prod(B, B))}: seq (count([B, bin, unlabeled], size=n), n=1..25); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 05 2007

Z[0]:=0: for k to 42 do Z[k]:=simplify(1/(1-z*Z[k-1])) od: g:=sum((Z[j]-Z[j-1]), j=1..42): gser:=series(g, z=0, 42): seq(coeff(gser, z, n), n=0..41); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 21 2008

A000108[ n_ ] := (2 n)!/n!/(n+1)!

A000108[n_]:=Hypergeometric2F1[1-n, -n, 2, 1] - Richard L. Ollerton (r.ollerton(AT)uws.edu.au), Sep 13 2006

(MAGMA) C:= func< n | Binomial(2*n, n)/(n+1) >; [ C(n) : n in [0..60]];

(PARI) a(n)=if(n<0, 0, (2*n)!/n!/(n+1)!)

(PARI) a(n)=local(A, m); if(n<0, 0, m=1; A=1+x+O(x^2); while(m<=n, m*=2; A=sqrt(subst(A, x, 4*x^2)); A+=(A-1)/(2*x*A)); polcoeff(A, n))

(PARI) a(n)=if(n<1, n==0, polcoeff(serreverse(x/(1+x)^2+x*O(x^n)), n)) (from Michael Somos)

(Mupad) combinat::dyckWords::count(n) $ n = 0..38 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 14 2007

sage: [catalan_number(i) for i in range(27)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 26 2008

(Other) sage: [binomial(2*i, i)-binomial(2*i, i-1) for i in xrange(0, 25)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 17 2009]

Cf. A000984, A002420, A048990, A024492, A000142, A022553. A row of A060854.

Cf. A039599, A094216, A094638, A014137, A094639, A099731, A008549.

See A001003, A001190, A001699, A000081 for other ways to count parentheses.

Enumerates objects encoded by A014486.

Cf. A008276, A094638 (|A008276|), A094216, A094639, A000984.

A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.

Cf. A000108 A000245 A002057 A000344 A003517 A000588 A003518 A003519 A001392.

Cf. A124926.

Cf. A098597, A086117, A137697.

A diagonal of the square array described in A051168.

A154559 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 11 2009]

A000957, A068875 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 01 2009]

A032443 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 15 2009]

Sequence in context: A054394 A036769 A033191 this_sequence A115140 A120588 A057413

Adjacent sequences: A000105 A000106 A000107 this_sequence A000109 A000110 A000111

core,nonn,easy,eigen,nice

N. J. A. Sloane (njas(AT)research.att.com).