Search: id:A000108 Results 1-1 of 1 results found. %I A000108 M1459 N0577 %S A000108 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900, %T A000108 2674440,9694845,35357670,129644790,477638700,1767263190, %U A000108 6564120420,24466267020,91482563640,343059613650,1289904147324 %N A000108 Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Also called Segner numbers. %C A000108 The solution to Schroeder's first problem. A very large number of combinatorial interpretations are known - see references, esp. Stanley, Enumerative Combinatorics, Volume 2. %C A000108 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))). %C A000108 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] %C A000108 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. %C A000108 Shifts one place left when convolved with itself. %C A000108 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 A000108 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 A000108 Arises in Schubert calculus - see Sottile reference. %C A000108 Inverse Euler transform of sequence is A022553. %C A000108 With interpolated zeros, the inverse binomial transform of the Motzkin numbers A001006. - Paul Barry (pbarry(AT)wit.ie), Jul 18 2003 %C A000108 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 A000108 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 %C A000108 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 %C A000108 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 %C A000108 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], ... %C A000108 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 %C A000108 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 %C A000108 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. %C A000108 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 %C A000108 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] %C A000108 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] %C A000108 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] %C A000108 lim(a(n)/a(n-1): n->infinity) = 4 [From Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008] %C A000108 Starting with offset 1 = row sums of triangle A154559 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 11 2009] %C A000108 Contribution from Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009: (Start) %C A000108 C(n) is the degree of the Grassmanian G(1,n+1): the set of lines in %C A000108 (n+1)-dimensional projective space, or the set of planes through the origin in %C A000108 (n+2)-dimensional affine space. The Grassmanian is considered a subset of %C A000108 N-dimensional projective space, N = binomial(n+2,2) - 1. If we choose 2n %C A000108 general (n-1)-planes in projective (n+1)-space, then there are C(n) lines that %C A000108 meet all of them. (End) %C A000108 Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 01 2009: (Start) %C A000108 Starting with offset 1 = A068875: (1, 2, 4, 10, 18, 84,...) convolved with %C A000108 Fine numbers, A000957: (1, 0, 1, 2, 6, 18,...). a(6) = 132 = %C A000108 (1, 2, 4, 10, 28, 84) dot (18, 6, 2, 1, 0, 1) = (18 + 12 + 8 + 10 + 0 + 84) = 132. (End) %C A000108 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] %C A000108 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] %C A000108 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) ) [From Groux roland (roland.groux(AT)orange.fr), Nov 13 2009] %D A000108 The large number of references and links demonstrates the ubiquity of the Catalan numbers. %D A000108 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 A000108 R. Alter and K. K. Kubota, Prime and prime power divisibility of Catalan numbers, J. Combinatorial Theory, Ser. A, 15 (1973), 243-256. %D A000108 D. F. Bailey, Counting Arrangements of 1's and -1's, Mathematics Magazine 69(2) 128-131 1996. %D A000108 I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785. %D A000108 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. %D A000108 E. Barcucci, A. Frosini and S. Rinaldi, On directed-convex polyominoes in a rectangle, Discr. Math., 298 (2005). 62-78. %D A000108 Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5. %D A000108 Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4. %D A000108 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 A000108 F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112. %D A000108 A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, preprint, 2007. %D A000108 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 A000108 W. G. Brown, Historical note on a recurrent combinatorial problem, Amer. Math. Monthly, 72 (1965), 973-977. %D A000108 D. Callan, A combinatorial interpretation of a Catalan numbers identity, Math. Mag., 72 (1999), 295-298. %D A000108 D. Callan, The maximum associativeness of division, Problem 11091, Amer. Math. Monthly, 113 (#5, 2006), 462-463. %D A000108 David Callan, A Combinatorial Interpretation for a Super-Catalan Recurrence, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.8. %D A000108 David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4. %D A000108 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. %D A000108 Chung, Kai Lai; Feller, W., On fluctuations in coin-tossing. Proc. Nat. Acad. Sci. U. S. A. 35, (1949). 605-608. %D A000108 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 53. %D A000108 J. H. Conway and R. K. Guy, The Book of Numbers, New York: Springer-Verlag, 1995, ch. 4, pp 96-106. %D A000108 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.). %D A000108 E. Deutsch, Dyck path enumeration, Discrete Math., 204, 167-202, 1999. %D A000108 E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265. %D A000108 E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001. %D A000108 S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105. %D A000108 A. Errara, Analysis situs: une probleme d'enumeration, Memoires Acad. Bruxelles, Series 2, Vol. 11, No. 6, 26pp. %D A000108 K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167. %D A000108 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 A000108 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 A000108 H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201. %D A000108 J. R. Gaggins, Constructing the Centroid of a Polygon, Math. Gaz., 61 (1988), 211-212. %D A000108 M. Gardner, Time Travel and Other Mathematical Bewilderments, Chap. 20 pp. 253-266 W. H. Freeman NY 1988. %D A000108 James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261). %D A000108 H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971. %D A000108 Alain Goupil and Gilles Schaeffer, Factoring N-Cycles and Counting Maps of Given Genus . Europ. J. Combinatorics (1998) 19 819-834. %D A000108 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 530. %D A000108 N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221. %D A000108 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.23). %D A000108 B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 513, Eq. (7.282). %D A000108 M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87. %D A000108 D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.6. %D A000108 Thomas Koshy and Mohammad Salmassi, "Parity and Primality of Catalan Numbers", College Mathematics Journal, Vol. 37, No. 1 (Jan 2006), pp. 52-53. %D A000108 M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362. %D A000108 Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5. %D A000108 P. J. Larcombe, On pre-Catalan Catalan numbers: Kotelnikow (1766), Mathematics Today, 35 (1999), p. 25. %D A000108 P. J. Larcombe, On the history of the Catalan numbers: a first record in China, Mathematics Today, 35 (1999), p. 89. %D A000108 P. J. Larcombe, The 18th century Chinese discovery of the Catalan numbers, Math. Spectrum, 32 (1999/2000), 5-7. %D A000108 P. J. Larcombe and P. D. C. Wilson, On the trail of the Catalan sequence, Mathematics Today, 34 (1998), 114-117. %D A000108 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 A000108 G. S. Lueker, Some techniques for solving recurrences, Computing Surveys, 12 (1980), 419-436. %D A000108 J. J. Luo, Antu Ming, the first inventor of Catalan numbers in the world [in Chinese], Neimenggu Daxue Xuebao, 19 (1998), 239-245. %D A000108 Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5. %D A000108 D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344. %D A000108 C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly, 64 (1957), 143-154. %D A000108 A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4). %D A000108 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. %D A000108 S. G. Penrice, Stacks, bracketings and CG-arrangements, Math. Mag., 72 (1999), 321-324. %D A000108 C. A. Pickover, Wonders of Numbers, Chap. 71, Oxford Univ. Press NY 2000. %D A000108 R. Read, "Counting Binary Trees" in 'The Mathematical Gardner', D. A. Klarner Ed. pp. 331-334, Wadsworth CA 1989. %D A000108 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 A000108 J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101. %D A000108 J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222. %D A000108 T. Santiago Costa Oliveira, "Catalan traffic" and integrals on the Grassmannian of lines, Discr. Math., 308 (2007), 148-152. %D A000108 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. %D A000108 A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924. %D A000108 E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376. %D A000108 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 A000108 L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory, A 20 (1976), 375-376. %D A000108 L. W. Shapiro, W.-J. Woan and S. Getu, The Catalan numbers via the World Series, Math. Mag., 66 (1993), 20-22. %D A000108 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). %D A000108 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %D A000108 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. %D A000108 R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, Vol. 2, 1999; see especially Chapter 6. %D A000108 R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68. %D A000108 Zhi-Wei Sun and Roberto Tauraso, Congruences involving Catalan numbers, arXiv:0709.1665v5. %D A000108 I. Vun and P. Belcher, Catalan numbers, Mathematical Spectrum, 30 (1997/ 1998), 3-5. %D A000108 D. Wells, Penguin Dictionary of Curious and Interesting Numbers, Entry 42 p 121, Penguin Books, 1987. %D A000108 Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6. %D A000108 Wen-jin Woan, A Relation Between Restricted and Unrestricted Weighted Motzkin Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.7. %D A000108 Wen-jin Woan, Animals and 2-Motzkin Paths, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.6. %D A000108 F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160. %D A000108 Liviu I. Nicolaescu, Counting Morse functions on the 2-sphere, arXiv:math/ 0512496. %D A000108 Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71. %D A000108 M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563. %D A000108 A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469. %D A000108 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] %D A000108 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] %D A000108 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] %D A000108 Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669. %D A000108 Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577. %D A000108 Dominique Foata and Guo-Niu Han, Dimers and new q-tangent numbers, Preprint, 2008. %D A000108 Dominique Foata and Guo-Niu Han, The dimer polynomial triangle, Preprint, 2008. %D A000108 S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964. %D A000108 R. H. Jeurissen, Raney and Catalan, Discrete Math., 308 (2008), 6298-6307. %D A000108 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] %D A000108 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] %H A000108 N. J. A. Sloane, The first 200 Catalan numbers %H A000108 Joerg Arndt, Fxtbook %H A000108 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).) %H A000108 John Baez, This week's finds in mathematical physics, Week 202 %H A000108 E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences %H A000108 M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. %H A000108 D. Bill, Durango Bill's Enumeration of Binary Trees %H A000108 H. Bottomley, Catalan Space Invaders %H A000108 H. Bottomley, Illustration for A000108, A001147, A002694, A067310 and A067311 %H A000108 T. Bourgeron, Montagnards et polygones %H A000108 M. Bousquet-Melou and Gilles Schaeffer, Walks on the slit plane, Probability Theory and Related Fields, Vol. 124, no. 3 (2002), 305-344. %H A000108 K. S. Brown's Mathpages, The Meanings of Catalan Numbers %H A000108 B. Bukh, PlanetMath.org, Catalan numbers %H A000108 Alexander Burstein, Sergi Elizalde and Toufik Mansour, Restricted Dumont permutations, Dyck paths and noncrossing partitions, arXiv math.CO/0610234. %H A000108 N. T. Cameron, Random walks, trees and extensions of Riordan group techniques %H A000108 P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5. %H A000108 F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997). %H A000108 Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seqs., Vol. 6, 2003. %H A000108 T. Davis, Catalan Numbers %H A000108 E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215. %H A000108 R. M. Dickau, Catalan numbers %H A000108 R. M. Dickau, Catalan Numbers (another copy) %H A000108 D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence %H A000108 I. Galkin, Enumeration of the Binary Trees(Catalan Numbers) %H A000108 H. W. Gould, Congr. Numer. 165 (2003) p 33-38. %H A000108 B. Gourevitch, L'univers de Pi (click Mathematiciens, Gosper) %H A000108 R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6 %H A000108 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 48 %H A000108 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 52 %H A000108 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 71 %H A000108 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 76 %H A000108 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 284 %H A000108 I. Jensen, Series exapansions for self-avoiding polygons %H A000108 S. Johnson, The Catalan Numbers %H A000108 A. Karttunen, Illustration of initial terms up to size n=7 %H A000108 C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003. %H A000108 A. F. Labossiere, Sobalian Coefficients. %H A000108 A. F. Labossiere, Miscellaneous. %H A000108 W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4. %H A000108 J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5. %H A000108 Colin L. Mallows and Lou Shapiro, Balls on the Lawn, J. Integer Sequences, Vol. 2, 1999, #5. %H A000108 Toufik Mansour, Counting Peaks at Height k in a Dyck Path, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.1 %H A000108 R. J. Marsh and P. P. Martin, Pascal arrays: counting Catalan sets %H A000108 D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001. %H A000108 A. Panayotopoulos and P. Tsikouras, Meanders and Motzkin Words, J. Integer Seqs., Vol. 7, 2004. %H A000108 A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4). %H A000108 P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1. %H A000108 P. Peart and W.-J. Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, 4 (2001), #01.1.3. %H A000108 K. A. Penson and J.-M. Sixdeniers, Integral Representations of Catalan and Related Numbers, J. Integer Sequences, 4 (2001), #01.2.5. %H A000108 A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.5. %H A000108 N. J. A. Sloane, Illustration of initial terms %H A000108 Frank Sottile, The Schubert Calculus of Lines (a section of Enumerative Real Algebraic Geometry) %H A000108 R. P. Stanley, Hipparchus, Plutarch, Schr"oder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997. %H A000108 R. P. Stanley, Exercises on Catalan and Related Numbers %H A000108 R. P. Stanley, Catalan Addendum %H A000108 Zhi-Wei Sun, A combinatorial identity with application to Catalan numbers %H A000108 D. Taylor, Catalan Structures(up to C(7)) %H A000108 G. Villemin's Almanac of Numbers, Nombres De Catalan %H A000108 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1). %H A000108 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2). %H A000108 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (3). %H A000108 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (4). %H A000108 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (5). %H A000108 Eric Weisstein's World of Mathematics, Dyck Path %H A000108 W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2. %H A000108 Index entries for "core" sequences %H A000108 Index entries for sequences related to rooted trees %H A000108 Index entries for sequences related to parenthesizing %H A000108 Index entries for sequences related to necklaces %H A000108 P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18, 35 %F A000108 a(n) = binomial(2n, n)/(n+1) = (2n)!/(n!(n+1)!). %F A000108 a(n) = binomial(2n, n)-binomial(2n, n-1) %F A000108 a(n) = Sum_{k=0..n-1} a(k)a(n-1-k). %F A000108 G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x). G.f. A(x) satisfies A = 1 + x*A^2. %F A000108 a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i) - Touchard. %F A000108 2(2n-1)a(n-1) = (n+1)a(n). %F A000108 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 A000108 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 A000108 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 %F A000108 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 %F A000108 Polygorial(n, 6)/Polygorial(n, 3) - Daniel Dockery (peritus(AT)gmail.com) Jun 24, 2003 %F A000108 G.f. A(x) satisfies ((A(x)+A(-x))/2)^2 = A(4*x^2). - Michael Somos, Jun 27, 2003 %F A000108 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 A000108 a(n+m) = Sum_{k} A039599(n, k)*A039599(m, k). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Dec 22 2003 %F A000108 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 %F A000108 a(n) = Sum_{k>=0} A008313(n, k)^2 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 14 2004 %F A000108 a(m+n+1) = Sum_{k>=0} A039598(m, k)*A039598(n, k) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 15 2004 %F A000108 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 %F A000108 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 %F A000108 a((m+n)/2) = Sum_{k>=0} A053121(m, k)*A053121(n, k) if m+n is even . - Philippe DELEHAM, May 26 2005 %F A000108 E.g.f. Sum_{n>=0} a(n)*x^(2n)/(2n)! = BesselI(1, 2x)/x . - Michael Somos Jun 22 2005 %F A000108 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 %F A000108 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 %F A000108 Sum_{k=1}^{infinity} a(k)/4^k = 1. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Jun 28 2006 %F A000108 a(n) = A047996(2*n+1,n) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jul 25 2006 %F A000108 Binomial transform of A005043 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 20 2006 %F A000108 a(n)=Sum_{k, 0<=k<=n}(-1)^k*A116395(n,k) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 07 2006 %F A000108 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 A000108 a(k) = Sum_{i=1..k} |A008276(i,k)| * (k-1)^(k-i) / k! - Andre F. Labossiere (boronali(AT)laposte.net), May 29 2007 %F A000108 a(n)=Sum_{k, 0<=k<=n}A129818(n,k)*A007852(k+1). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 20 2007 %F A000108 a(n)=Sum_{k, 0<=k<=n}A109466(n,k)*A127632(k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 20 2007 %F A000108 Row sums of triangle A124926 - Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 22 2007 %F A000108 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 %F A000108 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] %F A000108 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] %F A000108 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])). %F A000108 Formula from Thomas Wieder (wieder.thomas(AT)t-online.de), Feb 25 2009: %F A000108 a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1} %F A000108 delta(l_1,l_2,...,l_i,...,l_n) %F A000108 where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i < l_(i+1) and l_(i+1) <> 0 %F A000108 for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. %F A000108 a(n) = C(2*n,n)-C(2*n,n-1) . [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 17 2009] %p A000108 A000108 := n->binomial(2*n,n)/(n+1); G000108 := (1 - sqrt(1 - 4*x)) / (2*x); %p A000108 spec := [ A, {A=Prod(Z,Sequence(A))}, unlabeled ]: [ seq(combstruct[count](spec, size=n), n=0..42) ]; %p A000108 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 %p A000108 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 %t A000108 A000108[ n_ ] := (2 n)!/n!/(n+1)! %t A000108 A000108[n_]:=Hypergeometric2F1[1-n,-n,2,1] - Richard L. Ollerton (r.ollerton(AT)uws.edu.au), Sep 13 2006 %o A000108 (MAGMA) C:= func< n | Binomial(2*n,n)/(n+1) >; [ C(n) : n in [0..60]]; %o A000108 (PARI) a(n)=if(n<0,0,(2*n)!/n!/(n+1)!) %o A000108 (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 A000108 (PARI) a(n)=if(n<1,n==0,polcoeff(serreverse(x/(1+x)^2+x*O(x^n)),n)) (from Michael Somos) %o A000108 (Mupad) combinat::dyckWords::count(n) $ n = 0..38 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 14 2007 %o A000108 sage: [catalan_number(i) for i in range(27)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 26 2008 %o A000108 (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] %Y A000108 Cf. A000984, A002420, A048990, A024492, A000142, A022553. A row of A060854. %Y A000108 Cf. A039599, A094216, A094638, A014137, A094639, A099731, A008549. %Y A000108 See A001003, A001190, A001699, A000081 for other ways to count parentheses. %Y A000108 Enumerates objects encoded by A014486. %Y A000108 Cf. A008276, A094638 (|A008276|), A094216, A094639, A000984. %Y A000108 A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072. %Y A000108 Cf. A000108 A000245 A002057 A000344 A003517 A000588 A003518 A003519 A001392. %Y A000108 Cf. A124926. %Y A000108 Cf. A098597, A086117, A137697. %Y A000108 A diagonal of the square array described in A051168. %Y A000108 A154559 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 11 2009] %Y A000108 A000957, A068875 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 01 2009] %Y A000108 A032443 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 15 2009] %Y A000108 Sequence in context: A054394 A036769 A033191 this_sequence A115140 A120588 A057413 %Y A000108 Adjacent sequences: A000105 A000106 A000107 this_sequence A000109 A000110 A000111 %K A000108 core,nonn,easy,eigen,nice,new %O A000108 0,3 %A A000108 N. J. A. Sloane (njas(AT)research.att.com). Search completed in 0.011 seconds