|
%I M1459 N0577
%S 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,
%T 9694845,35357670,129644790,477638700,1767263190,6564120420,
%U 24466267020,91482563640,343059613650,1289904147324,4861946401452,18367353072152,69533550916004,263747951750360,1002242216651368,3814986502092304
%N Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Also called Segner numbers.
%C The solution to Schröder's first problem. A very large number of combinatorial interpretations are known - see references, esp. Stanley, Enumerative Combinatorics, Volume 2. This is probably the longest entry in the OEIS, and rightly so.
%C Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).
%C 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 that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]
%C Number of noncrossing partitions of the n-set. For example, of the 15 set partitions of the 4-set, only [{13},{24}] is crossing, so there are a(4)=14 noncrossing partitions of 4 elements. - _Joerg Arndt_, Jul 11 2011
%C a(n-1) is the number of ways of expressing an n-cycle in the symmetric group S_n as a product of n-1 transpositions (u_1,v_1)*(u_2,v_2)*...*(u_{n-1},v_{n-1}) where u_k<=u_j and v_k<=v_j for k<j; see example. If the condition is dropped, one obtains A000272. - _Joerg Arndt_ and Greg Stevenson, Jul 11 2011
%C 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. - _Wolfdieter Lang_, Aug 07 2007
%C As shown in the paper from Beineke and Pippert (1971), a(n-2)=D(n) is the number of labeled dissections of a disk, related to the number R(n)=A001761(n-2) of labeled planar 2-trees having n vertices and rooted at a given exterior edge, by the formula D(n)=R(n)/(n-2)!. - _M. F. Hasler_, Feb 22 2012
%C Shifts one place left when convolved with itself.
%C 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
%C 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).)
%C Arises in Schubert calculus - see Sottile reference.
%C Inverse Euler transform of sequence is A022553.
%C With interpolated zeros, the inverse binomial transform of the Motzkin numbers A001006. - _Paul Barry_, Jul 18 2003
%C 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 . - _Philippe Deléham_, Mar 04 2004
%C 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) + ..... ]. - _André F. Labossière_, Nov 10 2004
%C Sum_{n=0..infinity} 1/a(n) = 2 + 4*Pi/3^(5/2) = F(1,2;1/2;1/4) = 2.806133050770763... (see L'Univers de Pi link). - _Gerald McGarvey_ and _Benoit Cloitre_, Feb 13 2005
%C 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_, Apr 23 2005
%C 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], ... - Donald D. Cross (cosinekitty(AT)hotmail.com), Feb 04 2005
%C 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. - _Franklin T. Adams-Watters_, Feb 08 2006
%C 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_, Mar 06 2006
%C 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. - _Franklin T. Adams-Watters_, Apr 14 2006
%C 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_, Dec 04 2006
%C 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. - _Abdullahi Umar_, Aug 25 2008
%C 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)). - Rutger Boels (boels(AT)nbi.dk), Aug 26 2008
%C The invert transform appears to converge to the Catalan numbers when applied infinitely many times to any starting sequence. - _Mats Granvik_, _Gary W. Adamson_ and _Roger L. Bagula_, Sep 09 2008, Sep 12 2008
%C lim(a(n)/a(n-1): n->infinity) = 4. - Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008
%C Starting with offset 1 = row sums of triangle A154559. - _Gary W. Adamson_, Jan 11 2009
%C 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. - Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009
%C 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. - _Gary W. Adamson_, May 01 2009
%C Convolved with A032443: (1, 3, 11, 42, 163,...) = powers of 4, A000302: (1, 4, 16,...). - _Gary W. Adamson_, May 15 2009
%C Sum{k=1...Infinity,c(k-1)/2^(2k-1)}=1. The k-th 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. - _Geoffrey Critzer_, Sep 12 2009
%C C(p+q)-C(p)*C(q)=sum(C(i)*C(j)*C(p+q-i-j-1), i=0..(p-1), j=0..(q-1) ). - _Groux Roland_, Nov 13 2009
%C Leonhard Euler used the formula C(n) = product_{i=3..n}(4*i-10)/(i-1) in his 'Betrachtungen, auf wie vielerley Arten ein gegebenes polygonum durch Diagonallinien in triangula zerschnitten werden könne' and computes by recursion C(n+2) for n = 1..8. (Berlin, 4th September 1751, in a letter to Goldbach.) - _Peter Luschny_, Mar 13 2010
%C Let A179277 = A(x). Then C(x) is satisfied by A(x)/A(x^2). - _Gary W. Adamson_, Jul 07 2010
%C a(n) = A000680(n)/A006472(n). - Mark Dols (markdols99(AT)yahoo.com), Jul 14 2010
%C a(n) is also the number of quivers in the mutation class of type B_n or of type C_n. - _Christian Stump_, Nov 02 2010
%C Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color while satisfying the following conditions: 1. No two colors are chosen the same positive number of times. 2. For any two colors (c, d) that are chosen at least once, color c is chosen more times than color d iff color c appears more times in the original set than color d.
%C If the second requirement is lifted, the number of acceptable ways equals A000110(n+1). See related comments for A016098, A085082. - _Matthew Vandermast_, Nov 22 2010
%C Deutsch and Sagan prove the Catalan number C_n is odd if and only if n = 2^a - 1 for some nonnegative integer a. Lin proves for every odd Catalan number C_n, we have C_n == 1 (mod 4). - _Jonathan Vos Post_, Dec 09 2010
%C a(n) is the number of functions f:{1,2,...,n}->{1,2,...,n} such that f(1)=1 and for all n>=1 f(n+1)<=f(n)+1. For a nice bijection between this set of functions and the set of length 2n Dyck words, see page 333 of the Fxtbook (see link below).
%C Complement of A092459; A010058(a(n)) = 1. - _Reinhard Zumkeller_, Mar 29 2011
%C Postnikov (2005) defines "generalized Catalan numbers" associated with buildings (e.g., Catalan numbers of Type B, see A000984). - _N. J. A. Sloane_, Dec 10 2011
%C A076050(a(n)) = n + 1 for n > 0. - _Reinhard Zumkeller_, Feb 17 2012
%C Number of permutations in S(n) for which length equals depth. - _Bridget Tenner_, Feb 22 2012
%C a(n) is also the number of standard Young tableau of shape (n,n). - _Thotsaporn Thanatipanonda_, Feb 25 2012
%C a(n) is the number of binary sequences of length 2n+1 in which the number of ones first exceed the number of zeros at entry 2n+1. See the example below in the example section. - _Dennis P. Walsh_, Apr 11 2012
%C a(n+1) = A214292(2*n+1,n) = A214292(2*n+2,n). - _Reinhard Zumkeller_, Jul 12 2012
%C Number of binary necklaces of length 2*n+1 containing n 1's (or, by symmetry, 0's). All these are Lyndon words and their representatives (as cyclic maxima) are the binary Dyck words. - _Joerg Arndt_, Nov 12 1012
%C Number of sequences consisting of n 'x' letters and n 'y' letters such that (counting from the left) the 'x' count >= 'y' count. For example, for n=3 we have xxxyyy, xxyxyy, xxyyxy, xyxxyy and xyxyxy. - _Jon Perry_, Nov 16 2012
%C a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps come in 2 colors. Example: a(4)=14 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 8 paths of shape HHH, 2 paths of shape UHD, 2 paths of shape UDH, and 2 paths of shape HUD. - _José Luis Ramírez Ramírez_, Jan 16 2013
%C If p is an odd prime, then (-1)^((p-1)/2)*a((p-1)/2) mod p = 2. - _Gary Detlefs_, Feb 20 2013
%C Conjecture: For any positive integer n, the polynomial sum(k=0..n, a(k)*x^k) is irreducible over the field of rational numbers. - _Zhi-Wei Sun_, Mar 23 2013
%C a(n) is the size of the Jones monoid on 2n points (cf. A225798). - _James Mitchell_, Jul 28 2013
%C Given Probability (p): sum(n=0..inf) a(n)*(1-p)^n*p^(n+1) = sum(n=1..inf) p^n = p/(1-p). E.g., at p=0.4: 0.4 + 0.6*0.4^2 + 2*0.6^2*0.4^3 + 5*0.6^3*0.4^4 + 14*0.6^4*0.4^5 +... = 0.4 + 0.096 + 0.04608 + 0.027648 + 0.018579456... = 2/3. Since p/(1-p) is itself a probability, it therefore has a maximum value of 1 when p >= 0.5. - _Bob Selcoe_, Nov 16 2013
%C No a(n) has the form x^m with m > 1 and x > 1. - _Zhi-Wei Sun_, Dec 02 2013
%C From _Alexander Adamchuk_, Dec 27 2013: (Start)
%C Prime p divides a((p+1)/2) for p>3. See A120303(n) = Largest prime factor of Catalan number.
%C Reciprocal Catalan Constant C = 1 + 4*sqrt(3)*Pi/27 = 1.8061330507707... See A121839 = Decimal expansion of sum(k>=1, 1/a(k)).
%C Log(Phi) = (125*C - 55) / (24*sqrt(5)), where C = Sum_{k>=1} (-1)^(k+1)*1/a(k). See A002390 = Decimal expansion of natural logarithm of golden ratio.
%C 3-d analog of the Catalan numbers: (3n)!/(n!(n+1)!(n+2)!) = A161581(n) = A006480(n) / ((n+1)^2*(n+2)), where A006480(n) = (3n)!/(n!)^3 De Bruijn's S(3,n). (End)
%C For a relation to the inviscid Burgers', or Hopf, equation, see A001764. - _Tom Copeland_, Feb 15 2014
%C From _Fung Lam_, May 01 2014: (Start)
%C One class of generalized Catalan numbers can be defined by g.f. A(x) = (1-sqrt(1-q*4*x*(1-(q-1)*x)))/(2*q*x) with nonzero parameter q. Recurrence: (n+3)*a(n+2) -2*q*(2*n+3)*a(n+1) +4*q*(q-1)*n*a(n) = 0 with a(0)=1, a(1)=1.
%C Asymptotic approximation for q>=1: a(n) ~ (2*q+2*sqrt(q))^n*sqrt(2*q*(1+sqrt(q))) /sqrt(4*q^2*Pi*n^3).
%C For q=<-1, the g.f. defines signed sequences with asymptotic approximation: a(n) ~ Re(sqrt(2*q*(1+sqrt(q)))*(2*q+2*sqrt(q))^n) / sqrt(q^2*Pi*n^3), where Re denotes the real part. Due to Stokes' phenomena, accuracy of the asymptotic approximation deteriorates at/near certain values of n.
%C Special cases are A000108 (q=1), A068764 to A068772 (q=2 to 10), A240880 (q=-3).
%C (End)
%C Number of sequences [s(0), s(1), ..., s(n)] with s(n)=0, sum(j=0..n, s(j)) = n, and sum(j=0..k, s(j)-1 ) >= 0 for k<n-1 (and necessarily sum(j=0..n-1, s(j)-1 ) = 0). These are the branching sequences of the (ordered) trees with n non-root nodes, see example. - _Joerg Arndt_, Jun 30 2014
%C Number of stack-sortable permutations of [n], these are the 231-avoiding permutations; see the Bousquet-Mélou reference. - _Joerg Arndt_, Jul 01 2014
%C a(n) is the number of increasing strict binary trees with 2n-1 nodes that avoid 132. For more information about increasing strict binary trees with an associated permutation, see A245894. - _Manda Riehl_, Aug 07 2014
%C In a one-dimensional medium with elastic scattering (zig-zag walk), first recurrence after 2n+1 scattering events has the probability C(n)/2^(2n+1). - _Joachim Wuttke_, Sep 11 2014
%C The o.g.f. C(x) = [1 - sqrt(1-4x)]/2, for the Catalan numbers, with comp. inverse Cinv(x) = x*(1-x) and the functions P(x) = x / (1 + t*x) and its inverse Pinv(x,t) = -P(-x,t) = x / (1 - t*x) form a group under composition that generates or interpolates among many classic arrays, such as the Motzkin (Riordan, A005043), Fibonacci (A000045), and Fine (A000957) numbers and polynomials (A030528), and enumerating arrays for Motzkin, Dyck, and Lukasiewicz lattice paths and different types of trees and non-crossing partitions (A091867, connected to sums of the refined Narayana numbers A134264). - _Tom Copeland_, Nov 04 2014
%D The large number of references and links demonstrates the ubiquity of the Catalan numbers.
%D Abrate, Marco; Barbero, Stefano; Cerruti, Umberto; Murru, Nadir. Colored compositions, Invert operator and elegant compositions with the "black tie". Discrete Math. 335 (2014), 1--7. MR3248794
%D M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
%D 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.
%D R. Alter and K. K. Kubota, Prime and prime power divisibility of Catalan numbers, J. Combinatorial Theory, Ser. A, 15 (1973), 243-256.
%D Andrews, George E. Catalan numbers, q-Catalan numbers and hypergeometric series. J. Combin. Theory Ser. A 44 (1987), no. 2, 267--273. MR0879684 (88f:05015)
%D R. Bacher and C. Krattenthaler, Chromatic statistics for triangulations and FussCatalan complexes, Electronic Journal of Combinatorics, 18 (2011), #P152.
%D D. F. Bailey, Counting Arrangements of 1's and -1's, Mathematics Magazine 69(2) 128-131 1996.
%D I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.
%D Barcucci, E.; Del Lungo, A.; Pergola, E.; and Pinzani, R.; Some permutations with forbidden subsequences and their inversion number. Discrete Math. 234 (2001), no. 1-3, 1-15.
%D E. Barcucci, A. Frosini and S. Rinaldi, On directed-convex polyominoes in a rectangle, Discr. Math., 298 (2005). 62-78.
%D J.-L. Baril, T. Mansour, A. Petrossian, Equivalence classes of permutations modulo excedances, 2014; http://jl.baril.u-bourgogne.fr/equival.pdf
%D Baril, Jean-Luc; Petrossian, Armen. Equivalence classes of Dyck paths modulo some statistics. Discrete Math. 338 (2015), no. 4, 655--660. MR3300754
%D E. T. Bell, The iterated exponential numbers, Ann. Math., 39 (1938), 539-557.
%D 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.
%D E. E. Bernard and P. D. A. Mole, Generating strategies for continuous separation processes, Computer J., 2 (1959), 87-89.
%D F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
%D A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, J. Int. Seq. 10 (2007) # 07.9.7
%D M. Bona and B. E. Sagan, On Divisibility of Narayana Numbers by Primes, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.4.
%D Bousquet, Michel; and Lamathe, Cedric; On symmetric structures of order two. Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176.
%D W. G. Brown, Historical note on a recurrent combinatorial problem, Amer. Math. Monthly, 72 (1965), 973-977.
%D D. Callan, A combinatorial interpretation of a Catalan numbers identity, Math. Mag., 72 (1999), 295-298.
%D D. Callan, The maximum associativeness of division, Problem 11091, Amer. Math. Monthly, 113 (#5, 2006), 462-463.
%D D. Callan, Pattern avoidance in "flattened" partitions, Discrete Math., 309 (2009), 4187-4191.
%D Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See p. 155.
%D Chen, Young-Ming. The Chung-Feller theorem revisited. Discrete Math. 308 (2008), no. 7, 1328--1329. MR2382368 (2008j:05019)
%D Chung, Kai Lai; Feller, W., On fluctuations in coin-tossing. Proc. Nat. Acad. Sci. U. S. A. 35, (1949). 605-608.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 53.
%D J. H. Conway and R. K. Guy, The Book of Numbers, New York: Springer-Verlag, 1995, ch. 4, pp. 96-106.
%D Harry Crane, Left-right arrangements, set partitions, and pattern avoidance. Australasian Journal of Combinatorics, 61(1) (2105), 57-72.
%D S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see pp. 183, 196, etc.).
%D Dairyko, Michael; Tyner, Samantha; Pudwell, Lara; Wynn, Casey. Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From _N. J. A. Sloane_, Feb 01 2013
%D E. Deutsch, Dyck path enumeration, Discrete Math., 204, 167-202, 1999.
%D E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
%D E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001.
%D Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019)
%D S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105.
%D Eggleton, Roger B., and Richard K. Guy. "Catalan strikes again! How likely is a function to be convex?." Mathematics Magazine, 61 (1988): 211-219.
%D A. Errera, Analysis situs - Un problème d'énumération, Mémoires Acad. Bruxelles, Classe des sciences, Série 2, Vol. XI, Fasc. 6, No. 1421 (1931), 26 pp.
%D Ehrenfeucht, Andrzej; Haemer, Jeffrey; Haussler, David. Quasimonotonic sequences: theory, algorithms and applications. SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 410--429. MR0897739 (88h:06026)
%D I. M. H. Etherington, Non-associate powers and a functional equation. The Mathematical Gazette, 21 (1937): 36-39; addendum 21 (1937), 153.
%D I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
%D I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
%D K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167.
%D Susanna Fishel, Myrto Kallipoliti and Eleni Tzanaki, Facets of the Generalized Cluster Complex and Regions in the Extended Catalan Arrangement of Type A, The electronic Journal of Combinatorics 20(4) (2013), #P7.
%D Flajolet, Philippe; Gourdon, Xavier; and Dumas, Philippe; Mellin transforms and asymptotics: harmonic sums. Special volume on mathematical analysis of algorithms. Theoret. Comput. Sci. 144 (1995), no. 1-2, 3-58.
%D D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.
%D H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.
%D Fürlinger, J.; Hofbauer, J., q-Catalan numbers. J. Combin. Theory Ser. A 40 (1985), no. 2, 248--264. MR0814413 (87e:05017)
%D J. R. Gaggins, Constructing the Centroid of a Polygon, Math. Gaz., 61 (1988), 211-212.
%D M. Gardner, Time Travel and Other Mathematical Bewilderments, Chap. 20 pp. 253-266, W. H. Freeman NY 1988.
%D S. Gilliand, C. Johnson, S. Rush, D. Wood, The sock matching problem, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 691-697; DOI: 10.2140/involve.2014.7.691
%D James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).
%D Lisa R. Goldberg, Catalan numbers and branched coverings by the Riemann sphere, Adv. Math. 85 (1991), No. 2, 129-144.
%D H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.
%D Alain Goupil and Gilles Schaeffer, Factoring N-Cycles and Counting Maps of Given Genus. Europ. J. Combinatorics (1998) 19 819-834.
%D D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.
%D 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]
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 530.
%D N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
%D R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.
%D R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876.
%D Peter Hajnal and Gabor V. Nagy, A bijective proof of Shapiro's Catalan convolution, Elect. J. Combin., 21 (2014), #P2.42.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.23).
%D Harary, F.; Prins, G.; and Tutte, W. T. The Number of Plane Trees. Indag. Math. 26, 319-327, 1964.
%D J. Harris, Algebraic Geometry: A First Course (GTM 133), Springer-Verlag, 1992, pages 245-247.
%D S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964.
%D Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
%D Higgins, Peter M. Combinatorial results for semigroups of order-preserving mappings. Math. Proc. Camb. Phil. Soc. (1993), 113: 281-296.
%D B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 513, Eq. (7.282).
%D F. Hurtado, M. Noy, Ears of triangulations and Catalan numbers, Discrete Mathematics, Volume 149, Issues 1-3, Feb 22 1996, Pages 319-324.
%D M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - From _N. J. A. Sloane_, Sep 16 2012
%D R. H. Jeurissen, Raney and Catalan, Discrete Math., 308 (2008), 6298-6307.
%D M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 36.
%D Kim, Ki Hang; Rogers, Douglas G.; Roush, Fred W. Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577--594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013)
%D Klarner, D. A. A Correspondence Between Sets of Trees. Indag. Math. 31, 292-296, 1969.
%D M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
%D D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.6 (p. 450).
%D Thomas Koshy and Mohammad Salmassi, "Parity and Primality of Catalan Numbers", College Mathematics Journal, Vol. 37, No. 1 (Jan 2006), pp. 52-53.
%D M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.
%D Kreweras, G. Sur les partitions non croisees d'un cycle. (French) Discrete Math. 1 (1972), no. 4, 333--350. MR0309747 (46 #8852)
%D C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146.
%D P. Lafar and C. T. Long, A combinatorial problem, Amer. Math. Mnthly, 69 (1962), 876-883.
%D Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200.
%D P. J. Larcombe, On pre-Catalan Catalan numbers: Kotelnikow (1766), Mathematics Today, 35 (1999), p. 25.
%D P. J. Larcombe, On the history of the Catalan numbers: a first record in China, Mathematics Today, 35 (1999), p. 89.
%D P. J. Larcombe, The 18th century Chinese discovery of the Catalan numbers, Math. Spectrum, 32 (1999/2000), 5-7.
%D P. J. Larcombe and P. D. C. Wilson, On the trail of the Catalan sequence, Mathematics Today, 34 (1998), 114-117.
%D 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.
%D P. J. Larcombe et al., On certain series expansions of the sine function: Catalan numbers and convergence, Fib. Q., 52 (2014), 236-242.
%D G. S. Lueker, Some techniques for solving recurrences, Computing Surveys, 12 (1980), 419-436.
%D J. J. Luo, Antu Ming, the first inventor of Catalan numbers in the world [in Chinese], Neimenggu Daxue Xuebao, 19 (1998), 239-245.
%D Mansour, Toufik; Schork, Matthias; Shattuck, Mark. Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979--2991. MR2956089 - From _N. J. A. Sloane_, Sep 07 2012
%D Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.
%D Mays, M. E.; and Wojciechowski, Jerzy; A determinant property of Catalan numbers. Discrete Math. 211, No. 1-3, 125-133 (2000). Zbl 0945.05037
%D D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344.
%D A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.
%D C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly, 64 (1957), 143-154.
%D A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).
%D Papoulis, Athanasios. "A new method of inversion of the Laplace transform."Quart. Appl. Math 14.405-414 (1957): 124.
%D S. G. Penrice, Stacks, bracketings and CG-arrangements, Math. Mag., 72 (1999), 321-324.
%D C. A. Pickover, Wonders of Numbers, Chap. 71, Oxford Univ. Press NY 2000.
%D Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.
%D Pólya, G. On the number of certain lattice polygons. J. Combinatorial Theory 6 1969 102--105. MR0236031 (38 #4329)
%D C. Pomerance, Divisors of the middle binomial coefficient, Amer. Math. Monthly, 112 (2015), 636-644.
%D Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
%D R. Read, "Counting Binary Trees" in 'The Mathematical Gardner', D. A. Klarner Ed. pp. 331-334, Wadsworth CA 1989.
%D Amitai Regev, Nathaniel Shar, and Doron Zeilberger, A Very Short (Bijective!) Proof of Touchard's Catalan Identity, 2015; http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/touchard.html
%D 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.
%D J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
%D J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
%D T. Santiago Costa Oliveira, "Catalan traffic" and integrals on the Grassmannian of lines, Discr. Math., 308 (2007), 148-152.
%D A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
%D E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
%D Shapiro, Louis W. Catalan numbers and "total information" numbers. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 531--539. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0398853 (53 #2704).
%D L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory, A 20 (1976), 375-376.
%D L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
%D L. W. Shapiro, W.-J. Woan and S. Getu, The Catalan numbers via the World Series, Math. Mag., 66 (1993), 20-22.
%D D. M. Silberger, Occurrences of the integer (2n-2)!/n!(n-1)!, Roczniki Polskiego Towarzystwa Math. 13 (1969): 91-96.
%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).
%D S. Snover and S. Troyer, Multidimensional Catalan numbers, Abstracts 848-05-94 and 848-05-95, 848th Meeting, Amer. Math. Soc., Worcester Mass., March 15-16, 1989.
%D Solomon, A. Catalan monoids, monoids of local endomorphisms and their presentations. Semigroup Forum 53 (1996), 351-368.
%D R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, Vol. 2, 1999; see especially Chapter 6.
%D R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.
%D Richard P. Stanley, "Catalan Numbers", Cambridge University Press, 2015.
%D J. J. Sylvester, On reducible cyclodes, Coll. Math. Papers, Vol. 2, see especially page 670, where Catalan numbers appear.
%D 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.
%D I. Vun and P. Belcher, Catalan numbers, Mathematical Spectrum, 30 (1997/1998), 3-5.
%D D. Wells, Penguin Dictionary of Curious and Interesting Numbers, Entry 42 p 121, Penguin Books, 1987.
%D J. Wuttke, The zig-zag walk with scattering and absorption on the real half line and in a lattice model, J. Phys. A 47 (2014), 215203, 1-9.
%H Neil J. A. Sloane, K. D. Bajpai and Robert G. Wilson v, <a href="/A000108/b000108.txt">Table of n, a(n) for n = 0..1000</a> (first 200 terms from Neil J. A. Sloane and the first 351 from K. D. Bajpai)
%H James Abello, <a href="http://dx.doi.org/10.1137/0404001">The weak Bruhat order of S consistent sets, and Catalan numbers</a>, SIAM J. Discrete Math. 4 (1991), 1-16.
%H P. C. Allaart and K. Kawamura, <a href="http://arxiv.org/abs/1110.1691">The Takagi function: a survey</a>, Real Analysis Exchange, 37 (2011/12), 1--54; arXiv:1110.1691. See Section 3.2.
%H N. Alon, Y. Caro and I. Krasikov, <a href="http://www.math.tau.ac.il/~nogaa/PDFS/Publications/Bisection of trees and sequences.pdf">Bisection of trees and sequences</a>, Discrete Math., 114 (1993), 3-7. (See Lemma 2.1.)
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 333 and p. 337.
%H Jean-Christophe Aval, <a href="http://arxiv.org/abs/0711.0906">Multivariate Fuss-Catalan numbers</a>, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.
%H M. Azaola and F. Santos, <a href="http://personales.unican.es/santosf/Articulos/">The number of triangulations of the cyclic polytope C(n,n-4)</a>, Discrete Comput. Geom., 27 (2002), 29-48. (C(n) = number of triangulations of cyclic polytope C(n,2).)
%H John Baez, <a href="http://math.ucr.edu/home/baez/week202.html">This week's finds in mathematical physics, Week 202</a>
%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://algo.inria.fr/banderier/Papers/DiscMath99.ps">Generating Functions for Generating Trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
%H E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, <a href="http://www.dmtcs.org/volumes/abstracts/dm040103.abs.html">Permutations avoiding an increasing number of length-increasing forbidden subsequences</a>, Discrete Mathematics and Theoretical Computer Science 4, 2000, 31-44.
%H J.-L. Baril, <a href="http://www.combinatorics.org/Volume_18/PDF/v18i1p178.pdf">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.
%H J.-L. Baril, J.-M. Pallo, <a href="http://jl.baril.u-bourgogne.fr/Motzkin.pdf">Motzkin subposet and Motzkin geodesics in Tamari lattices</a>, 2013.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
%H Paul Barry, <a href="http://arxiv.org/abs/1107.5490">Invariant number triangles, eigentriangles and Somos-4 sequences</a>, arXiv:1107.5490, 2011.
%H A. M. Baxter, L. K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014.
%H L. W. Beineke and R. E. Pippert, Enumerating labeled k-dimensional trees and ball dissections, pp. 12-26 of Proceedings of Second Chapel Hill Conference on Combinatorial Mathematics and its Applications, University of North Carolina, Chapel Hill, 1970. Reprinted in <a href="http://dx.doi.org/10.1007/BF02330563">Math. Annalen 191 (1971), 87-98</a>.
%H Matthew Bennett, Vyjayanthi Chari, R. J. Dolbin and Nathan Manning, <a href="http://arxiv.org/abs/0912.4983">Square partitions and Catalan numbers</a>, arXiv:0912.4983.
%H E. E. Bernard and P. D. A. Mole, <a href="/A000108/a000108_7.pdf">Generating strategies for continuous separation processes</a>, Computer J., 2 (1959), 87-89. [Annotated scanned copy]
%H M. Bernstein and N. J. A. Sloane, <a href="http://arXiv.org/abs/math.CO/0205301">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
%H D. Bill, <a href="http://www.durangobill.com/BinTrees.html">Durango Bill's Enumeration of Binary Trees</a>
%H Miklós Bóna, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p62">Surprising Symmetries in Objects Counted by Catalan Numbers</a>, Electronic J. Combin., 19 (2012), P62.
%H H. Bottomley, <a href="/A000108/a000108b.gif">Catalan Space Invaders</a>
%H H. Bottomley, <a href="/A002694/a002694.gif">Illustration for A000108, A001147, A002694, A067310 and A067311</a>
%H T. Bourgeron, <a href="http://www.dma.ens.fr/culturemath/maths/pdf/combi/montagnards.pdf">Montagnards et polygones</a>
%H Mireille Bousquet-Mélou, <a href="http://www.sciencedirect.com/science/article/pii/S0012365X00001461">Sorted and/or sortable permutations</a>, Discrete Mathematics, vol.225, no.1-3, pp.25-50, (2000).
%H M. Bousquet-Mélou and Gilles Schaeffer, <a href="http://www.labri.fr/Perso/~bousquet/Articles/Slitplane/PTRF/final.ps.gz">Walks on the slit plane</a>, Probability Theory and Related Fields, Vol. 124, no. 3 (2002), 305-344.
%H G. Bowlin and M. G. Brin, <a href="http://arxiv.org/abs/1301.3984">Coloring Planar Graphs via Colored Paths in the Associahedra</a>, arXiv preprint arXiv:1301.3984, 2013.
%H Douglas Bowman and Alon Regev, <a href="http://arxiv.org/abs/1209.6270">Counting symmetry classes of dissections of a convex regular polygon</a>, arXiv preprint arXiv:1209.6270, 2012.
%H K. S. Brown's Mathpages, <a href="http://www.mathpages.com/home/kmath322.htm">The Meanings of Catalan Numbers</a> [Broken link]
%H W. G. Brown, <a href="/A000108/a000108_5.pdf">Historical note on a recurrent combinatorial problem</a>, Amer. Math. Monthly, 72 (1965), 973-977. [Annotated scanned copy]
%H B. Bukh, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/CatalanNumbers.html">Catalan numbers</a>
%H Alexander Burstein, Sergi Elizalde and Toufik Mansour, <a href="http://arXiv.org/abs/math.CO/0610234">Restricted Dumont permutations, Dyck paths and noncrossing partitions</a>, arXiv math.CO/0610234.
%H W. Butler, A. Kalotay and N. J. A. Sloane, <a href="/A000108/a000108_3.pdf">Correspondence, 1974</a>
%H W. Butler and N. J. A. Sloane, <a href="/A000108/a000108_2.pdf">Correspondence, 1974</a>
%H David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Callan/callan301.html">A Combinatorial Interpretation for a Super-Catalan Recurrence</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.8.
%H David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Callan/callan96.html">A Combinatorial Interpretation of the Eigensequence for Composition</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.
%H D. Callan, <a href="http://arxiv.org/abs/1204.5704">A variant of Touchard's Catalan number identity</a>, arXiv preprint arXiv:1204.5704, 2012.
%H David Callan and Emeric Deutsch, <a href="http://arxiv.org/abs/1112.3639">The Run Transform</a>, Discrete Math. 312 (2012), no. 19, 2927-2937, arXiv:1112.3639, 2011
%H N. T. Cameron, <a href="http://www.princeton.edu/~wmassey/NAM03/cameron.pdf">Random walks, trees and extensions of Riordan group techniques</a>
%H Naiomi T. Cameron and Asamoah Nkwanta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html">On Some (Pseudo) Involutions in the Riordan Group</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
%H P. J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 162
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H A. Cayley, <a href="http://dx.doi.org/10.1112/plms/s1-22.1.237">On the partitions of a polygon</a>, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.
%H F. Cazals, <a href="http://algo.inria.fr/libraries/autocomb/NCC-html/NCC.html">Combinatorics of Non-Crossing Configurations</a>, Studies in Automatic Combinatorics, Volume II (1997).
%H G. Chatel, V. Pilaud, <a href="http://arxiv.org/abs/1411.3704">The Cambrian and Baxter-Cambrian Hopf Algebras</a>, arXiv preprint arXiv:1411.3704, 2014
%H Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Doignon/doignon40.html">Counting Biorders</a>, J. Integer Seqs., Vol. 6, 2003.
%H J. Cigler, <a href="http://arxiv.org/abs/1109.1449">Some nice Hankel determinants</a>, arXiv:1109.1449, 2011.
%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 Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, Leon C. Woodson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Davenport/dav3.html">The Boundary of Ordered Trees</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
%H T. Davis, <a href="http://www.geometer.org/mathcircles/catalan.pdf">Catalan Numbers</a>
%H E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/abs/math.CO/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, J. Num. Theory 117 (2006), 191-215.
%H R. M. Dickau, <a href="http://mathforum.org/advanced/robertd/catalan.html">Catalan numbers</a> (<a href="http://www-groups.dcs.st-andrews.ac.uk/~history/Miscellaneous/CatalanNumbers/catalan.html">another copy</a>)
%H T. Dokos, I. Pak, <a href="http://arxiv.org/abs/1401.0770">The expected shape of random doubly alternating Baxter permutations</a>, arXiv:1401.0770, 2014.
%H Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, <a href="http://arxiv.org/abs/1504.02513">The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r</a>, arXiv:1504.02513, 2015.
%H I. M. H. Etherington, <a href="/A000108/a000108_15.pdf">Non-associate powers and a functional equation</a>, Math. Gaz., 21 (1937), 36-39. [Annotated scanned copy]
%H I. M. H. Etherington, <a href="/A000108/a000108_13.pdf">On non-associative combinations</a>, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]
%H I. M. H. Etherington, <a href="/A000108/a000108_14.pdf">Some problems of non-associative combinations (I)</a>, Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
%H Luca Ferrari and Emanuele Munarini, <a href="http://arxiv.org/abs/1203.6792">Enumeration of edges in some lattices of paths</a>, arXiv preprint arXiv:1203.6792, 2012. - From _N. J. A. Sloane_, Oct 03 2012
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000028/">The number of stack-sorts needed to sort a permutation</a>
%H Philippe Flajolet, Éric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, <a href="http://arxiv.org/abs/math/0606370">A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics</a>, arXiv:math.CO/0606370
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 18, 35
%H D. Foata, G-N. Han, <a href="http://dx.doi.org/10.1007/s11139-009-9194-9">The doubloon polynomial triangle</a>, Ram. J. 23 (2010), 107-126
%H Dominique Foata and Guo-Niu Han, <a href="http://dx.doi.org/10.1093/qmath/hap043">Doubloons and new q-tangent numbers</a>, Quart. J. Math. 62 (2) (2011) 417-432
%H D. Foata and D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/classic.pdf">A classic proof of a recurrence for a very classical sequence</a>
%H S. Forcey, M. Kafashan, M. Maleki and M. Strayer, <a href="http://arxiv.org/abs/1212.1188">Recursive bijections for Catalan objects</a>, arXiv preprint arXiv:1212.1188, 2012.
%H H. G. Forder, <a href="/A000108/a000108_4.pdf">Some problems in combinatorics</a>, Math. Gazette, vol. 45, 1961, 199-201. [Annotated scanned copy]
%H I. Galkin, <a href="http://ulcar.uml.edu/~iag/CS/Catalan.html">Enumeration of the Binary Trees(Catalan Numbers)</a>
%H Mohammad GANJTABESH, Armin MORABBI and Jean-Marc STEYAERT, <a href="http://www.lifl.fr/SEQUOIA/Arena/Presentations/Ganjtabesh.pdf">Enumerating the number of RNA structures</a>
%H E.-K. Ghang and D. Zeilberger, <a href="http://arxiv.org/abs/1303.0885">Zeroless Arithmetic: Representing Integers ONLY using ONE</a>, arXiv preprint arXiv:1303.0885, 2013
%H A. Ghasemi, K. Sreenivas, L. K. Taylor, <a href="http://arxiv.org/abs/1309.4820">Numerical Stability and Catalan Numbers</a>, arXiv preprint arXiv:1309.4820, 2013
%H Lisa R. Goldberg, <a href="http://www.sciencedirect.com/science/article/pii/0001870891900529">Catalan numbers and branched coverings by the Riemann sphere</a>, Adv. Math. 85 (1991), No. 2, 129-144.
%H K. Gorska and K. A. Penson, <a href="http://arxiv.org/abs/1304.6008">Multidimensional Catalan and related numbers as Hausdorff moments</a>, arXiv preprint arXiv:1304.6008, 2013
%H H. W. Gould, <a href="http://www.ams.org/mathscinet-getitem?mr=2049119">Congr. Numer. 165 (2003) p 33-38</a>.
%H B. Gourevitch, <a href="http://www.pi314.net/">L'univers de Pi</a> (click Mathematiciens, Gosper)
%H Mats Granvik, <a href="http://pastebin.com/fsCtBUe1">Catalan numbers as convergents of power series</a>
%H H. G. Grundman and E. A. Teeple, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Grundman/grundman5.html">Sequences of Generalized Happy Numbers with Small Bases</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.8.
%H R. K. Guy, <a href="/A000108/a000108_11.pdf">Dissecting a polygon into triangles</a>, Research Paper #9, Math. Dept., Univ. Calgary, 1967. [Annotated scanned copy]
%H R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">J. Integer Seqs., Vol. 3 (2000), #00.1.6</a>
%H R. K. Guy and J. L. Selfridge, <a href="/A003018/a003018.pdf">The nesting and roosting habits of the laddered parenthesis</a> (annotated cached copy)
%H Mark Haiman, with an Appendix by Ezra Miller, <a href="http://math.berkeley.edu/~mhaiman/ftp/msri-talks-2002/msri-comm-alg.pdf">Commutative algebra of n points in the plane</a>, Trends Commut. Algebra, MSRI Publ 51 (2004): 153-180. [See Theorem 1.2]
%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a> [Cached copy]
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011
%H A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 259. <a href="http://tohbook.info">Book's website</a>
%H V. E. Hoggatt, Jr., <a href="/A001628/a001628.pdf">Letters to N. J. A. Sloane, 1974-1975</a>
%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 V. E. Hoggatt, Jr., and Paul S. Bruckman, <a href="http://www.fq.math.ca/Scanned/13-4/hoggatt2.pdf">The H-convolution transform</a>, Fibonacci Quart., Vol. 13(4), 1975, p. 357.
%H C. Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint arXiv:1410.2657, 2014
%H Anders Hyllengren, <a href="/A001006/a001006_5.pdf">Four integer sequences</a>, Oct 04 1985. Observes essentially that A000984 and A002426 are inverse binomial transforms of each other, as are A000108 and A001006.
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=48">Encyclopedia of Combinatorial Structures 48</a> [broken link?]
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=52">Encyclopedia of Combinatorial Structures 52</a> [broken link?]
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=71">Encyclopedia of Combinatorial Structures 71</a> [broken link?]
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=76">Encyclopedia of Combinatorial Structures 76</a> [broken link?]
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=284">Encyclopedia of Combinatorial Structures 284</a> [broken link?]
%H I. Jensen, <a href="http://www.ms.unimelb.edu.au/~iwan/polygons/Polygons_ser.html">Series exapansions for self-avoiding polygons</a>
%H S. Johnson, <a href="http://web.archive.org/web/20080129074833/http://www.saintanns.k12.ny.us/depart/math/Seth/catafrm.html">The Catalan Numbers</a>
%H A. Karttunen, <a href="/A014486/a014486.pdf">Illustration of initial terms up to size n=7</a>
%H C. Kimberling, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Kimberling/kimberling24.html">Matrix Transformations of Integer Sequences</a>, J. Integer Seqs., Vol. 6, 2003.
%H D. E. Knuth, <a href="http://arxiv.org/abs/math/9207221">Convolution polynomials</a>, The Mathematica J., 2 (1992), 67-78.
%H G. Kreweras, <a href="/A000108/a000108_1.pdf">Sur les éventails de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
%H C. Krishnamachary and M. Bheemasena Rao, <a href="/A000108/a000108_10.pdf">Determinants whose elements are Eulerian, prepared Bernoullian and other numbers</a>, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146. [Annotated scanned copy]
%H Nate Kube and Frank Ruskey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Ruskey/ruskey99.html">Sequences That Satisfy a(n-a(n))=0</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
%H W. Lang, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/LANG/lang.html">On generalizations of Stirling number triangles</a>, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H Pierre Lescanne, <a href="http://arxiv.org/abs/1312.4917">An exercise on streams: convergence acceleration</a>, arXiv preprint arXiv:1312.4917, 2013
%H Hsueh-Yung Lin, <a href="http://arxiv.org/abs/1012.1756">The odd Catalan numbers modulo 2^k</a>, Dec 08 2010.
%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 Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/TheLostCatalanNumbers">The Lost Catalan Numbers And The Schröder Tableaux</a>
%H Sara Madariaga, <a href="http://arxiv.org/abs/1304.5184">Gröbner-Shirshov bases for the non-symmetric operads of dendriform algebras and quadri-algebras</a>, arXiv:1304.5184, 2013
%H Colin L. Mallows and Lou Shapiro, <a href="http://www.cs.uwaterloo.ca/journals/JIS/MALLOWS/mallows.html">Balls on the Lawn</a>, J. Integer Sequences, Vol. 2, 1999, #5.
%H Toufik Mansour, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Mansour/mansour6.html">Counting Peaks at Height k in a Dyck Path</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.1
%H Toufik Mansour, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html">Statistics on Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
%H Toufik Mansour and Mark Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Shattuck/shattuck5.html">Counting Dyck Paths According to the Maximum Distance Between Peaks and Valleys</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.1.1.
%H Toufik Mansour and Yidong Sun, <a href="http://arxiv.org/abs/0805.1274">Identities involving Narayana polynomials and Catalan numbers</a> (2008), arXiv:0805.1274; Discrete Mathematics, Volume 309, Issue 12, Jun 28 2009, Pages 4079-4088
%H R. J. Marsh and P. P. Martin, <a href="http://arXiv.org/abs/math.CO/0612572">Pascal arrays: counting Catalan sets</a>
%H Math Forum Discussions, <a href="http://mathforum.org/kb/message.jspa?messageID=22219">The Meanings of Catalan Numbers</a>
%H Jon McCammond, <a href="http://arxiv.org/abs/math/0601687">Noncrossing partitions in surprising locations</a>, arXiv:math/0601687 [math.CO], (27-January-2006)
%H D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://www.dsi.unifi.it/~merlini/fun01.ps">Waiting patterns for a printer</a>, FUN with algorithm'01, Isola d'Elba, 2001.
%H Sam Miner and I. Pak, <a href="http://www.math.ucla.edu/~pak/papers/PermShape7.pdf">The shape of random pattern avoiding permutations</a>, 2013.
%H Marni Mishna and Lily Yen, <a href="http://arxiv.org/abs/1106.5036">Set partitions with no k-nesting</a>, arXiv:1106.5036, 2011
%H T. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1945-08486-9">The hypersurface cross ratio</a>, Bull. Amer. Math. Soc., 51 (1945), 976-984.
%H T. S. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1948-09002-4 ">Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products</a>, Bull. Amer. Math. Soc., 54 (1948), 352-360.
%H Torsten Muetze and Franziska Weber, <a href="http://arxiv.org/abs/1111.2413">Construction of 2-factors in the middle layer of the discrete cube</a>, arXiv preprint arXiv:1111.2413, 2011
%H Liviu I. Nicolaescu, <a href="http://arxiv.org/abs/math/0512496">Counting Morse functions on the 2-sphere</a>, arXiv:math/0512496.
%H J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/abs/math.CO/0405597">Free quasi-symmetric functions of arbitrary level</a>
%H R. J. Nowakowski, G. Renault, E. Lamoureux, S. Mellon and T. Miller, <a href="http://www.labri.fr/perso/grenault/NRLMM.pdf">The Game of timber!</a>, 2013.
%H C. D. Olds (Proposer) and H. W. Becker (Discussion), <a href="/A000108/a000108_6.pdf">Problem 4277</a>, Amer. Math. Monthly 56 (1949), 697-699. [Annotated scanned copy]
%H Igor Pak, <a href="http://www.math.ucla.edu/~pak/lectures/Cat/pakcat.htm">Catalan Numbers Page</a>
%H Igor Pak, <a href="http://igorpak.wordpress.com/2014/02/05/who-named-catalan-numbers/?">Who Named the Catalan Numbers?</a>
%H Igor Pak, <a href="http://arxiv.org/abs/1408.5711">History of Catalan numbers</a>, arXiv:1408.5711, 2014.
%H A. Panayotopoulos and P. Tsikouras, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Panayotopoulos/panayo4.html">Meanders and Motzkin Words</a>, J. Integer Seqs., Vol. 7, 2004.
%H A. Panholzer and H. Prodinger, <a href="http://doi.org/10.1016/S0012-365X(01)00282-5">Bijections for ternary trees and non-crossing trees</a>, Discrete Math., 250 (2002), 181-195 (see Eq. 4).
%H A. Papoulis, <a href="/A000108/a000108_8.pdf">A new method of inversion of the Laplace transform</a>, Quart. Appl. Math 14 (1957), 405-414. [Annotated scan of selected pages]
%H Robert Parviainen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Parviainen/parviainen3.html">Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.
%H P. Peart and W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/PEART/peart1.html">Generating Functions via Hankel and Stieltjes Matrices</a>, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
%H P. Peart and W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/PEART/pwatjis2.html">Dyck Paths With No Peaks at Height k</a>, J. Integer Sequences, 4 (2001), #01.1.3.
%H K. A. Penson and J.-M. Sixdeniers, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/SIXDENIERS/Catalan.html">Integral Representations of Catalan and Related Numbers</a>, J. Integer Sequences, 4 (2001), #01.2.5.
%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>, <a href="http://arxiv.org/abs/1103.3453/">arXiv version</a>; Phys. Rev E. vol. 83, 061118 (2011).
%H T. K. Petersen and Bridget Eileen Tenner, <a href="http://arxiv.org/abs/1202.4765">The depth of a permutation</a>, arXiv:1202.4765.
%H Ville H. Pettersson, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7">Enumerating Hamiltonian Cycles</a>, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
%H Vincent Pilaud, <a href="http://arxiv.org/abs/1505.07665">Brick polytopes, lattice quotients, and Hopf algebras</a>, arXiv preprint, 2015.
%H Alexander Postnikov, <a href="http://arxiv.org/abs/math/0507163">Permutohedra, associahedra, and beyond</a>, 2005, arXiv:math/0507163.
%H J.-B. Priez, A. Virmaux, <a href="http://arxiv.org/abs/1411.4161">Non-commutative Frobenius characteristic of generalized parking functions: Application to enumeration</a>, arXiv preprint arXiv:1411.4161, 2014
%H L. Pudwell, A. Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014.
%H Alon Regev, <a href="http://arxiv.org/abs/1208.3915">Enumerating Triangulations by Parallel Diagonals</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.8.5; arXiv preprint arXiv:1208.3915, 2012.
%H J. Riordan, <a href="http://www.jstor.org/stable/2005477">The distribution of crossings of chords joining pairs of 2n points on a circle</a>, Math. Comp., 29 (1975), 215-222.
%H E. Rowland, R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv preprint arXiv:1310.8635, 2013
%H E. Rowland, D. Zeilberger, <a href="http://arxiv.org/abs/1311.4776">A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences</a>, arXiv preprint arXiv:1311.4776, 2013
%H Albert Sade, <a href="/A000108/a000108_17.pdf">Sur les Chevauchements des Permutations</a>, published by the author, Marseille, 1949. [Annotated scanned copy]
%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Tsikouras/tsikouras67.html">On the Dominance Partial Ordering of Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
%H A. Sapounakis and P. Tsikouras, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Tsikouras/tsikouras43.html">On k-colored Motzkin words</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.5.
%H E. Schröder, <a href="/A000108/a000108_9.pdf">Vier combinatorische Probleme</a>, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]
%H A. Schuetz and G. Whieldon, <a href="http://arxiv.org/abs/1401.7194">Polygonal Dissections and Reversions of Series</a>, arXiv preprint arXiv:1401.7194, 2014
%H Sarah Shader, <a href="http://math.mit.edu/news/summer/RSIPapers/2013Shader.pdf">Weighted Catalan Numbers and Their Divisibility Properties</a>, Research Science Institute, MIT, 2014.
%H D. M. Silberger, <a href="/A000108/a000108_12.pdf">Occurrences of the integer (2n-2)!/n!(n-1)!</a>, Roczniki Polskiego Towarzystwa Math. 13 (1969): 91-96. [Annotated scanned copy]
%H N. J. A. Sloane, <a href="/A000108/a000108.html">Illustration of initial terms</a>
%H N. J. A. Sloane, <a href="/A000108/a000108_16.pdf">Note on Sylvester's "On reducible cyclodes" paper</a> [Scanned copy]
%H N. Solomon, S. Solomon, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Solomon/solomon8rev.html">A natural extension of Catalan Numbers</a>, JIS 11 (2008) 08.3.5
%H Frank Sottile, <a href="http://www.math.tamu.edu/~sottile/research/pages/ERAG/S4/1.html">The Schubert Calculus of Lines</a> (a section of Enumerative Real Algebraic Geometry)
%H Michael Z. Spivey and Laura L. Steil, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html">The k-Binomial Transforms and the Hankel Transform</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers.html">Hipparchus, Plutarch, Schr"oder and Hough</a>, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/ec/catalan.pdf">Exercises on Catalan and Related Numbers</a>
%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/ec#catadd">Catalan Addendum</a>
%H R. P. Stanley, <a href="/A000108/a000108.pdf">Interpretations of Catalan Numbers (Notes)</a> [Annotated scanned copy]
%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/math.CO/0509648">A combinatorial identity with application to Catalan numbers</a>, arXiv:math.CO/0509648
%H Zhi-Wei Sun and Roberto Tauraso, <a href="http://arxiv.org/abs/0709.1665">On some new congruences for binomial coefficients</a>, arXiv:0709.1665.
%H V. S. Sunder, <a href="http://www.imsc.res.in/~sunder/catalan.pdf">Catalan numbers</a>
%H P. Tarau, <a href="http://logic.cse.unt.edu/tarau/research/2013/catco.pdf">Computing with Catalan Families</a>, 2013.
%H P. Tarau, <a href="http://arxiv.org/abs/1406.1796">A Generic Numbering System based on Catalan Families of Combinatorial Objects</a>, arXiv preprint arXiv:1406.1796, 2014
%H D. Taylor, <a href="http://www.maths.usyd.edu.au/u/don/code/Catalan/Catalan.html">Catalan Structures(up to C(7))</a>
%H J.-D. Urbina, J. Kuipers, Q. Hummel, K. Richter, <a href="http://arxiv.org/abs/1409.1558">Multiparticle correlations in complex scattering and the mesoscopic Boson Sampling problem</a>, arXiv preprint arXiv:1409.1558, 2014
%H A. Vieru, <a href="http://arxiv.org/abs/1107.2938">Agoh's conjecture: its proof, its generalizations, its analogues</a>, arXiv:1107.2938, 2011.
%H Gérard Villemin, <a href="http://villemin.gerard.free.fr/aNombre/TYPDENOM/Catalan/Catalan.htm">Nombres De Catalan</a> (French)
%H D. W. Walkup, <a href="http://dx.doi.org/10.1112/S0025579300005659">The number of plane trees</a>, Mathematika, vol. 19, No. 2 (1972), 200-204.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CatalanNumber.html">Catalan Number</a>, <a href="http://mathworld.wolfram.com/BinaryBracketing.html">Binary Bracketing</a>, <a href="http://mathworld.wolfram.com/BinaryTree.html">Binary Tree</a>, <a href="http://mathworld.wolfram.com/NonassociativeProduct.html">Nonassociative Product</a>, <a href="http://mathworld.wolfram.com/StaircaseWalk.html">Staircase Walk</a>, <a href="http://mathworld.wolfram.com/DyckPath.html">Dyck Path</a>
%H J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, <a href="http://oai.cwi.nl/oai/asset/21313/21313A.pdf ">Context-free coalgebras</a>, 2013
%H Roman Witula, Damian Slota and Edyta Hetmaniok, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_41_from255to263.pdf">Bridges between different known integer sequences</a>, Annales Mathematicae et Informaticae, 41 (2013) pp. 255-263.
%H W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WOAN/hankel2.html">Hankel Matrices and Lattice Paths</a>, J. Integer Sequences, 4 (2001), #01.1.2.
%H Wen-jin Woan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Woan/woan11.html">A Recursive Relation for Weighted Motzkin Sequences</a> Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6.
%H Wen-jin Woan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Woan2/woan35.html">Animals and 2-Motzkin Paths</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.6.
%H Wen-jin Woan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Woan/woan206.html">A Relation Between Restricted and Unrestricted Weighted Motzkin Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.7.
%H F. Yano and H. Yoshida, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.050">Some set partition statistics in non-crossing partitions and generating functions</a>, Discr. Math., 307 (2007), 3147-3160.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F a(n) = A000984(n)/(n+1) = binomial(2*n, n)/(n+1) = (2*n)!/(n!*(n+1)!).
%F a(n) = binomial(2*n, n)-binomial(2*n, n-1).
%F a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).
%F a(n) = Prod_{k=2..n} (1 + n/k), if n>1.
%F G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x). G.f. A(x) satisfies A = 1 + x*A^2.
%F a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i). - Touchard
%F 2*(2*n-1)*a(n-1) = (n+1)*a(n).
%F 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
%F 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
%F Integral representation: a(n) = int(x^n*sqrt((4-x)/x), x=0..4)/(2*Pi). - _Karol A. Penson_, Apr 12 2001
%F E.g.f.: exp(2*x)*(I_0(2*x)-I_1(2*x)), where I_n is Bessel function. - _Karol A. Penson_, Oct 07 2001
%F Polygorial(n, 6)/Polygorial(n, 3). - Daniel Dockery (peritus(AT)gmail.com), Jun 24 2003
%F G.f. A(x) satisfies ((A(x) + A(-x)) / 2)^2 = A(4*x^2). - _Michael Somos_, Jun 27, 2003
%F G.f. A(x) satisfies Sum_{k>=1} k(A(x)-1)^k = Sum_{n >= 1} 4^{n-1}*x^n. - Shapiro, Woan, Getu
%F a(n+m) = Sum_{k} A039599(n, k)*A039599(m, k). - _Philippe Deléham_, Dec 22 2003
%F a(n+1) = (1/(n+1))*sum_{k=0..n} a(n-k)*binomial(2k+1, k+1). - _Philippe Deléham_, Jan 24 2004
%F a(n) = Sum_{k>=0} A008313(n, k)^2. - _Philippe Deléham_, Feb 14 2004
%F a(m+n+1) = Sum_{k>=0} A039598(m, k)*A039598(n, k). - _Philippe Deléham_, Feb 15 2004
%F a(n) = sum{k=0..n, (-1)^k*2^(n-k)*binomial(n, k)*binomial(k, floor(k/2))}. - Paul Barry, Jan 27 2005
%F 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_, Apr 23 2005
%F a((m+n)/2) = Sum_{k>=0} A053121(m, k)*A053121(n, k) if m+n is even. - _Philippe Deléham_, May 26 2005
%F E.g.f. Sum_{n>=0} a(n) * x^(2*n) / (2*n)! = BesselI(1, 2*x) / x. - _Michael Somos_, Jun 22 2005
%F Given g.f. A(x), then B(x) = x * A(x^3) satisfies 0 = f(x, B(X)) where f(u, v) = u - v + (u*v)^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
%F 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)). - _Franklin T. Adams-Watters_, Feb 08 2006
%F Sum_{k >= 1} a(k)/4^k = 1. - _Franklin T. Adams-Watters_, Jun 28 2006
%F a(n) = A047996(2*n+1, n). - _Philippe Deléham_, Jul 25 2006
%F Binomial transform of A005043. - _Philippe Deléham_, Oct 20 2006
%F a(n) = Sum_{k, 0<=k<=n}(-1)^k*A116395(n,k). - _Philippe Deléham_, Nov 07 2006
%F 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].
%F a(k) = Sum_{i=1..k} |A008276(i,k)| * (k-1)^(k-i) / k!. - _André F. Labossière_, May 29 2007
%F a(n) = Sum_{k, 0<=k<=n} A129818(n,k) * A007852(k+1). - _Philippe Deléham_, Jun 20 2007
%F a(n) = Sum_{k, 0<=k<=n} A109466(n,k) * A127632(k). - _Philippe Deléham_, Jun 20 2007
%F Row sums of triangle A124926. - _Gary W. Adamson_, Oct 22 2007
%F lim(1+Sum(a(k)/A004171(k): 0<=k<=n): n->infinity) = 4/Pi. - _Reinhard Zumkeller_, Aug 26 2008
%F a(n) = Sum_{k, 0<=k<=n}A120730(n,k)^2 and a(k+1) = Sum_{n, n>=k} A120730(n,k). - _Philippe Deléham_, Oct 18 2008
%F 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])). - _Gary W. Adamson_, Oct 27 2008
%F 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. - _Thomas Wieder_, Feb 25 2009
%F Let A(x) be the g.f., then B(x)=x*A(x) satisfies the differential equation B'(x)-2*B'(x)*B(x)-1=0. - _Vladimir Kruchinin_, Jan 18 2011
%F G.f.: 1/(1-x/(1-x/(1-x/(...)))) (continued fraction). - _Joerg Arndt_, Mar 18 2011
%F With F(x) = (1-2*x-sqrt(1-4*x))/(2*x) an o.g.f. in x for the Catalan series, G(x) = x/(1+x)^2 is the compositional inverse of F (nulling the n=0 term). - _Tom Copeland_, Sep 04 2011
%F With H(x) = 1/(dG(x)/dx) = (1+x)^3 / (1-x), the n-th Catalan number is given by (1/n!)*((H(x)*d/dx)^n)x evaluated at x=0, i.e., F(x) = exp(x*H(u)*d/du)u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)), and H(x) is the o.g.f. for A115291. - _Tom Copeland_, Sep 04 2011
%F With F(x) = {1-sqrt[1-4*x]}/2 an o.g.f. in x for the Catalan series, G(x)= x*(1-x) is the compositional inverse and this relates the Catalan numbers to the row sums of A125181. - _Tom Copeland_, Sep 30 2011
%F With H(x)=1/(dG(x)/dx)= 1/(1-2x), the n-th Catalan number (offset 1) is given by (1/n!)*((H(x)*d/dx)^n)x evaluated at x=0, i.e., F(x) = exp(x*H(u)*d/du)u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)). - _Tom Copeland_, Sep 30 2011
%F G.f.: (1-sqrt(1-4*x))/(2*x)=G(0) where G(k)=1+(4*k+1)*x/(k+1-2*x*(k+1)*(4*k+3)/(2*x*(4*k+3)+(2*k+3)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Nov 30 2011
%F E.g.f.: exp(2*x)*(BesselI(0,2*x)-BesselI(1,2*x))=G(0) where G(k)=1+(4*k+1)*x/((k+1)*(2*k+1)-x*(k+1)*(2*k+1)*(4*k+3)/(x*(4*k+3)+(k+1)*(2*k+3)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Nov 30 2011
%F E.g.f.: Hypergeometric([1/2],[2],4*x) which coincides with the e.g.f. given just above, and also by _Karol A. Penson_ further above. - _Wolfdieter Lang_, Jan 13 2012
%F a(n) = A208355(2*n-1) = A208355(2*n) for n > 0. - _Reinhard Zumkeller_, Mar 04 2012
%F G.f.: 1 + 2*x/(U(0)-2*x) where U(k)= k*(4*x+1) + 2*x + 2 - x*(2*k+3)*(2*k+4)/U(k+1); (continued fraction, Euler's 1st kind, 1-step). - _Sergei N. Gladkovskii_, Sep 20 2012
%F G.f.: hypergeom([1/2,1],[2],4*x). - _Joerg Arndt_, Apr 06 2013
%F Special values of Jacobi polynomials, in Maple notation: a(n) = 4^n*JacobiP(n,1,-1/2-n,-1)/(n+1). - _Karol A. Penson_, Jul 28 2013
%F For n > 0: a(n) = sum of row n in triangle A001263. - _Reinhard Zumkeller_, Oct 10 2013
%F a(n) = binomial(2n,n-1)/n and a(n) mod n = binomial(2n,n) mod n = A059288(n). - _Jonathan Sondow_, Dec 14 2013
%F a(n-1) = sum(t1+2*t2+...+n*tn=n, (-1)^(1+t1+t2+...+tn)*multinomial(t1+t2 +...+tn,t1,t2,...,tn)*a(1)^t1*a(2)^t2*...*a(n)^tn). - _Mircea Merca_, Feb 27 2014
%F a(n) = sum_{k=1..n} binomial(n+k-1,n)/n if n>0. _Alexander Adamchuk_, Mar 25 2014
%F a(n) = -2^(2*n+1) * binomial(n-1/2, -3/2). - _Peter Luschny_, May 06 2014
%F a(n) = (4*A000984(n)-A000984(n+1))/2. - _Stanislav Sykora_, Aug 09 2014
%F a(n) = A246458(n) * A246466(n). - _Tom Edgar_, Sep 02 2014
%F a(n) = (2*n)!*[x^(2*n)]hypergeom([],[2],x^2). - _Peter Luschny_, Jan 31 2015
%F a(n) = 4^(n-1)*hypergeom([3/2, 1-n], [3], 1). - _Peter Luschny_, Feb 03 2015
%F a(2n) = 2*A000150(2n); a(2n+1) = 2*A000150(2n+1) + a(n). - _John Bodeen_, Jun 24 2015
%e G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + ...
%e From _Joerg Arndt_ and Greg Stevenson, Jul 11 2011: (Start)
%e The following products of 3 transpositions lead to a 4-cycle in S_4:
%e (1,2)*(1,3)*(1,4);
%e (1,2)*(1,4)*(3,4);
%e (1,3)*(1,4)*(2,3);
%e (1,4)*(2,3)*(2,4);
%e (1,4)*(2,4)*(3,4). (End)
%e For n=3, a(3)=5 since there are exactly 5 binary sequences of length 7 in which the number of ones first exceed the number of zeros at entry 7, namely, 0001111, 0010111, 0011011, 0100111, and 0101011. - _Dennis P. Walsh_, Apr 11 2012
%e From _Joerg Arndt_, Jun 30 2014: (Start)
%e The a(4) = 14 branching sequences of the (ordered) trees with 4 non-root nodes are (dots denote zeros):
%e 01: [ 1 1 1 1 . ]
%e 02: [ 1 1 2 . . ]
%e 03: [ 1 2 . 1 . ]
%e 04: [ 1 2 1 . . ]
%e 05: [ 1 3 . . . ]
%e 06: [ 2 . 1 1 . ]
%e 07: [ 2 . 2 . . ]
%e 08: [ 2 1 . 1 . ]
%e 09: [ 2 1 1 . . ]
%e 10: [ 2 2 . . . ]
%e 11: [ 3 . . 1 . ]
%e 12: [ 3 . 1 . . ]
%e 13: [ 3 1 . . . ]
%e 14: [ 4 . . . . ]
%e (End)
%p A000108 := n->binomial(2*n,n)/(n+1); G000108 := (1 - sqrt(1 - 4*x)) / (2*x);
%p spec := [ A, {A=Prod(Z,Sequence(A))}, unlabeled ]: [ seq(combstruct[count](spec, size=n+1), n=0..42) ];
%p with(combstruct):bin := {B=Union(Z,Prod(B,B))}: seq(count([B,bin,unlabeled],size=n), n=1..25); # _Zerinvary Lajos_, Dec 05 2007
%p 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_, May 21 2008
%p seq((2*n)!*coeff(series(hypergeom([],[2],x^2),x,2*n+2),x,2*n),n=0..30); # _Peter Luschny_, Jan 31 2015
%t A000108[ n_ ] := (2 n)!/n!/(n+1)!
%t A000108[n_] := Hypergeometric2F1[1 - n, -n, 2, 1] (* Richard L. Ollerton, Sep 13 2006 *)
%t Table[ CatalanNumber@ n, {n, 0, 24}] (* _Robert G. Wilson v_, Feb 15 2011 *)
%t CoefficientList[InverseSeries[Series[x/Sum[x^n, {n, 0, 31}], {x, 0, 31}]]/x, x] (* _Mats Granvik_, Nov 24 2013 *)
%o (MAGMA) C:= func< n | Binomial(2*n,n)/(n+1) >; [ C(n) : n in [0..60]];
%o (PARI) a(n)=binomial(2*n,n)/(n+1) \\ _M. F. Hasler_, Aug 25 2012
%o (PARI) {a(n) = if( n<0, 0, (2*n)! / n! / (n+1)!)};
%o (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))};
%o (PARI) {a(n) = if( n<1, n==0, polcoeff( serreverse( x / (1 + x)^2 + x * O(x^n)), n))}; /* _Michael Somos_ */
%o (PARI) (recur(a,b)=if(b<=2,(a==2)+(a==b)+(a!=b)*(1+a/2), (1+a/b)*recur(a,b-1))); a(n)=recur(n,n); \\ _R. J. Cano_, Nov 22 2012
%o (Mupad) combinat::dyckWords::count(n) $ n = 0..38 // _Zerinvary Lajos_, Apr 14 2007
%o (Sage) [catalan_number(i) for i in range(27)] # _Zerinvary Lajos_, Jun 26 2008
%o (Sage) [binomial(2*i,i)-binomial(2*i,i-1) for i in xrange(0,25)] # _Zerinvary Lajos_, May 17 2009
%o (MAGMA) [Catalan(n): n in [0..40]]; // _Vincenzo Librandi_, Apr 02 2011
%o (Haskell)
%o import Data.List (genericIndex)
%o a000108 n = genericIndex a000108_list n
%o a000108_list = 1 : catalan [1] where
%o catalan cs = c : catalan (c:cs) where
%o c = sum $ zipWith (*) cs $ reverse cs
%o -- _Reinhard Zumkeller_, Nov 12 2011
%o a000108 = map last $ iterate (scanl1 (+) . (++ [0])) [1]
%o -- _David Spies_, Aug 23 2015
%o (Sage) # Generalized algorithm of L. Seidel
%o def A000108_list(n) :
%o D = [0]*(n+1); D[1] = 1
%o b = True; h = 1; R = []
%o for i in range(2*n-1) :
%o if b :
%o for k in range(h,0,-1) : D[k] += D[k-1]
%o h += 1; R.append(D[1])
%o else :
%o for k in range(1,h, 1) : D[k] += D[k+1]
%o b = not b
%o return R
%o A000108_list(31) # _Peter Luschny_, Jun 02 2012
%o (Maxima) A000108(n):=binomial(2*n,n)/(n+1)$ makelist(A000108(n),n,0,30); [_Martin Ettl_, Oct 24 2012]
%o (Python)
%o from gmpy2 import divexact
%o A000108 = [1, 1]
%o for n in range(1,10**3):
%o ....A000108.append(divexact(A000108[-1]*(4*n+2),(n+2)))
%o # _Chai Wah Wu_, Aug 31 2014
%Y Cf. A000984, A001453, A002420, A048990, A024492, A000142, A022553, A039599, A003046, A069640, A094216, A094638, A014137, A014138, A094639, A099731, A008549, A008276, A094638, (|A008276|), A094216, A094639, A000984, A000245, A002057, A000344, A003517, A000588, A003518, A003519, A001392, A124926, A098597, A086117, A137697, A000957, A068875, A032443, A179277, A154559, A059288, A129763, A003046, A032357, A014140, A120304, A211611, A119822, A129763, A167892, A167893, A161581, A006480, A001791.
%Y A row of A060854.
%Y See A001003, A001190, A001699, A000081 for other ways to count parentheses.
%Y Enumerates objects encoded by A014486.
%Y A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
%Y Cf. A051168 (diagonal of the square array described).
%Y Cf. A033552, A176137 (partitions into Catalan numbers).
%Y Cf. A000753, A000736 (Boustrophedon transforms).
%Y Cf. A120303 (largest prime factor of Catalan number).
%Y Cf. A121839 (reciprocal Catalan constant).
%Y Cf. A038003, A119861, A119908, A120274, A120275 (odd Catalan number).
%Y Cf. A002390 (decimal expansion of natural logarithm of golden ratio).
%Y Coefficients of square root of the g.f. are A001795/A046161. - _N. J. A. Sloane_, Aug 26 2015
%K core,nonn,easy,eigen,nice,changed
%O 0,3
%A _N. J. A. Sloane_
|
