A000108 - OEIS

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A000108 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A000108" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA000108">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A000108 - OEIS"></a> </div> <div class="motdbox"> <div class="motd"> <p>Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).</p> </div> <div class="donate"> <div id="donate-button-container"> <div id="donate-button"></div> <script src="https://www.paypalobjects.com/donate/sdk/donate-sdk.js" charset="UTF-8"></script> <script> PayPal.Donation.Button({ env:'production', hosted_button_id:'SVPGSDDCJ734A', image: { src:'https://www.paypalobjects.com/en_US/i/btn/btn_donateCC_LG.gif', alt:'Donate with PayPal button', title:'PayPal - The safer, easier way to pay online!', } }).render('#donate-button'); </script> </div> <a href="https://oeisf.org/donate/"> <strong>Other ways to Give</strong> </a> </div> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A000108 </div> <div class=seqname> Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). <br><font size=-1>(Formerly M1459 N0577)</font> </div> </div> <div class=scorerefs> 4075 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304</div> <div class=seqdatalinks> (<a href="/A000108/list">list</a>; <a href="/A000108/graph">graph</a>; <a href="/search?q=A000108+-id:A000108">refs</a>; <a href="/A000108/listen">listen</a>; <a href="/history?seq=A000108">history</a>; <a href="/search?q=id:A000108&fmt=text">text</a>; <a href="/A000108/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,3</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>These were formerly sometimes called Segner numbers.</div> <div class=sectline>A very large number of combinatorial interpretations are known - see references, esp. R. P. Stanley, "Catalan Numbers", Cambridge University Press, 2015. This is probably the longest entry in the OEIS, and rightly so.</div> <div class=sectline>The solution to Schröder's first problem: 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))).</div> <div class=sectline>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]</div> <div class=sectline>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. - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Jul 11 2011</div> <div class=sectline>a(n-1) is the number of ways of expressing an n-cycle (123...n) 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_i<v_i and u_k <= u_j for k < j; see example. If the condition is dropped, one obtains <a href="/A000272" title="Number of trees on n labeled nodes: n^(n-2) with a(0)=1.">A000272</a>. - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a> and Greg Stevenson, Jul 11 2011</div> <div class=sectline>Noncrossing partitions are partitions of genus 0. - <a href="/wiki/User:Robert_Coquereaux">Robert Coquereaux</a>, Feb 13 2024</div> <div class=sectline>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. - <a href="/wiki/User:Wolfdieter_Lang">Wolfdieter Lang</a>, Aug 07 2007</div> <div class=sectline>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)=<a href="/A001761" title="a(n) = (2*n)!/(n+1)!.">A001761</a>(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)!. - <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Feb 22 2012</div> <div class=sectline>Shifts one place left when convolved with itself.</div> <div class=sectline>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</div> <div class=sectline>Number of ways of joining 2n points on a circle to form n nonintersecting chords. (If no such restriction imposed, then the number of ways of forming n chords is given by (2n-1)!! = (2n)!/(n!*2^n) = <a href="/A001147" title="Double factorial of odd numbers: a(n) = (2*n-1)!! = 1*3*5*...*(2*n-1).">A001147</a>(n).)</div> <div class=sectline>Arises in Schubert calculus - see Sottile reference.</div> <div class=sectline>Inverse Euler transform of sequence is <a href="/A022553" title="Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n o...">A022553</a>.</div> <div class=sectline>With interpolated zeros, the inverse binomial transform of the Motzkin numbers <a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Jul 18 2003</div> <div class=sectline>The Hankel transforms of this sequence or of this sequence with the first term omitted give <a href="/A000012" title="The simplest sequence of positive numbers: the all 1's sequence.">A000012</a> = 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. - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Mar 04 2004</div> <div class=sectline>a(n) equals the sum of squares of terms in row n of triangle <a href="/A053121" title="Catalan triangle (with 0's) read by rows.">A053121</a>, which is formed from successive self-convolutions of the Catalan sequence. - <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Apr 23 2005</div> <div class=sectline>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</div> <div class=sectline>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. - <a href="/wiki/User:Franklin_T._Adams-Watters">Franklin T. Adams-Watters</a>, Feb 08 2006</div> <div class=sectline>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? - <a href="/wiki/User:Jonathan_Vos_Post">Jonathan Vos Post</a>, Mar 06 2006</div> <div class=sectline>The answer is yes. Using the formula C_n = binomial(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. - <a href="/wiki/User:Franklin_T._Adams-Watters">Franklin T. Adams-Watters</a>, Apr 14 2006</div> <div class=sectline>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). - <a href="/wiki/User:Dennis_P._Walsh">Dennis P. Walsh</a>, Dec 04 2006</div> <div class=sectline>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. - <a href="/wiki/User:Abdullahi_Umar">Abdullahi Umar</a>, Aug 25 2008</div> <div class=sectline>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</div> <div class=sectline>The invert transform appears to converge to the Catalan numbers when applied infinitely many times to any starting sequence. - <a href="/wiki/User:Mats_Granvik">Mats Granvik</a>, <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a> and <a href="/wiki/User:Roger_L._Bagula">Roger L. Bagula</a>, Sep 09 2008, Sep 12 2008</div> <div class=sectline>Limit_{n->oo} a(n)/a(n-1) = 4. - Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008</div> <div class=sectline>Starting with offset 1 = row sums of triangle <a href="/A154559" title="Triangle read by rows, A007318 * (A129186 * (A001006 * 0^(n-k))).">A154559</a>. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Jan 11 2009</div> <div class=sectline>C(n) is the degree of the Grassmannian 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 Grassmannian 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</div> <div class=sectline>Starting with offset 1 = <a href="/A068875" title="Expansion of (1 + x*C)*C, where C = (1 - (1 - 4*x)^(1/2))/(2*x) is the g.f. for Catalan numbers, A000108.">A068875</a>: (1, 2, 4, 10, 18, 84, ...) convolved with Fine numbers, <a href="/A000957" title="Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with...">A000957</a>: (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. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, May 01 2009</div> <div class=sectline>Convolved with <a href="/A032443" title="a(n) = Sum_{i=0..n} binomial(2*n, i).">A032443</a>: (1, 3, 11, 42, 163, ...) = powers of 4, <a href="/A000302" title="Powers of 4: a(n) = 4^n.">A000302</a>: (1, 4, 16, ...). - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, May 15 2009</div> <div class=sectline>Sum_{k>=1} C(k-1)/2^(2k-1) = 1. The k-th term in the summation is the probability that a random walk on the integers (beginning at the origin) will arrive at positive one (for the first time) in exactly (2k-1) steps. - <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Sep 12 2009</div> <div class=sectline>C(p+q)-C(p)*C(q) = Sum_{i=0..p-1, j=0..q-1} C(i)*C(j)*C(p+q-i-j-1). - <a href="/wiki/User:Groux_Roland">Groux Roland</a>, Nov 13 2009</div> <div class=sectline>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.) - <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Mar 13 2010</div> <div class=sectline>Let <a href="/A179277" title="A(x) = C(x) * C(x^2) * C(x^4) * C(x^8) *...; C = Catalan, A000108.">A179277</a> = A(x). Then C(x) is satisfied by A(x)/A(x^2). - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Jul 07 2010</div> <div class=sectline>a(n) is also the number of quivers in the mutation class of type B_n or of type C_n. - <a href="/wiki/User:Christian_Stump">Christian Stump</a>, Nov 02 2010</div> <div class=sectline>From <a href="/wiki/User:Matthew_Vandermast">Matthew Vandermast</a>, Nov 22 2010: (Start)</div> <div class=sectline>Consider a set of <a href="/A000217" title="Triangular numbers: a(n) = binomial(n+1,2) = n*(n+1)/2 = 0 + 1 + 2 + ... + n.">A000217</a>(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.</div> <div class=sectline>If the second requirement is lifted, the number of acceptable ways equals <a href="/A000110" title="Bell or exponential numbers: number of ways to partition a set of n labeled elements.">A000110</a>(n+1). See related comments for <a href="/A016098" title="Number of crossing set partitions of {1,2,...,n}.">A016098</a>, <a href="/A085082" title="Number of distinct prime signatures arising among the divisors of n.">A085082</a>. (End)</div> <div class=sectline>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). - <a href="/wiki/User:Jonathan_Vos_Post">Jonathan Vos Post</a>, Dec 09 2010</div> <div class=sectline>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). - <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Dec 16 2010</div> <div class=sectline>Postnikov (2005) defines "generalized Catalan numbers" associated with buildings (e.g., Catalan numbers of Type B, see <a href="/A000984" title="Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.">A000984</a>). - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Dec 10 2011</div> <div class=sectline>Number of permutations in S(n) for which length equals depth. - <a href="/wiki/User:Bridget_Tenner">Bridget Tenner</a>, Feb 22 2012</div> <div class=sectline>a(n) is also the number of standard Young tableau of shape (n,n). - <a href="/wiki/User:Thotsaporn_Thanatipanonda">Thotsaporn Thanatipanonda</a>, Feb 25 2012</div> <div class=sectline>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. - <a href="/wiki/User:Dennis_P._Walsh">Dennis P. Walsh</a>, Apr 11 2012</div> <div class=sectline>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. - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Nov 12 2012</div> <div class=sectline>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. - <a href="/wiki/User:Jon_Perry">Jon Perry</a>, Nov 16 2012</div> <div class=sectline>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. - <a href="/wiki/User:José_Luis_Ramírez_Ramírez">José Luis Ramírez Ramírez</a>, Jan 16 2013</div> <div class=sectline>If p is an odd prime, then (-1)^((p-1)/2)*a((p-1)/2) mod p = 2. - <a href="/wiki/User:Gary_Detlefs">Gary Detlefs</a>, Feb 20 2013</div> <div class=sectline>Conjecture: For any positive integer n, the polynomial Sum_{k=0..n} a(k)*x^k is irreducible over the field of rational numbers. - <a href="/wiki/User:Zhi-Wei_Sun">Zhi-Wei Sun</a>, Mar 23 2013</div> <div class=sectline>a(n) is the size of the Jones monoid on 2n points (cf. <a href="/A225798" title="The number of idempotents in the Jones (or Temperley-Lieb) monoid on the set [1..n].">A225798</a>). - <a href="/wiki/User:James_Mitchell">James Mitchell</a>, Jul 28 2013</div> <div class=sectline>For 0 < p < 1, define f(p) = Sum_{n>=0} a(n)*(p*(1-p))^n, then f(p) = min{1/p, 1/(1-p)}, so f(p) reaches its maximum value 2 at p = 0.5, and p*f(p) is constant 1 for 0.5 <= p < 1. - <a href="/wiki/User:Bob_Selcoe">Bob Selcoe</a>, Nov 16 2013 [Corrected by <a href="/wiki/User:Jianing_Song">Jianing Song</a>, May 21 2021]</div> <div class=sectline>No a(n) has the form x^m with m > 1 and x > 1. - <a href="/wiki/User:Zhi-Wei_Sun">Zhi-Wei Sun</a>, Dec 02 2013</div> <div class=sectline>From <a href="/wiki/User:Alexander_Adamchuk">Alexander Adamchuk</a>, Dec 27 2013: (Start)</div> <div class=sectline>Prime p divides a((p+1)/2) for p > 3. See <a href="/A120303" title="Largest prime factor of Catalan number A000108(n).">A120303</a>(n) = Largest prime factor of Catalan number.</div> <div class=sectline>Reciprocal Catalan Constant C = 1 + 4*sqrt(3)*Pi/27 = 1.80613.. = <a href="/A121839" title="Decimal expansion of Sum_{k>=1} 1/C(k), where C(k) is a Catalan Number (A000108).">A121839</a>.</div> <div class=sectline>Log(Phi) = (125*C - 55) / (24*sqrt(5)), where C = Sum_{k>=1} (-1)^(k+1)*1/a(k). See <a href="/A002390" title="Decimal expansion of natural logarithm of golden ratio.">A002390</a> = Decimal expansion of natural logarithm of golden ratio.</div> <div class=sectline>3-d analog of the Catalan numbers: (3n)!/(n!(n+1)!(n+2)!) = <a href="/A161581" title="a(n) = (3n)!/(n!(n+1)!(n+2)!).">A161581</a>(n) = <a href="/A006480" title="De Bruijn's S(3,n): (3n)!/(n!)^3.">A006480</a>(n) / ((n+1)^2*(n+2)), where <a href="/A006480" title="De Bruijn's S(3,n): (3n)!/(n!)^3.">A006480</a>(n) = (3n)!/(n!)^3 De Bruijn's S(3,n). (End)</div> <div class=sectline>For a relation to the inviscid Burgers's, or Hopf, equation, see <a href="/A001764" title="a(n) = binomial(3*n,n)/(2*n+1) (enumerates ternary trees and also noncrossing trees).">A001764</a>. - <a href="/wiki/User:Tom_Copeland">Tom Copeland</a>, Feb 15 2014</div> <div class=sectline>From <a href="/wiki/User:Fung_Lam">Fung Lam</a>, May 01 2014: (Start)</div> <div class=sectline>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.</div> <div class=sectline>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).</div> <div class=sectline>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.</div> <div class=sectline>Special cases are <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a> (q=1), <a href="/A068764" title="Generalized Catalan numbers.">A068764</a> to <a href="/A068772" title="Generalized Catalan numbers.">A068772</a> (q=2 to 10), <a href="/A240880" title="Expansion of g.f.: (-1 + sqrt(1+12*x+48*x^2)) / (6*x).">A240880</a> (q=-3).</div> <div class=sectline>(End)</div> <div class=sectline>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. - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Jun 30 2014</div> <div class=sectline>Number of stack-sortable permutations of [n], these are the 231-avoiding permutations; see the Bousquet-Mélou reference. - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Jul 01 2014</div> <div class=sectline>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 <a href="/A245894" title="Number of labeled increasing binary trees on 2n-1 nodes whose breadth-first reading word avoids 231.">A245894</a>. - <a href="/wiki/User:Manda_Riehl">Manda Riehl</a>, Aug 07 2014</div> <div class=sectline>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). - <a href="/wiki/User:Joachim_Wuttke">Joachim Wuttke</a>, Sep 11 2014</div> <div class=sectline>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, <a href="/A005043" title="Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).">A005043</a>), Fibonacci (<a href="/A000045" title="Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.">A000045</a>), and Fine (<a href="/A000957" title="Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with...">A000957</a>) numbers and polynomials (<a href="/A030528" title="Triangle read by rows: a(n,k) = binomial(k,n-k).">A030528</a>), and enumerating arrays for Motzkin, Dyck, and Łukasiewicz lattice paths and different types of trees and non-crossing partitions (<a href="/A091867" title="Triangle read by rows: T(n,k) = number of Dyck paths of semilength n having k peaks at odd height.">A091867</a>, connected to sums of the refined Narayana numbers <a href="/A134264" title="Coefficients T(j, k) of a partition transform for Lagrange compositional inversion of a function or generating series in ter...">A134264</a>). - <a href="/wiki/User:Tom_Copeland">Tom Copeland</a>, Nov 04 2014</div> <div class=sectline>Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - <a href="/wiki/User:Zhi-Wei_Sun">Zhi-Wei Sun</a>, Sep 24 2015</div> <div class=sectline>The Catalan number series <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>(n+3), offset n=0, gives Hankel transform revealing the square pyramidal numbers starting at 5, <a href="/A000330" title="Square pyramidal numbers: a(n) = 0^2 + 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2*n+1)/6.">A000330</a>(n+2), offset n=0 (empirical observation). - <a href="/wiki/User:Tony_Foster_III">Tony Foster III</a>, Sep 05 2016</div> <div class=sectline>Hankel transforms of the Catalan numbers with the first 2, 4, and 5 terms omitted give <a href="/A001477" title="The nonnegative integers.">A001477</a>, <a href="/A006858" title="Expansion of g.f. x*(1 + x)*(1 + 6*x + x^2)/(1 - x)^7.">A006858</a>, and <a href="/A091962" title="From enumerating paths in the plane.">A091962</a>, respectively, without the first 2 terms in all cases. More generally, the Hankel transform of the Catalan numbers with the first k terms omitted is H_k(n) = Product_{j=1..k-1} Product_{i=1..j} (2*n+j+i)/(j+i) [see Cigler (2011), Eq. (1.14) and references therein]; together they form the array <a href="/A078920" title="Upper triangle of Catalan Number Wall.">A078920</a>/<a href="/A123352" title="Triangle read by rows, giving Kekulé numbers for certain benzenoids (see the Cyvin-Gutman book for details).">A123352</a>/<a href="/A368025" title="Array read by ascending antidiagonals: A(n,k) is the determinant of the n-th order Hankel matrix of Catalan numbers M(n) who...">A368025</a>. - <a href="/wiki/User:Andrey_Zabolotskiy">Andrey Zabolotskiy</a>, Oct 13 2016</div> <div class=sectline>Presumably this satisfies Benford's law, although the results in Hürlimann (2009) do not make this clear. See S. J. Miller, ed., 2015, p. 5. - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Feb 09 2017</div> <div class=sectline>Coefficients of the generating series associated to the Magmatic and Dendriform operadic algebras. Cf. p. 422 and 435 of the Loday et al. paper. - <a href="/wiki/User:Tom_Copeland">Tom Copeland</a>, Jul 08 2018</div> <div class=sectline>Let M_n be the n X n matrix with M_n(i,j) = binomial(i+j-1,2j-2); then det(M_n) = a(n). - <a href="/wiki/User:Tony_Foster_III">Tony Foster III</a>, Aug 30 2018</div> <div class=sectline>Also the number of Catalan trees, or planted plane trees (Bona, 2015, p. 299, Theorem 4.6.3). - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Dec 25 2018</div> <div class=sectline>Number of coalescent histories for a caterpillar species tree and a matching caterpillar gene tree with n+1 leaves (Rosenberg 2007, Corollary 3.5). - <a href="/wiki/User:Noah_A_Rosenberg">Noah A Rosenberg</a>, Jan 28 2019</div> <div class=sectline>Finding solutions of eps*x^2+x-1 = 0 for eps small, that is, writing x = Sum_{n>=0} x_{n}*eps^n and expanding, one finds x = 1 - eps + 2*eps^2 - 5*eps^3 + 14*eps^3 - 42*eps^4 + ... with x_{n} = (-1)^n*C(n). Further, letting x = 1/y and expanding y about 0 to find large roots, that is, y = Sum_{n>=1} y_{n}*eps^n, one finds y = 0 - eps + eps^2 - 2*eps^3 + 5*eps^3 - ... with y_{n} = (-1)^n*C(n-1). - <a href="/wiki/User:Derek_Orr">Derek Orr</a>, Mar 15 2019</div> <div class=sectline>Permutations of length n that produce a bipartite permutation graph of order n [see Knuth (1973), Busch (2006), Golumbic and Trenk (2004)]. - <a href="/wiki/User:Elise_Anderson">Elise Anderson</a>, <a href="/wiki/User:R._M._Argus">R. M. Argus</a>, <a href="/wiki/User:Caitlin_Owens">Caitlin Owens</a>, <a href="/wiki/User:Tessa_Stevens">Tessa Stevens</a>, Jun 27 2019</div> <div class=sectline>For n > 0, a random selection of n + 1 objects (the minimum number ensuring one pair by the pigeonhole principle) from n distinct pairs of indistinguishable objects contains only one pair with probability 2^(n-1)/a(n) = b(n-1)/<a href="/A098597" title="Numerator of Catalan(n)/2^(2n+1). Also, numerators of (2n-1)!!/(n+1)!. Odd part of the n-th Catalan number.">A098597</a>(n), where b is the 0-offset sequence with the terms of <a href="/A120777" title="a(n) = 2^(2*n - valuation(CatalanNumber(n), 2)).">A120777</a> repeated (1,1,4,4,8,8,64,64,128,128,...). E.g., randomly selecting 6 socks from 5 pairs that are black, blue, brown, green, and white, results in only one pair of the same color with probability 2^(5-1)/a(5) = 16/42 = 8/21 = b(4)/<a href="/A098597" title="Numerator of Catalan(n)/2^(2n+1). Also, numerators of (2n-1)!!/(n+1)!. Odd part of the n-th Catalan number.">A098597</a>(5). - <a href="/wiki/User:Rick_L._Shepherd">Rick L. Shepherd</a>, Sep 02 2019</div> <div class=sectline>See Haran & Tabachnikov link for a video discussing Conway-Coxeter friezes. The Conway-Coxeter friezes with n nontrivial rows are generated by the counts of triangles at each vertex in the triangulations of regular n-gons, of which there are a(n). - <a href="/wiki/User:Charles_R_Greathouse_IV">Charles R Greathouse IV</a>, Sep 28 2019</div> <div class=sectline>For connections to knot theory and scattering amplitudes from Feynman diagrams, see Broadhurst and Kreimer, and Todorov. Eqn. 6.12 on p. 130 of Bessis et al. becomes, after scaling, -12g * r_0(-y/(12g)) = (1-sqrt(1-4y))/2, the o.g.f. (expressed as a Taylor series in Eqn. 7.22 in 12gx) given for the Catalan numbers in Copeland's (Sep 30 2011) formula below. (See also Mizera p. 34, Balduf pp. 79-80, Keitel and Bartosch.) - <a href="/wiki/User:Tom_Copeland">Tom Copeland</a>, Nov 17 2019</div> <div class=sectline>Number of permutations in S_n whose principal order ideals in the weak order are modular lattices. - <a href="/wiki/User:Bridget_Tenner">Bridget Tenner</a>, Jan 16 2020</div> <div class=sectline>Number of permutations in S_n whose principal order ideals in the weak order are distributive lattices. - <a href="/wiki/User:Bridget_Tenner">Bridget Tenner</a>, Jan 16 2020</div> <div class=sectline>Legendre gives the following formula for computing the square root modulo 2^m:</div> <div class=sectline> sqrt(1 + 8*a) mod 2^m = (1 + 4*a*Sum_{i=0..m-4} C(i)*(-2*a)^i) mod 2^m</div> <div class=sectline> as cited by L. D. Dickson, History of the Theory of Numbers, Vol. 1, 207-208. - <a href="/wiki/User:Peter_Schorn">Peter Schorn</a>, Feb 11 2020</div> <div class=sectline>a(n) is the number of length n permutations sorted to the identity by a consecutive-132-avoiding stack followed by a classical-21-avoiding stack. - <a href="/wiki/User:Kai_Zheng">Kai Zheng</a>, Aug 28 2020</div> <div class=sectline>Number of non-crossing partitions of a 2*n-set with n blocks of size 2. Also number of non-crossing partitions of a 2*n-set with n+1 blocks of size at most 3, and without cyclical adjacencies. The two partitions can be mapped by rotated Kreweras bijection. - <a href="/wiki/User:Yuchun_Ji">Yuchun Ji</a>, Jan 18 2021</div> <div class=sectline>Named by Riordan (1968, and earlier in Mathematical Reviews, 1948 and 1964) after the French and Belgian mathematician Eugène Charles Catalan (1814-1894) (see Pak, 2014). - <a href="/wiki/User:Amiram_Eldar">Amiram Eldar</a>, Apr 15 2021</div> <div class=sectline>For n >= 1, a(n-1) is the number of interpretations of x^n is an algebra where power-associativity is not assumed. For example, for n = 4 there are a(3) = 5 interpretations: x(x(xx)), x((xx)x), (xx)(xx), (x(xx))x, ((xx)x)x. See the link "Non-associate powers and a functional equation" from I. M. H. Etherington and the page "Nonassociative Product" from Eric Weisstein's World of Mathematics for detailed information. See also <a href="/A001190" title="Wedderburn-Etherington numbers: unlabeled binary rooted trees (every node has outdegree 0 or 2) with n endpoints (and 2n-1 n...">A001190</a> for the case where multiplication is commutative. - <a href="/wiki/User:Jianing_Song">Jianing Song</a>, Apr 29 2022</div> <div class=sectline>Number of states in the transition diagram associated with the Laplacian system over the complete graph K_N, corresponding to ordered initial conditions x_1 < x_2 < ... < x_N. - <a href="/wiki/User:Andrea_Arlette_España">Andrea Arlette España</a>, Nov 06 2022</div> <div class=sectline>a(n) is the number of 132-avoiding stabilized-interval-free permutations of size n+1. - <a href="/wiki/User:Juan_B._Gil">Juan B. Gil</a>, Jun 22 2023</div> <div class=sectline>Number of rooted polyominoes composed of n triangular cells of the hyperbolic regular tiling with Schläfli symbol {3,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. A stereographic projection of the {3,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - <a href="/wiki/User:Robert_A._Russell">Robert A. Russell</a>, Jan 27 2024</div> <div class=sectline>a(n) is the number of extremely lucky Stirling permutations of order n; i.e., the number of Stirling permutations of order n that have exactly n lucky cars. (see Colmenarejo et al. reference) - <a href="/wiki/User:Bridget_Tenner">Bridget Tenner</a>, Apr 16 2024</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>The large number of references and links demonstrates the ubiquity of the Catalan numbers.</div> <div class=sectline>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.</div> <div class=sectline>Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, many references.</div> <div class=sectline>L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 53.</div> <div class=sectline>J. H. Conway and R. K. Guy, The Book of Numbers, New York: Springer-Verlag, 1995, ch. 4, pp. 96-106.</div> <div class=sectline>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.).</div> <div class=sectline>Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.</div> <div class=sectline>E. Deutsch, Dyck path enumeration, Discrete Math., 204, 167-202, 1999.</div> <div class=sectline>E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001.</div> <div class=sectline>L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, 207-208.</div> <div class=sectline>Tomislav Doslic and Darko Veljan, Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182-2212. MR2404544 (2009j:05019)</div> <div class=sectline>S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105.</div> <div class=sectline>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.</div> <div class=sectline>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)</div> <div class=sectline>I. M. H. Etherington, Non-associate powers and a functional equation. The Mathematical Gazette, 21 (1937): 36-39; addendum 21 (1937), 153.</div> <div class=sectline>I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.</div> <div class=sectline>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.</div> <div class=sectline>K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167.</div> <div class=sectline>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.</div> <div class=sectline>D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.</div> <div class=sectline>H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.</div> <div class=sectline>Fürlinger, J.; Hofbauer, J., q-Catalan numbers. J. Combin. Theory Ser. A 40 (1985), no. 2, 248-264. MR0814413 (87e:05017)</div> <div class=sectline>M. Gardner, Time Travel and Other Mathematical Bewilderments, Chap. 20 pp. 253-266, W. H. Freeman NY 1988.</div> <div class=sectline>James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).</div> <div class=sectline>M. C. Golumbic and A. N. Trenk, Tolerance graphs, Vol. 89, Cambridge University Press, 2004, pp. 32.</div> <div class=sectline>S Goodenough, C Lavault, Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups, The Electronic Journal of Combinatorics, 22(4) (2015), #P4.16,</div> <div class=sectline>H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.</div> <div class=sectline>D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.</div> <div class=sectline>M. Griffiths, The Backbone of Pascal's Triangle, United Kingdom Mathematics Trust (2008), 53-63 and 85-93.</div> <div class=sectline>J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 530.</div> <div class=sectline>N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.</div> <div class=sectline>R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.</div> <div class=sectline>R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876.</div> <div class=sectline>Peter Hajnal and Gabor V. Nagy, A bijective proof of Shapiro's Catalan convolution, Elect. J. Combin., 21 (2014), #P2.42.</div> <div class=sectline>F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.23).</div> <div class=sectline>F. Harary, G. Prins, and W. T. Tutte, The number of plane trees. Indag. Math. 26, 319-327, 1964.</div> <div class=sectline>J. Harris, Algebraic Geometry: A First Course (GTM 133), Springer-Verlag, 1992, pages 245-247.</div> <div class=sectline>S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964.</div> <div class=sectline>Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.</div> <div class=sectline>Higgins, Peter M. Combinatorial results for semigroups of order-preserving mappings. Math. Proc. Camb. Phil. Soc. (1993), 113: 281-296.</div> <div class=sectline>B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 513, Eq. (7.282).</div> <div class=sectline>F. Hurtado, M. Noy, Ears of triangulations and Catalan numbers, Discrete Mathematics, Volume 149, Issues 1-3, Feb 22 1996, Pages 319-324.</div> <div class=sectline>M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.</div> <div class=sectline>R. H. Jeurissen, Raney and Catalan, Discrete Math., 308 (2008), 6298-6307.</div> <div class=sectline>M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 36.</div> <div class=sectline>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)</div> <div class=sectline>Klarner, D. A. A Correspondence Between Sets of Trees. Indag. Math. 31, 292-296, 1969.</div> <div class=sectline>M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.</div> <div class=sectline>D. E. Knuth, The Art of Computer Programming, 2nd Edition, Vol. 1, Addison-Wesley, 1973, pp. 238.</div> <div class=sectline>D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.6 (p. 450).</div> <div class=sectline>Thomas Koshy and Mohammad Salmassi, "Parity and Primality of Catalan Numbers", College Mathematics Journal, Vol. 37, No. 1 (Jan 2006), pp. 52-53.</div> <div class=sectline>M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.</div> <div class=sectline>E. Krasko, A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.</div> <div class=sectline>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.</div> <div class=sectline>P. Lafar and C. T. Long, A combinatorial problem, Amer. Math. Mnthly, 69 (1962), 876-883.</div> <div class=sectline>Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200.</div> <div class=sectline>P. J. Larcombe, On pre-Catalan Catalan numbers: Kotelnikow (1766), Mathematics Today, 35 (1999), p. 25.</div> <div class=sectline>P. J. Larcombe, On the history of the Catalan numbers: a first record in China, Mathematics Today, 35 (1999), p. 89.</div> <div class=sectline>P. J. Larcombe, The 18th century Chinese discovery of the Catalan numbers, Math. Spectrum, 32 (1999/2000), 5-7.</div> <div class=sectline>P. J. Larcombe and P. D. C. Wilson, On the trail of the Catalan sequence, Mathematics Today, 34 (1998), 114-117.</div> <div class=sectline>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.</div> <div class=sectline>G. S. Lueker, Some techniques for solving recurrences, Computing Surveys, 12 (1980), 419-436.</div> <div class=sectline>J. J. Luo, Antu Ming, the first inventor of Catalan numbers in the world [in Chinese], Neimenggu Daxue Xuebao, 19 (1998), 239-245.</div> <div class=sectline>C. L. Mallows, R. J. Vanderbei, Which Young Tableaux Can Represent an Outer Sum?, Journal of Integer Sequences, Vol. 18, 2015, #15.9.1.</div> <div class=sectline>Toufik Mansour, Matthias Schork, and Mark Shattuck, Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979-2991. MR2956089</div> <div class=sectline>Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.</div> <div class=sectline>M. E. Mays and Jerzy Wojciechowski, A determinant property of Catalan numbers. Discrete Math. 211, No. 1-3, 125-133 (2000). Zbl 0945.05037</div> <div class=sectline>D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344.</div> <div class=sectline>A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.</div> <div class=sectline>Miller, Steven J., ed. Benford's Law: Theory and Applications. Princeton University Press, 2015.</div> <div class=sectline>David Molnar, "Wiggly Games and Burnside's Lemma", Chapter 8, The Mathematics of Various Entertaining Subjects: Volume 3 (2019), Jennifer Beineke & Jason Rosenhouse, eds. Princeton University Press, Princeton and Oxford, p. 102.</div> <div class=sectline>C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly, 64 (1957), 143-154.</div> <div class=sectline>A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).</div> <div class=sectline>Papoulis, Athanasios. "A new method of inversion of the Laplace transform."Quart. Appl. Math 14.405-414 (1957): 124.</div> <div class=sectline>S. G. Penrice, Stacks, bracketings and CG-arrangements, Math. Mag., 72 (1999), 321-324.</div> <div class=sectline>C. A. Pickover, Wonders of Numbers, Chap. 71, Oxford Univ. Press NY 2000.</div> <div class=sectline>Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.</div> <div class=sectline>G. Pólya, On the number of certain lattice polygons. J. Combinatorial Theory 6 1969 102-105. MR0236031 (38 #4329)</div> <div class=sectline>C. Pomerance, Divisors of the middle binomial coefficient, Amer. Math. Monthly, 112 (2015), 636-644.</div> <div class=sectline>Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.</div> <div class=sectline>Ronald C. Read, "The Graph Theorists who Count -- and What They Count", in 'The Mathematical Gardner', in D. A. Klarner, Ed., pp. 331-334, Wadsworth CA 1989.</div> <div class=sectline>J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.</div> <div class=sectline>J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.</div> <div class=sectline>T. Santiago Costa Oliveira, "Catalan traffic" and integrals on the Grassmannian of lines, Discr. Math., 308 (2007), 148-152.</div> <div class=sectline>A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.</div> <div class=sectline>E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.</div> <div class=sectline>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).</div> <div class=sectline>L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory, A 20 (1976), 375-376.</div> <div class=sectline>L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.</div> <div class=sectline>L. W. Shapiro, W.-J. Woan and S. Getu, The Catalan numbers via the World Series, Math. Mag., 66 (1993), 20-22.</div> <div class=sectline>D. M. Silberger, Occurrences of the integer (2n-2)!/n!(n-1)!, Roczniki Polskiego Towarzystwa Math. 13 (1969): 91-96.</div> <div class=sectline>N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).</div> <div class=sectline>N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).</div> <div class=sectline>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.</div> <div class=sectline>Solomon, A. Catalan monoids, monoids of local endomorphisms and their presentations. Semigroup Forum 53 (1996), 351-368.</div> <div class=sectline>R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, Vol. 2, 1999; see especially Chapter 6.</div> <div class=sectline>R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.</div> <div class=sectline>Richard P. Stanley, "Catalan Numbers", Cambridge University Press, 2015.</div> <div class=sectline>J. J. Sylvester, On reducible cyclodes, Coll. Math. Papers, Vol. 2, see especially page 670, where Catalan numbers appear.</div> <div class=sectline>Thiel, Marko. "A new cyclic sieving phenomenon for Catalan objects." Discrete Mathematics 340.3 (2017): 426-429.</div> <div class=sectline>I. Vun and P. Belcher, Catalan numbers, Mathematical Spectrum, 30 (1997/1998), 3-5.</div> <div class=sectline>D. Wells, Penguin Dictionary of Curious and Interesting Numbers, Entry 42 p 121, Penguin Books, 1987.</div> <div class=sectline>D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 41.</div> <div class=sectline>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.</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>Robert G. Wilson v, <a href="/A000108/b000108.txt">Table of n, a(n) for n = 0..1000</a> (first 200 terms from N. J. A. Sloane, first 351 from K. D. Bajpai)</div> <div class=sectline>James Abello, <a href="http://dx.doi.org/10.1137/0404001">The weak Bruhat order of S_Sigma, consistent sets, and Catalan numbers</a>, SIAM J. Discrete Math. 4 (1991), 1-16.</div> <div class=sectline>Marco Abrate, Stefano Barbero, Umberto Cerruti and Nadir Murru, <a href="https://doi.org/10.1016/j.disc.2014.06.026">Colored compositions, Invert operator and elegant compositions with the "black tie"</a>, Discrete Mathematics, 335 (2014), 1-7.</div> <div class=sectline>M. Aigner, <a href="https://doi.org/10.1016/j.disc.2007.06.012">Enumeration via ballot numbers</a>, Discrete Mathematics, Vol. 308, No. 12 (2008), 2544-2563.</div> <div class=sectline>R. Alter and K. K. Kubota, <a href="https://doi.org/10.1016/0097-3165(73)90072-1">Prime and prime power divisibility of Catalan numbers</a>, Journal of Combinatorial Theory, Series A, Vol. 15, No. 3 (1973), 243-256.</div> <div class=sectline>M. J. H. Al-Kaabi, D. Manchon and F. Patras, Chapter 2 of <a href="https://arxiv.org/abs/1708.08312">Monomial bases and pre-Lie structure for free Lie algebras</a>, arXiv:1708.08312 [math.RA], 2017, See p. 3.</div> <div class=sectline>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 [math.CA]. See Section 3.2.</div> <div class=sectline>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.)</div> <div class=sectline>G. Alvarez, J. E. Bergner and R. Lopez, <a href="http://arxiv.org/abs/1503.00044">Action graphs and Catalan numbers</a>, arXiv preprint arXiv:1503.00044 [math.CO], 2015.</div> <div class=sectline>George E. Andrews, <a href="https://doi.org/10.1016/0097-3165(87)90033-1">Catalan numbers, q-Catalan numbers and hypergeometric series</a>, Journal of Combinatorial Theory, Series A, Vol. 44, No. 2 (1987), 267-273.</div> <div class=sectline>Federico Ardila, <a href="https://fardila.com/Articles/catalanENG.pdf">Catalan Numbers</a>, 2016.</div> <div class=sectline>Drew Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, Mem. Amer. Math. Soc. 202 (2009), no. 949, x+159. MR 2561274 16; See Table 2.8. Also arXiv:<a href="https://arxiv.org/abs/math/0611106">math/0611106</a>, 2006-2007.</div> <div class=sectline>Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 333 and p. 337.</div> <div class=sectline>Joerg Arndt, <a href="/A000108/a000108.txt">The a(5)=42 Young tableaux of shape [5,5]</a>.</div> <div class=sectline>Yu Hin (Gary) Au, Fatemeh Bagherzadeh, Murray R. Bremner, <a href="https://arxiv.org/abs/1903.00813">Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube</a>, arXiv:1903.00813 [math.CO], 2019.</div> <div class=sectline>Yu Hin Au, <a href="https://arxiv.org/abs/1912.00555">Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers</a>, arXiv:1912.00555 [math.CO], 2019.</div> <div class=sectline>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.</div> <div class=sectline>M. Azaola and F. Santos, <a href="http://personales.unican.es/santosf/Articulos/#2002">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).)</div> <div class=sectline>R. Bacher and C. Krattenthaler, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p152">Chromatic statistics for triangulations and Fuss-Catalan complexes</a>, Electronic Journal of Combinatorics, Vol. 18, No. 1 (2011), #P152.</div> <div class=sectline>John Baez, <a href="http://math.ucr.edu/home/baez/week202.html">This week's finds in mathematical physics, Week 202</a></div> <div class=sectline>D. F. Bailey, <a href="http://www.jstor.org/stable/2690671">Counting Arrangements of 1's and -1's</a>, Mathematics Magazine 69(2) 128-131 1996.</div> <div class=sectline>I. Bajunaid et al., <a href="https://doi.org/10.1080/00029890.2005.11920251">Function Series, Catalan Numbers, and Random Walks on Trees</a>, The American Mathematical Monthly, Vol. 112, No. 9 (2005), 765-785.</div> <div class=sectline>P. Balduf, <a href="http://www2.mathematik.hu-berlin.de/~kreimer/wp-content/uploads/PaulMaster">The propagator and diffeomorphisms of an interacting field theory</a>, Master's thesis, submitted to the Institut für Physik, Mathematisch-Naturwissenschaftliche Fakultät, Humboldt-Universität, Berlin, 2018.</div> <div class=sectline>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.</div> <div class=sectline>C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://algo.inria.fr/flajolet/Publications/RR-3661.pdf">INRIA report 3661</a>, <a href="http://algo.inria.fr/banderier/Papers/DiscMath99.ps">preprint for FPSAC 99</a>, <a href="https://doi.org/10.1016/S0012-365X(01)00250-3">Generating Functions for Generating Trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.</div> <div class=sectline>C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, <a href="https://arxiv.org/abs/1609.06473">Explicit formulas for enumeration of lattice paths: basketball and the kernel method</a>, arXiv preprint arXiv:1609.06473 [math.CO], 2016.</div> <div class=sectline>Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne and Martin Leuner, <a href="https://arxiv.org/abs/1907.01073">On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture</a>, arXiv:1907.01073 [math.CO], 2019.</div> <div class=sectline>S. Barbero, U. Cerruti and N. Murru, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barbero2/barbero7.html">A Generalization of the Binomial Interpolated Operator and its Action on Linear Recurrent Sequences</a>, J. Int. Seq. 13 (2010) # 10.9.7, theorem 17.</div> <div class=sectline>E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, <a href="https://hal.inria.fr/hal-00958943">Permutations avoiding an increasing number of length-increasing forbidden subsequences</a>, Discrete Mathematics and Theoretical Computer Science 4, 2000, 31-44.</div> <div class=sectline>E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, <a href="https://doi.org/10.1016/S0012-365X(00)00359-9">Some permutations with forbidden subsequences and their inversion number</a>, Discrete Mathematics, Vol. 234, No. 1-3 (2001), 1-15.</div> <div class=sectline>E. Barcucci, A. Frosini and S. Rinaldi, <a href="https://doi.org/10.1016/j.disc.2005.01.006">On directed-convex polyominoes in a rectangle</a>, Discrete Mathematics, Vol. 298, No. 1-3 (2005), 62-78.</div> <div class=sectline>Jean-Luc Baril, <a href="https://doi.org/10.37236/665">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.</div> <div class=sectline>Jean-Luc Baril, <a href="https://doi.org/10.46298/dmtcs.2158">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016).</div> <div class=sectline>Jean-Luc Baril, David Bevan and Sergey Kirgizov, <a href="https://arxiv.org/abs/1906.11870">Bijections between directed animals, multisets and Grand-Dyck paths</a>, arXiv:1906.11870 [math.CO], 2019.</div> <div class=sectline>Jean-Luc Baril, C. Khalil and V. Vajnovszki, <a href="https://arxiv.org/abs/2004.01812">Catalan and Schröder permutations sortable by two restricted stacks</a>, arXiv:2004.01812 [cs.DM], 2020.</div> <div class=sectline>Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, <a href="http://math.colgate.edu/~integers/t46/t46.Abstract.html">Motzkin paths with a restricted first return decomposition</a>, Integers (2019) Vol. 19, A46.</div> <div class=sectline>Jean-Luc Baril, Sergey Kirgizov, José L. Ramírez, and Diego Villamizar, <a href="https://arxiv.org/abs/2401.06228">The Combinatorics of Motzkin Polyominoes</a>, arXiv:2401.06228 [math.CO], 2024. See page 1.</div> <div class=sectline>Jean-Luc Baril, Sergey Kirgizov and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1803.06706">Descent distribution on Catalan words avoiding a pattern of length at most three</a>, arXiv:1803.06706 [math.CO], 2018.</div> <div class=sectline>Jean-Luc Baril, T. Mansour and A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/equival.pdf">Equivalence classes of permutations modulo excedances</a>, 2014.</div> <div class=sectline>Jean-Luc Baril and J.-M. Pallo, <a href="http://jl.baril.u-bourgogne.fr/Motzkin.pdf">Motzkin subposet and Motzkin geodesics in Tamari lattices</a>, 2013.</div> <div class=sectline>Jean-Luc Baril and Armen Petrossian, <a href="https://doi.org/10.1016/j.disc.2014.12.003">Equivalence classes of Dyck paths modulo some statistics</a>, Discrete Mathematics, Vol. 338, No. 4 (2015), 655-660.</div> <div class=sectline>Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html">Motzkin and Catalan Tunnel Polynomials</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry1/barry95r.html">Generalized Catalan Numbers, Hankel Transforms and Somos-4 Sequences </a>, J. Int. Seq. 13 (2010) #10.7.2.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1803.10297">Generalized Eulerian Triangles and Some Special Production Matrices</a>, arXiv:1803.10297 [math.CO], 2018.</div> <div class=sectline>Paul Barry, <a href="https://doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016), 343-385.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1804.05027">The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays</a>, arXiv:1804.05027 [math.CO], 2018.</div> <div class=sectline>Paul Barry and A. Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry2/barry94r.html">The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences</a>, J. Int. Seq. 13 (2010) # 10.8.2</div> <div class=sectline>Paul Barry, <a href="http://arxiv.org/abs/1107.5490">Invariant number triangles, eigentriangles and Somos-4 sequences</a>, arXiv:1107.5490 [math.CO], 2011.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.</div> <div class=sectline>Paul Barry, <a href="https://www.emis.de/journals/JIS/VOL22/Barry1/barry411.html">The Central Coefficients of a Family of Pascal-like Triangles and Colored Lattice Paths</a>, J. Int. Seq., Vol. 22 (2019), Article 19.1.3.</div> <div class=sectline>Paul Barry, <a href="https://www.emis.de/journals/JIS/VOL22/Barry3/barry422.html">Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles</a>, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1910.00875">Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials</a>, arXiv:1910.00875 [math.CO], 2019.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1912.01124">A Note on Riordan Arrays with Catalan Halves</a>, arXiv:1912.01124 [math.CO], 2019.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1912.01126">Riordan arrays, the A-matrix, and Somos 4 sequences</a>, arXiv:1912.01126 [math.CO], 2019.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1912.11845">Chebyshev moments and Riordan involutions</a>, arXiv:1912.11845 [math.CO], 2019.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/2001.08799">Characterizations of the Borel triangle and Borel polynomials</a>, arXiv:2001.08799 [math.CO], 2020.</div> <div class=sectline>A. M. Baxter and L. K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014.</div> <div class=sectline>Margaret Bayer and Keith Brandt, <a href="https://bayer.ku.edu/pub/preprints/pill.pdf">The Pill Problem, Lattice Paths and Catalan Numbers</a>, preprint, Mathematics Magazine, Vol. 87, No. 5 (December 2014), pp. 388-394.</div> <div class=sectline>Christian Bean, A. Claesson and H. Ulfarsson, <a href="http://arxiv.org/abs/1512.03226">Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3</a>, arXiv preprint arXiv:1512.03226 [math.CO], 2015.</div> <div class=sectline>Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi, <a href="https://arxiv.org/abs/1808.04114">Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers</a>, arXiv:1808.04114 [math.CO], 2018.</div> <div class=sectline>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>.</div> <div class=sectline>E. T. Bell, <a href="https://doi.org/10.2307/1968633">The Iterated Exponential Integers</a>, Annals of Mathematics, Vol. 39, No. 3 (1938), 539-557.</div> <div class=sectline>Maciej Bendkowski and Pierre Lescanne, <a href="https://arxiv.org/abs/1804.03862">Combinatorics of explicit substitutions</a>, arXiv:1804.03862 [cs.LO], 2018.</div> <div class=sectline>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 [math.RT], 2009.</div> <div class=sectline>F. Bergeron, G. Labelle and P. Leroux, <a href="https://doi.org/10.1017/CBO9781107325913">Combinatorial Species and Tree-like Structures</a>, Encyclopedia of Mathematics and its Applications 67 (1997), see pp. 163, 167, 168, 252, 256, 291.</div> <div class=sectline>Julia E. Bergner, Cedric Harper, Ryan Keller and Mathilde Rosi-Marshall, <a href="https://arxiv.org/abs/1807.03005">Action graphs, planar rooted forests, and self-convolutions of the Catalan numbers</a>, arXiv:1807.03005 [math.CO], 2018.</div> <div class=sectline>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]</div> <div class=sectline>E. E. Bernard and P. D. A. Mole, <a href="https://doi.org/10.1093/comjnl/2.2.87">Generating Strategies for Continuous Separation Processes</a>, The Computer Journal, Vol. 2, No. 2 (1959), 87-89.</div> <div class=sectline>F. R. Bernhart, <a href="https://doi.org/10.1016/S0012-365X(99)00054-0">Catalan, Motzkin and Riordan numbers</a>, Discrete Mathematics, Vol. 204, No. 1-3 (1999), 73-112.</div> <div class=sectline>A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Rinaldi/rinaldi5.html">Permutations Defining Convex Permutominoes</a>, Journal of Integer Sequences 10 (2007), Article 07.9.7.</div> <div class=sectline>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. [Link to arXiv version]</div> <div class=sectline>M. Bernstein and N. J. A. Sloane, <a href="/A003633/a003633_1.pdf">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures].</div> <div class=sectline>D. Bessis, C. Itzykson, and J. B. Zuber, <a href="https://www.sciencedirect.com/science/article/pii/0196885880900081">Quantum Field Theory Techniques in Graphical Enumeration</a>, Adv. in Applied Math., Vol. I, Issue 3, Jun 1980, p. 109-157.</div> <div class=sectline>D. Bill, <a href="http://www.durangobill.com/BinTrees.html">Durango Bill's Enumeration of Binary Trees</a></div> <div class=sectline>D. Birmajer, J. B. Gil, J. O. Tirrell, and M. D. Weiner, <a href="https://arxiv.org/abs/2306.03155">Pattern-avoiding stabilized-interval-free permutations</a>, arXiv:2306.03155 [math.CO], 2023.</div> <div class=sectline>Aubrey Blecher, Charlotte Brennan and Arnold Knopfmacher, <a href="https://doi.org/10.1016/j.aam.2019.101945">Water capacity of Dyck paths</a>, Advances in Applied Mathematics (2019) Vol. 112, 101945.</div> <div class=sectline>Natasha Blitvić and Einar Steingrímsson, <a href="https://arxiv.org/abs/2001.00280">Permutations, moments, measures</a>, arXiv:2001.00280 [math.CO], 2020.</div> <div class=sectline>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.</div> <div class=sectline>M. Bona and B. E. Sagan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Sagan/sagan101.html">On Divisibility of Narayana Numbers by Primes</a>, Journal of Integer Sequences 8 (2005), Article 05.2.4.</div> <div class=sectline>H. Bottomley, <a href="/A000108/a000108b.gif">Catalan Space Invaders</a></div> <div class=sectline>H. Bottomley, <a href="/A002694/a002694.gif">Illustration for A000108, A001147, A002694, A067310 and A067311</a></div> <div class=sectline>T. Bourgeron, <a href="http://www.dma.ens.fr/culturemath/maths/pdf/combi/montagnards.pdf">Montagnards et polygones</a> [dead link]</div> <div class=sectline>Michel Bousquet and Cedric Lamathe, <a href="https://hal.inria.fr/hal-00972316">On symmetric structures of order two</a>, Discrete Mathematics and Theoretical Computer Science, Vol. 10, No. 2 (2008), 153-176.</div> <div class=sectline>Mireille Bousquet-Mélou, <a href="https://doi.org/10.1016/0001-8708(91)90052-9">Sorted and/or sortable permutations</a>, Discrete Mathematics, vol.225, no.1-3, pp.25-50, (2000).</div> <div class=sectline>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.</div> <div class=sectline>M. Bouvel, V. Guerrini and S. Rinaldi, <a href="http://arxiv.org/abs/1511.04864">Slicings of parallelogram polyominoes, or how Baxter and Schroeder can be reconciled</a>, arXiv preprint arXiv:1511.04864 [math.CO], 2015.</div> <div class=sectline>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 [math.CO], 2013.</div> <div class=sectline>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 [math.CO], 2012.</div> <div class=sectline>Richard Brak, <a href="https://arxiv.org/abs/1808.09078">A Universal Bijection for Catalan Structures</a>, arXiv:1808.09078 [math.CO], 2018.</div> <div class=sectline>D. Broadhurst and D. Kreimer, <a href="https://arxiv.org/abs/hep-ph/9504352">Knots and Numbers in phi^4 Theory to 7 Loops and Beyond</a>, arXiv:9504352 [hep-ph], 1995.</div> <div class=sectline>K. S. Brown's Mathpages at Math Forum, <a href="https://web.archive.org/web/20171109040813/http://mathforum.org/kb/message.jspa?messageID=22219">The Meanings of Catalan Numbers</a></div> <div class=sectline>W. G. Brown, <a href="https://doi.org/10.1080/00029890.1965.11970654">Historical Note on a Recurrent Combinatorial Problem</a>, The American Mathematical Monthly, Vol. 72, No. 9 (1965), 973-977.</div> <div class=sectline>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]</div> <div class=sectline>Kevin Buchin, Man-Kwun Chiu, Stefan Felsner, Günter Rote and André Schulz, <a href="https://arxiv.org/abs/1903.01095">The Number of Convex Polyominoes with Given Height and Width</a>, arXiv:1903.01095 [math.CO], 2019.</div> <div class=sectline>B. Bukh, PlanetMath.org, <a href="http://planetmath.org/catalannumbers">Catalan numbers</a></div> <div class=sectline>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/0610234 [math.CO], 2006.</div> <div class=sectline>A. H. Busch, <a href="https://doi.org/10.1016/j.dam.2005.06.010">A characterization of triangle-free tolerance graphs</a>, Discrete Applied Mathematics 154, no. 3, 2006 pp. 471.</div> <div class=sectline>W. Butler, A. Kalotay and N. J. A. Sloane, <a href="/A000108/a000108_3.pdf">Correspondence, 1974</a></div> <div class=sectline>W. Butler and N. J. A. Sloane, <a href="/A000108/a000108_2.pdf">Correspondence, 1974</a></div> <div class=sectline>Libor Caha and Daniel Nagaj, <a href="https://arxiv.org/abs/1805.07168">The pair-flip model: a very entangled translationally invariant spin chain</a>, arXiv:1805.07168 [quant-ph], 2018.</div> <div class=sectline>Fangfang Cai, Qing-Hu Hou, Yidong Sun and Arthur L.B. Yang, <a href="https://arxiv.org/abs/1808.05736">Combinatorial identities related to 2X2 submatrices of recursive matrices</a>, arXiv:1808.05736 [math.CO], 2018.</div> <div class=sectline>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.</div> <div class=sectline>D. Callan, <a href="https://doi.org/10.1080/0025570X.1999.11996750">A Combinatorial Interpretation of a Catalan Numbers Identity</a>, Mathematics Magazine, Vol. 72, No. 4 (1999), 295-298.</div> <div class=sectline>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.</div> <div class=sectline>D. Callan, <a href="http://arxiv.org/abs/1204.5704">A variant of Touchard's Catalan number identity</a>, arXiv preprint arXiv:1204.5704 [math.CO], 2012.</div> <div class=sectline>D. Callan, <a href="https://doi.org/10.1016/j.disc.2008.11.019">Pattern avoidance in "flattened" partitions</a>, Discrete Mathematics, Vol. 309, No. 12 (2009), 4187-4191.</div> <div class=sectline>D. Callan, <a href="https://www.jstor.org/stable/27641963">The Maximum Associativeness of Division: 11091</a>, The American Mathematical Monthly, Vol. 113, No. 5 (2006), 462-463.</div> <div class=sectline>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 [math.CO], 2011.</div> <div class=sectline>H. Cambazard and N. Catusse, <a href="http://arxiv.org/abs/1512.06649">Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the Plane</a>, arXiv preprint arXiv:1512.06649, 2015</div> <div class=sectline>N. T. Cameron, <a href="https://web.archive.org/web/20190331234929 /https://math.hmc.edu/~cameron/dissertation.pdf">Random walks, trees and extensions of Riordan group techniques</a></div> <div class=sectline>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.</div> <div class=sectline>Peter J. Cameron, <a href="https://doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, The Quarterly Journal of Mathematics, Vol. 38, No. 2 (1987), 155-183. See pp. 155, 162.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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).</div> <div class=sectline>Giulio Cerbai, Anders Claesson, Luca Ferrari and Einar Steingrímsson, <a href="https://arxiv.org/abs/2006.05692">Sorting with pattern-avoiding stacks: the 132-machine</a>, arXiv:2006.05692 [math.CO], 2020.</div> <div class=sectline>José Luis Cereceda, <a href="http://arxiv.org/abs/1510.00731">An alternative recursive formula for the sums of powers of integers</a>, arXiv:1510.00731 [math.CO], 2015.</div> <div class=sectline>G. Chatel and V. Pilaud, <a href="http://arxiv.org/abs/1411.3704">The Cambrian and Baxter-Cambrian Hopf Algebras</a>, arXiv preprint arXiv:1411.3704 [math.CO], 2014.</div> <div class=sectline>Cedric Chauve, Yann Ponty and Michael Wallner, <a href="https://arxiv.org/abs/1905.04971">Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models</a>, arXiv:1905.04971 [math.CO], 2019.</div> <div class=sectline>Young-Ming Chen, <a href="https://doi.org/10.1016/j.disc.2007.03.068">The Chung-Feller theorem revisited</a>, Discrete Mathematics, Vol. 308, No. 7 (2008), 1328-1329.</div> <div class=sectline>Peter Cholak and Ludovic Patey, <a href="https://arxiv.org/abs/1812.00188">Thin set theorems and cone avoidance</a>, arXiv:1812.00188 [math.LO], 2018.</div> <div class=sectline>Wun-Seng Chou, Tian-Xiao He and Peter J.-S. Shiue, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/He/he61.html">On the Primality of the Generalized Fuss-Catalan Numbers</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.2.1.</div> <div class=sectline>Malin Christensson, <a href="http://malinc.se/m/ImageTiling.php">Make hyperbolic tilings of images</a>, web page, 2019.</div> <div class=sectline>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.</div> <div class=sectline>Kai Lai Chung and W. Feller, <a href="https://www.jstor.org/stable/88260">On Fluctuations in Coin-Tossing</a>, Proceedings of the National Academy of Sciences of the United States of America, Vol. 35, No. 10 (1949), 605-608.</div> <div class=sectline>J. Cigler, <a href="http://arxiv.org/abs/1109.1449">Some nice Hankel determinants</a>, arXiv:1109.1449 [math.CO], 2011.</div> <div class=sectline>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.</div> <div class=sectline>Johann Cigler and Christian Krattenthaler, <a href="https://arxiv.org/abs/2003.01676">Hankel determinants of linear combinations of moments of orthogonal polynomials</a>, arXiv:2003.01676 [math.CO], 2020.</div> <div class=sectline>Laura Colmenarejo, Aleyah Dawkins, Jennifer Elder, Pamela E. Harris, Kimberly J. Harry, Selvi Kara, Dorian Smith, and Bridget Eileen Tenner, <a href="https://arxiv.org/abs/2403.03280">On the lucky and displacement statistics of Stirling permutations</a>, arXiv:2403.03280 [math.CO], 2024.</div> <div class=sectline>CombOS - Combinatorial Object Server, <a href="http://combos.org/dyck.html">Generate Dyck paths</a></div> <div class=sectline>Aldo Conca, Hans-Christian Herbig and Srikanth B. Iyengar, <a href="https://arxiv.org/abs/1705.02688">Koszul properties of the moment map of some classical representations</a>, arXiv:1705.02688 [math.AC], 2017, also <a href="https://doi.org/10.1007/s13348-018-0226-x">Collectanea Mathematica</a> (2018) 69.3, 337-357.</div> <div class=sectline>Harry Crane, <a href="https://ajc.maths.uq.edu.au/pdf/61/ajc_v61_p057.pdf">Left-right arrangements, set partitions, and pattern avoidance</a>, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.</div> <div class=sectline>Alissa S. Crans, <a href="https://www.youtube.com/watch?v=eoofvKI_Okg">A surreptitious sequence: the Catalan numbers</a> video (2014).</div> <div class=sectline>Danielle Cressman, Jonathan Lin, An Nguyen and Luke Wiljanen, <a href="http://www.terpconnect.umd.edu/~jlin1000/JMM_2020_Poster.pdf">Generalized Action Graphs</a>, poster, (2020).</div> <div class=sectline>S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, <a href="/A002057/a002057.pdf">Enumeration of polyene hydrocarbons: a complete mathematical solution</a>, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]</div> <div class=sectline>Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro and 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.</div> <div class=sectline>Dennis E. Davenport, Louis W. Shapiro and Leon C. Woodson, <a href="http://math.colgate.edu/~integers/u8/u8.pdf">A bijection between the triangulations of convex polygons and ordered trees</a>, Integers (2020) Vol. 20, Article #A8.</div> <div class=sectline>T. Davis, <a href="http://www.geometer.org/mathcircles/catalan.pdf">Catalan Numbers</a></div> <div class=sectline>Colin Defant, <a href="https://arxiv.org/abs/1904.02627">Catalan Intervals and Uniquely Sorted Permutations</a>, arXiv:1904.02627 [math.CO], 2019.</div> <div class=sectline>C. Defant and K. Zheng, <a href="https://arxiv.org/abs/2008.12297">Stack-Sorting with Consecutive-Pattern-Avoiding Stacks</a>, arXiv:2008.12297 [math.CO], 2020.</div> <div class=sectline>Italo J. Dejter, <a href="https://www.researchgate.net/publication/245576352">The role of restricted growth strings in the two middle levels of the Boolean lattice B_(2k+1)</a>, University of Puerto Rico, 2018.</div> <div class=sectline>Italo J. Dejter, <a href="https://arxiv.org/abs/1911.02100">Reinterpreting Mütze's Theorem via Natural Enumeration of Ordered Rooted Trees</a>, arXiv:1911.02100 [math.CO], 2019.</div> <div class=sectline>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.</div> <div class=sectline>E. Deutsch and L. Shapiro, <a href="https://doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., 241 (2001), 241-265.</div> <div class=sectline>Jimmy Devillet and Bruno Teheux, <a href="https://arxiv.org/abs/1805.11936">Associative, idempotent, symmetric, and order-preserving operations on chains</a>, arXiv:1805.11936 [math.RA], 2018.</div> <div class=sectline>R. M. Dickau, <a href="https://mathshistory.st-andrews.ac.uk/Extras/Catalan/">Catalan numbers</a></div> <div class=sectline>T. Dokos and I. Pak, <a href="http://arxiv.org/abs/1401.0770">The expected shape of random doubly alternating Baxter permutations</a>, arXiv:1401.0770 [math.CO], 2014.</div> <div class=sectline>C. Domb & A. J. Barrett, <a href="/A003408/a003408.pdf">Enumeration of ladder graphs</a>, Discrete Math. 9 (1974), 341-358. (Annotated scanned copy)</div> <div class=sectline>C. Domb & A. J. Barrett, <a href="/A001764/a001764.pdf">Notes on Table 2 in "Enumeration of ladder graphs"</a>, Discrete Math. 9 (1974), 55. (Annotated scanned copy)</div> <div class=sectline>T. Doslic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Doslic/doslic6.html">Handshakes across a (round) table</a>, JIS 13 (2010) #10.2.7.</div> <div class=sectline>Eric S. Egge, Kailee Rubin, <a href="http://arxiv.org/abs/1508.05310">Snow Leopard Permutations and Their Even and Odd Threads</a>, arXiv:1508.05310 [math.CO], 2015.</div> <div class=sectline>Roger B. Eggleton and Richard K. Guy, <a href="http://www.jstor.org/stable/2689355">Catalan strikes again! How likely is a function to be convex?</a>, Mathematics Magazine, 61 (1988): 211-219.</div> <div class=sectline>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 [math.CO], 2015.</div> <div class=sectline>Gennady Eremin, <a href="https://arxiv.org/abs/1908.03752">Factoring Catalan numbers</a>, arXiv:1908.03752 [math.NT], 2019.</div> <div class=sectline>A. España, X. Leoncini, and E. Ugalde, <a href="https://arxiv.org/abs/2205.05948">Combinatorics of the paths towards synchronization</a>, arXiv:2205.05948 [math.DS], 2022.</div> <div class=sectline>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]</div> <div class=sectline>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]</div> <div class=sectline>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.</div> <div class=sectline>Jackson Evoniuk, Steven Klee and Van Magnan, <a href="https://www.emis.de/journals/JIS/VOL21/Klee/klee2.html">Enumerating Minimal Length Lattice Paths</a>, J. Int. Seq., Vol. 21 (2018), Article 18.3.6.</div> <div class=sectline>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 [math.CO], 2012.</div> <div class=sectline>FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000028/">The number of stack-sorts needed to sort a permutation</a></div> <div class=sectline>D. C. Fielder & C. O. Alford, <a href="/A000108/a000108_19.pdf">An investigation of sequences derived from Hoggatt Sums and Hoggatt Triangles</a>, Application of Fibonacci Numbers, 3 (1990) 77-88. Proceedings of 'The Third Annual Conference on Fibonacci Numbers and Their Applications,' Pisa, Italy, July 25-29, 1988. (Annotated scanned copy)</div> <div class=sectline>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/0606370 [math.CO], 2006.</div> <div class=sectline>Philippe Flajolet, Xavier Gourdon, and Philippe Dumas, <a href="https://doi.org/10.1016/0304-3975(95)00002-E">Mellin transforms and asymptotics: harmonic sums</a>, Special volume on mathematical analysis of algorithms. Theoret. Comput. Sci. 144 (1995), no. 1-2, 3-58.</div> <div class=sectline>P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 18, 35</div> <div class=sectline>D. Foata and 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</div> <div class=sectline>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</div> <div class=sectline>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></div> <div class=sectline>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 [math.CO], 2012 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Forcey/forcey2.html">J. Int. Seq. 16 (2013) #13.5.3</a>.</div> <div class=sectline>H. G. Forder, <a href="/A000108/a000108_4.pdf">Some problems in combinatorics</a>, Math. Gazette, vol. 45, 1961, 199-201. [Annotated scanned copy]</div> <div class=sectline>Shishuo Fu and Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.</div> <div class=sectline>J. R. Gaggins, <a href="https://www.jstor.org/stable/3618254">Constructing the Centroid of a Polygon</a>, Math. Gaz., 61 (1988), 211-212.</div> <div class=sectline>I. Galkin, <a href="http://ulcar.uml.edu/~iag/CS/Catalan.html">Enumeration of the Binary Trees (Catalan Numbers)</a></div> <div class=sectline>Mohammad Ganjtabesh, Armin Morabbi and Jean-Marc Steyaert, <a href="https://web.archive.org/web/20210415051137 /http://www.lifl.fr/SEQUOIA/Arena/Presentations/Ganjtabesh.pdf">Enumerating the number of RNA structures</a></div> <div class=sectline>Joël Gay and Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.</div> <div class=sectline>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 [math.CO], 2013.</div> <div class=sectline>A. Ghasemi, K. Sreenivas and L. K. Taylor, <a href="http://arxiv.org/abs/1309.4820">Numerical Stability and Catalan Numbers</a>, arXiv preprint arXiv:1309.4820 [math.NA], 2013.</div> <div class=sectline>Étienne Ghys, <a href="http://arxiv.org/abs/1612.06373">A Singular Mathematical Promenade</a>, arXiv:1612.06373, 2016.</div> <div class=sectline>Juan B. Gil and Michael D. Weiner, <a href="https://arxiv.org/abs/1812.01682">On pattern-avoiding Fishburn permutations</a>, arXiv:1812.01682 [math.CO], 2018.</div> <div class=sectline>S. Gilliand, C. Johnson, S. Rush, D. Wood, <a href="https://doi.org/10.2140/involve.2014.7.691">The sock matching problem</a>, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 691-697.</div> <div class=sectline>Samuele Giraudo, <a href="http://arxiv.org/abs/1603.01394">Pluriassociative algebras II: The polydendriform operad and related operads</a>, arXiv:1603.01394 [math.CO], 2016.</div> <div class=sectline>Samuele Giraudo, <a href="https://arxiv.org/abs/1903.00677">Tree series and pattern avoidance in syntax trees</a>, arXiv:1903.00677 [math.CO], 2019.</div> <div class=sectline>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.</div> <div class=sectline>S. Goldstein, J. L. Lebowitz and E. R. Speer, <a href="https://arxiv.org/abs/2003.04995">The Discrete-Time Facilitated Totally Asymmetric Simple Exclusion Process</a>, arXiv:2003.04995 [math-ph], 2020.</div> <div class=sectline>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 [math.CO], 2013.</div> <div class=sectline>H. W. Gould, <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2049119">Proof and generalization of a Catalan number formula of Larcombe</a>, Congr. Numer. 165 (2003) p 33-38.</div> <div class=sectline>Alain Goupil and Gilles Schaeffer, <a href="https://doi.org/10.1006/eujc.1998.0215">Factoring N-Cycles and Counting Maps of Given Genus</a>, Europ. J. Combinatorics (1998) 19 819-834.</div> <div class=sectline>B. Gourevitch, <a href="http://www.pi314.net/">L'univers de Pi</a> (click Mathematiciens, Gosper)</div> <div class=sectline>D. Gouyou-Beauchamps, <a href="/A005700/a005700.pdf">Chemins sous-diagonaux et tableau de Young</a>, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, Springer, 1986. (Annotated scanned copy)</div> <div class=sectline>Taras Goy and Mark Shattuck, <a href="https://doi.org/10.1007/s12044-019-0513-9">Determinant formulas of some Toeplitz-Hessenberg matrices with Catalan entries</a>, Proceedings of the Indian Academy of Science - Mathematical Sciences, Vol. 129 (2019), Article 46.</div> <div class=sectline>Mats Granvik, <a href="http://pastebin.com/fsCtBUe1">Catalan numbers as convergents of power series</a></div> <div class=sectline>Curtis Greene and Brady Haran, <a href="https://www.youtube.com/watch?v=JiwM5g_RC3c">Shapes and Hook Numbers (extra footage)</a>, Numberphile video (2016)</div> <div class=sectline>Catherine Greenhill, Bernard Mans, and Ali Pourmiri, <a href="https://arxiv.org/abs/2006.07588">Balanced Allocation on Dynamic Hypergraphs</a>, arXiv:2006.07588 [cs.DS], 2020.</div> <div class=sectline>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.</div> <div class=sectline>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]</div> <div class=sectline>R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, Sandsteps and Pascal Pyramids</a>, J. Integer Seqs., Vol. 3 (2000), #00.1.6.</div> <div class=sectline>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)</div> <div class=sectline>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]</div> <div class=sectline>Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a> [Cached copy]</div> <div class=sectline>Brady Haran and Sergei Tabachnikov, <a href="https://www.youtube.com/watch?v=0mXz-NP-raY">Frieze Patterns</a>, Numberphile video (2019); <a href="https://www.youtube.com/watch?v=MJ1NAzpens4">more footage</a></div> <div class=sectline>F. Harary, E. M. Palmer, R. C. Read, <a href="/A000108/a000108_20.pdf">On the cell-growth problem for arbitrary polygons, computer printout, circa 1974</a></div> <div class=sectline>F. Harary & R. W. Robinson, <a href="/A000108/a000108_18.pdf">The number of achiral trees</a>, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)</div> <div class=sectline>Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.</div> <div class=sectline>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</div> <div class=sectline>A. M. Hinz, S. Klavžar, U. Milutinović and 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></div> <div class=sectline>V. E. Hoggatt, Jr., <a href="/A001628/a001628.pdf">Letters to N. J. A. Sloane, 1974-1975</a></div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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 [math.CO], 2014.</div> <div class=sectline>W. Hürlimann (2009). <a href="https://doi.org/10.1155/2009/970284">Generalizing Benford's law using power laws: application to integer sequences</a>. International Journal of Mathematics and Mathematical Sciences, Article ID 970284.</div> <div class=sectline>Hsien-Kuei Hwang, Mihyun Kang and Guan-Huei Duh, <a href="https://doi.org/10.4230/LIPIcs.AofA.2018.29">Asymptotic Expansions for Sub-Critical Lagrangean Forms</a>, LIPIcs Proceedings of Analysis of Algorithms (2018), Vol. 110, Article 29.</div> <div class=sectline>Anders Hyllengren, <a href="/A001006/a001006_5.pdf">Four integer sequences</a>, Oct 04 1985. Observes essentially that <a href="/A000984" title="Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.">A000984</a> and <a href="/A002426" title="Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n.">A002426</a> are inverse binomial transforms of each other, as are <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a> and <a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>.</div> <div class=sectline>INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=48">Encyclopedia of Combinatorial Structures 48</a>, <a href="http://ecs.inria.fr/services/structure?nbr=52">Encyclopedia of Combinatorial Structures 52</a>, <a href="http://ecs.inria.fr/services/structure?nbr=71">Encyclopedia of Combinatorial Structures 71</a>, <a href="http://ecs.inria.fr/services/structure?nbr=76">Encyclopedia of Combinatorial Structures 76</a>, and <a href="http://ecs.inria.fr/services/structure?nbr=284">Encyclopedia of Combinatorial Structures 284</a> [dead links]</div> <div class=sectline>Milan Janjić, <a href="https://arxiv.org/abs/1905.04465">On Restricted Ternary Words and Insets</a>, arXiv:1905.04465 [math.CO], 2019.</div> <div class=sectline>I. Jensen, <a href="https://web.archive.org/web/20190330111705 /https://researchers.ms.unimelb.edu.au/~ij@unimelb/polygons/Polygons_ser.html">Series expansions for self-avoiding polygons</a></div> <div class=sectline>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></div> <div class=sectline>A. Joseph and P. Lamprou, <a href="http://arxiv.org/abs/1512.00406">A new interpretation of Catalan numbers</a>, arXiv preprint arXiv:1512.00406 [math.CO], 2015.</div> <div class=sectline>R. Kahkeshani, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Kahkeshani/kahke3.html">A Generalization of the Catalan Numbers</a>, J. Int. Seq. 16 (2013) #13.6.8</div> <div class=sectline>A. Karttunen, <a href="/A014486/a014486.pdf">Illustration of initial terms up to size n=7</a></div> <div class=sectline>Nicholas M. Katz, <a href="https://web.math.princeton.edu/~nmk/catalan11.pdf">A note on random matrix integrals, moment identities, and Catalan numbers</a>, 2015.</div> <div class=sectline>Manuel Kauers and Doron Zeilberger, <a href="https://arxiv.org/abs/2006.10205">Counting Standard Young Tableaux With Restricted Runs</a>, arXiv:2006.10205 [math.CO], 2020.</div> <div class=sectline>J. Keitel and L. Bartosch, <a href="https://arxiv.org/abs/1109.3013">The zero-dimensional O(N) vector model as a benchmark for perturbation theory, the large-N expansion and the functional renormalisation group</a>, arXiv preprint arXiv:1109.3013 [cond-mat.stat-mech], 2012.</div> <div class=sectline>Clark 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.</div> <div class=sectline>Martin Klazar, <a href="http://arxiv.org/abs/1808.08449">What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I</a>, arXiv:1808.08449, 2018.</div> <div class=sectline>Martin Klazar and Richard Horský, <a href="https://arxiv.org/abs/2107.10717">Are the Catalan Numbers a Linear Recurrence Sequence?</a>, arXiv:2107.10717 [math.CO], 2021. Published in American Mathematical Monthly, 129:2, 166-171, DOI:10.1080/00029890.2022.2005392.</div> <div class=sectline>D. E. Knuth, <a href="http://arxiv.org/abs/math/9207221">Convolution polynomials</a>, The Mathematica J., 2 (1992), 67-78.</div> <div class=sectline>M. Konvalinka and S. Wagner, <a href="http://arxiv.org/abs/1412.01168">The shape of random tanglegrams</a>, arXiv preprint arXiv:1512.01168 [cond-mat.mes-hall], 2015.</div> <div class=sectline>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]</div> <div class=sectline>G. Kreweras, <a href="https://doi.org/10.1016/0012-365X(72)90041-6">Sur les partitions non croisées d'un cycle</a>, (in French) Discrete Math. 1 (1972), no. 4, 333-350. MR0309747 (46 #8852)</div> <div class=sectline>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]</div> <div class=sectline>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.</div> <div class=sectline>Shrinu Kushagra, Shai Ben-David and Ihab Ilyas, <a href="https://arxiv.org/abs/1810.04361">Semi-supervised clustering for de-duplication</a>, arXiv:1810.04361 [cs.LG], 2018.</div> <div class=sectline>Marie-Louise Lackner and M Wallner, <a href="http://dmg.tuwien.ac.at/mwallner/files/lpintro.pdf">An invitation to analytic combinatorics and lattice path counting</a>; Preprint, Dec 2015.</div> <div class=sectline>Wolfdieter 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.</div> <div class=sectline>Peter J. Larcombe, Daniel R. French, <a href="https://www.researchgate.net/publication/268646122">On the "Other" Catalan Numbers: A Historical Formulation Re-Examined</a>, Preprint 2000-2016.</div> <div class=sectline>P. J. Larcombe et al., <a href="https://www.fq.math.ca/Papers1/52-3/LarcombeOneillFennessey.pdf">On certain series expansions of the sine function: Catalan numbers and convergence</a>, Fib. Q., 52 (2014), 236-242.</div> <div class=sectline>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.</div> <div class=sectline>Pierre Lescanne, <a href="http://arxiv.org/abs/1312.4917">An exercise on streams: convergence acceleration</a>, arXiv preprint arXiv:1312.4917 [cs.NA], 2013.</div> <div class=sectline>Hsueh-Yung Lin, <a href="http://arxiv.org/abs/1012.1756">The odd Catalan numbers modulo 2^k</a>, arXiv:1012.1756 [math.NT], 2010-2011.</div> <div class=sectline>Elżbieta Liszewska and Wojciech Młotkowski, <a href="https://arxiv.org/abs/1907.10725">Some relatives of the Catalan sequence</a>, arXiv:1907.10725 [math.CO], 2019.</div> <div class=sectline>J.-L. Loday and B. Vallette, <a href="https://hdl.handle.net/21.11116/0000-0004-1D0F-D">Algebraic Operads</a>, version 0.999, 2012.</div> <div class=sectline>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.</div> <div class=sectline>Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/TheLostCatalanNumbers">The Lost Catalan Numbers And The Schröder Tableaux</a></div> <div class=sectline>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 [math.RA], 2013.</div> <div class=sectline>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.</div> <div class=sectline>C. Mallows and R. J. Vanderbei, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Vanderbei/vand3.html">Which Young Tableaux Can Represent an Outer Sum?</a>, J. Int. Seq. 18 (2015) 15.9.1.</div> <div class=sectline>K Manes, A Sapounakis, I Tasoulas, P Tsikouras, <a href="http://arxiv.org/abs/1510.01952">Equivalence classes of ballot paths modulo strings of length 2 and 3</a>, arXiv preprint arXiv:1510.01952 [math.CO], 2015.</div> <div class=sectline>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</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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 [math.CO]; Discrete Mathematics, Volume 309, Issue 12, Jun 28 2009, Pages 4079-4088</div> <div class=sectline>R. J. Marsh and P. P. Martin, <a href="http://arXiv.org/abs/math.CO/0612572">Pascal arrays: counting Catalan sets</a>, arXiv:math/0612572 [math.CO], 2006.</div> <div class=sectline>MathOverflow, <a href="https://mathoverflow.net/questions/112062/geometric-physical-probabilistic-interpretations-of-riemann-zetan1/401540#401540">Geometric / physical / probabilistic interpretations of Riemann zeta(n>1)?</a>, answer by Tom Copeland posted in Aug 2021.</div> <div class=sectline>Peter McCalla and Asamoah Nkwanta, <a href="https://arxiv.org/abs/1901.07092">Catalan and Motzkin Integral Representations</a>, arXiv:1901.07092 [math.NT], 2019.</div> <div class=sectline>Jon McCammond, <a href="http://arxiv.org/abs/math/0601687">Noncrossing partitions in surprising locations</a>, arXiv:math/0601687 [math.CO], 2006.</div> <div class=sectline>D. Merlini, R. Sprugnoli and M. C. Verri, <a href="https://doi.org/10.1016/j.dam.2003.11.012">Waiting patterns for a printer</a>Discrete Applied Mathematics, 144 (2004), 359-373; FUN with algorithm'01, Isola d'Elba, 2001.</div> <div class=sectline>Ângela Mestre and José Agapito, <a href="https://www.emis.de/journals/JIS/VOL22/Agapito/mestre8.html">A Family of Riordan Group Automorphisms</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.</div> <div class=sectline>Sam Miner and I. Pak, <a href="http://www.math.ucla.edu/~pak/papers/PermShapeShort.pdf">The shape of random pattern avoiding permutations</a>, 2013.</div> <div class=sectline>Marni Mishna and Lily Yen, <a href="http://arxiv.org/abs/1106.5036">Set partitions with no k-nesting</a>, arXiv:1106.5036 [math.CO], 2011.</div> <div class=sectline>S. Mizera, <a href="https://arxiv.org/abs/1706.08527">Combinatorics and Topology of Kawai-Lewellen-Tye Relations</a>, arXiv:1706.08527 [hep-th], 2017.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Torsten Mütze 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 [math.CO], 2011.</div> <div class=sectline>Liviu I. Nicolaescu, <a href="http://arxiv.org/abs/math/0512496">Counting Morse functions on the 2-sphere</a>, arXiv:math/0512496 [math.GT], 2005-2006.</div> <div class=sectline>J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/abs/math.CO/0405597">Free quasi-symmetric functions of arbitrary level</a>, arXiv:math/0405597 [math.CO], 2004.</div> <div class=sectline>R. J. Nowakowski, G. Renault, E. Lamoureux, S. Mellon and T. Miller, <a href="https://www.researchgate.net/publication/267170853_The_Game_of_timber">The Game of timber!</a>, 2013.</div> <div class=sectline>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]</div> <div class=sectline>Igor Pak, <a href="http://www.math.ucla.edu/~pak/lectures/Cat/pakcat.htm">Catalan Numbers Page</a></div> <div class=sectline>Igor Pak, <a href="http://igorpak.wordpress.com/2014/02/05/who-named-catalan-numbers/?">Who Named the Catalan Numbers?</a></div> <div class=sectline>Igor Pak, <a href="http://arxiv.org/abs/1408.5711">History of Catalan numbers</a>, arXiv:1408.5711 [math.HO], 2014.</div> <div class=sectline>Hao Pan and Zhi-Wei Sun, <a href="http://arxiv.org/abs/math.CO/0509648">A combinatorial identity with application to Catalan numbers</a>, arXiv:math/0509648 [math.CO], 2005-2006.</div> <div class=sectline>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.</div> <div class=sectline>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).</div> <div class=sectline>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]</div> <div class=sectline>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.</div> <div class=sectline>Ludovic Patey, <a href="https://arxiv.org/abs/1901.04388">Ramsey-like theorems and moduli of computation</a>, arXiv:1901.04388 [math.LO], 2019.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Robin Pemantle and Mark C. Wilson, <a href="http://dx.doi.org/10.1137/050643866">Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions</a>, SIAM Rev., 50 (2) (2008), 199-272.</div> <div class=sectline>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.</div> <div class=sectline>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).</div> <div class=sectline>T. K. Petersen and Bridget Eileen Tenner, <a href="http://arxiv.org/abs/1202.4765">The depth of a permutation</a>, arXiv:1202.4765 [math.CO], 2012-2014.</div> <div class=sectline>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.</div> <div class=sectline>Vincent Pilaud, <a href="http://arxiv.org/abs/1505.07665">Brick polytopes, lattice quotients, and Hopf algebras</a>, arXiv preprint arXiv:1505.07665 [math.CO], 2015.</div> <div class=sectline>Vincent Pilaud, <a href="https://arxiv.org/abs/2205.06686">Pebble trees</a>, arXiv:2205.06686 [math.CO], 2022.</div> <div class=sectline>Maxim V. Polyakov, Kirill M. Semenov-Tian-Shansky, Alexander O. Smirnov and Alexey A. Vladimirov, <a href="https://arxiv.org/abs/1811.08449">Quasi-Renormalizable Quantum Field Theories</a>, arXiv:1811.08449 [hep-th], 2018.</div> <div class=sectline>Alexander Postnikov, <a href="http://arxiv.org/abs/math/0507163">Permutohedra, associahedra, and beyond</a>, 2005, arXiv:math/0507163 [math.CO], 2005.</div> <div class=sectline>J.-B. Priez and 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 [math.CO], 2014-2015.</div> <div class=sectline>L. Pudwell and A. Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014.</div> <div class=sectline>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.</div> <div class=sectline>Alon Regev, Amitai Regev, and Doron Zeilberger, <a href="http://arxiv.org/abs/1507.03499">Identities in character tables of S_n</a>, arXiv preprint arXiv:1507.03499 [math.CO], 2015.</div> <div class=sectline>Amitai Regev, Nathaniel Shar, and Doron Zeilberger, <a href="http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/touchard.html">A Very Short (Bijective!) Proof of Touchard's Catalan Identity</a>, 2015.</div> <div class=sectline>Amitai Regev, Nathaniel Shar, and Doron Zeilberger, <a href="/A000108/a000108_21.pdf">A Very Short (Bijective!) Proof of Touchard's Catalan Identity</a>, [Local copy, pdf file only, no active links]</div> <div class=sectline>J.-L. Rémy, <a href="https://doi.org/10.1051/ita/1985190201791">Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire</a>, RAIRO Inform. Theor. 19 (1985), 179-195.</div> <div class=sectline>C. M. Ringel, <a href="http://arxiv.org/abs/1502.06553">The Catalan combinatorics of the hereditary artin algebras</a>, arXiv preprint arXiv:1502.06553 [math.RT], 2015.</div> <div class=sectline>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.</div> <div class=sectline>J. Riordan, <a href="/A003480/a003480.pdf">The distribution of crossings of chords joining pairs of 2n points on a circle</a>, Math. Comp., 29 (1975), 215-222. [Annotated scanned copy]</div> <div class=sectline>N. A. Rosenberg, <a href="https://doi.org/10.1089/cmb.2006.0109">Counting coalescent histories</a>, J. Comput Biol., 14 (2007), 360-377.</div> <div class=sectline>E. Rowland and R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv preprint arXiv:1310.8635 [math.NT], 2013-2014.</div> <div class=sectline>E. Rowland and 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 [math.CO], 2013.</div> <div class=sectline>Albert Sade, <a href="/A000108/a000108_17.pdf">Sur les Chevauchements des Permutations</a>, published by the author, Marseille, 1949. [Annotated scanned copy]</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>E. Schröder, <a href="/A000108/a000108_9.pdf">Vier combinatorische Probleme</a>, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]</div> <div class=sectline>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 [math.CO], 2014.</div> <div class=sectline>J. A. von Segner, <a href="https://archive.org/details/novicommentariia07impe/page/203">Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula</a>, Novi Comm. Acad. Scient. Imper. Petropolitanae, 7 (1758/1759), 203-209.</div> <div class=sectline>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.</div> <div class=sectline>L. W. Shapiro, <a href="http://dx.doi.org/10.1016/0012-365X(76)90009-1">A Catalan triangle</a>, Discrete Math., 14, 83-90, 1976.</div> <div class=sectline>L. W. Shapiro, <a href="/A003517/a003517.pdf">A Catalan triangle</a>, Discrete Math. 14 (1976), no. 1, 83-90. [Annotated scanned copy]</div> <div class=sectline>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]</div> <div class=sectline>N. J. A. Sloane, <a href="/A000108/a000108.html">Illustration of initial terms</a></div> <div class=sectline>N. J. A. Sloane, <a href="/A000108/a000108_16.pdf">Note on Sylvester's "On reducible cyclodes" paper</a> [Scanned copy]</div> <div class=sectline>N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 7.</div> <div class=sectline>N. Solomon and 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</div> <div class=sectline>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)</div> <div class=sectline>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.</div> <div class=sectline>R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers.html">Hipparchus, Plutarch, Schröder and Hough</a>, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.</div> <div class=sectline>R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/ec/catalan.pdf">Exercises on Catalan and Related Numbers</a></div> <div class=sectline>R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/ec#catadd">Catalan Addendum</a></div> <div class=sectline>R. P. Stanley, <a href="/A000108/a000108.pdf">Interpretations of Catalan Numbers (Notes)</a> [Annotated scanned copy]</div> <div class=sectline>P. J. Stockmeyer, <a href="/A006078/a006078.pdf">The charm bracelet problem and its applications</a>, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]</div> <div class=sectline>T. Stojadinovic, <a href="https://doi.org/10.13140/RG.2.1.2996.9129">The Catalan numbers</a>, Preprint 2015.</div> <div class=sectline>C. Stump, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Stump/stump4.html">On a New Collection of Words in the Catalan Family</a>, J. Int. Seq. 17 (2014) # 14.7.1</div> <div class=sectline>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 [math.NT], 2007-2011.</div> <div class=sectline>V. S. Sunder, <a href="http://www.imsc.res.in/~sunder/catalan.pdf">Catalan numbers</a></div> <div class=sectline>P. Tarau, <a href="https://pdfs.semanticscholar.org/eefb/e30e99067c8077e133749d83734b5daf188b.pdf">Computing with Catalan Families</a>, 2013, <a href="https://doi.org/10.1007/978-3-319-28228-2_8">doi:10.1007/978-3-319-28228-2_8</a>.</div> <div class=sectline>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 [cs.MS], 2014.</div> <div class=sectline>P. Tarau, <a href="http://arxiv.org/abs/1507.06944">A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations</a>, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.</div> <div class=sectline>I. Tasoulas, K. Manes, A. Sapounakis and P. Tsikouras, <a href="https://arxiv.org/abs/1911.10883">Chains with Small Intervals in the Lattice of Binary Paths</a>, arXiv:1911.10883 [math.CO], 2019.</div> <div class=sectline>D. Taylor, <a href="http://www.maths.usyd.edu.au/u/don/code/Catalan/Catalan.html">Catalan Structures(up to C(7))</a>.</div> <div class=sectline>B. E. Tenner, <a href="https://arxiv.org/abs/2001.05011">Interval structures in the Bruhat and weak orders</a>, arXiv:2001.05011 [math.CO], 2020.</div> <div class=sectline>Thotsaporn "Aek" Thanatipanonda and Doron Zeilberger, <a href="https://arxiv.org/abs/1909.11546">A Multi-Computational Exploration of Some Games of Pure Chance</a>, arXiv:1909.11546 [math.CO], 2019.</div> <div class=sectline>I. Todorov, <a href="https://arxiv.org/abs/1311.7258">Studying Quantum Field Theory</a>, arXiv:1311.7258 [math-ph], 2013.</div> <div class=sectline>Michael Torpey, <a href="https://doi.org/10.17630/10023-17350">Semigroup congruences: computational techniques and theoretical applications</a>, Ph.D. Thesis, University of St. Andrews (Scotland, 2019).</div> <div class=sectline>J.-D. Urbina, J. Kuipers, Q. Hummel and 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 [quant-ph], 2014.</div> <div class=sectline>A. Vieru, <a href="http://arxiv.org/abs/1107.2938">Agoh's conjecture: its proof, its generalizations, its analogues</a>, arXiv:1107.2938 [math.NT], 2011.</div> <div class=sectline>Gérard Villemin, <a href="http://villemin.gerard.free.fr/aNombre/TYPDENOM/Catalan/Catalan.htm">Nombres De Catalan</a> (French)</div> <div class=sectline>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.</div> <div class=sectline>Wenxi Wang, Muhammad Usman, Alyas Almaawi, Kaiyuan Wang, Kuldeep S. Meel and Sarfraz Khurshid, <a href="https://www.comp.nus.edu.sg/~meel/Papers/tacas20.pdf">A Study of Symmetry Breaking Predicates and Model Counting</a>, National University of Singapore (2020).</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BinaryBracketing.html">Binary Bracketing</a>.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BinaryTree.html">Binary Tree</a>.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CatalanNumber.html">Catalan Number</a>.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DyckPath.html">Dyck Path</a>.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/NonassociativeProduct.html">Nonassociative Product</a>.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/StaircaseWalk.html">Staircase Walk</a>.</div> <div class=sectline>Wikipedia, <a href="https://en.wikipedia.org/wiki/Catalan_number">Catalan number</a></div> <div class=sectline>J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, <a href="https://ir.cwi.nl/pub/21313">Context-free coalgebras</a>, 2013.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Chunyan Yan and Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.</div> <div class=sectline>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.</div> <div class=sectline>Yan X Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv preprint arXiv:1508.00318 [math.CO], 2015.</div> <div class=sectline><a href="/index/Cor#core">Index entries for "core" sequences</a></div> <div class=sectline><a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a></div> <div class=sectline><a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a></div> <div class=sectline><a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a></div> <div class=sectline><a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a></div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>a(n) = binomial(2*n, n)/(n+1) = (2*n)!/(n!*(n+1)!) = <a href="/A000984" title="Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.">A000984</a>(n)/(n+1).</div> <div class=sectline>Recurrence: a(n) = 2*(2*n-1)*a(n-1)/(n+1) with a(0) = 1.</div> <div class=sectline>Recurrence: a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).</div> <div class=sectline>G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x), and satisfies A(x) = 1 + x*A(x)^2.</div> <div class=sectline>a(n) = Product_{k=2..n} (1 + n/k).</div> <div class=sectline>a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i). - Touchard</div> <div class=sectline>It is known that a(n) is odd if and only if n=2^k-1, k=0, 1, 2, 3, ... - <a href="/wiki/User:Emeric_Deutsch">Emeric Deutsch</a>, Aug 04 2002, corrected by <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Nov 08 2015</div> <div class=sectline>Using the Stirling approximation in <a href="/A000142" title="Factorial numbers: n! = 1*2*3*4*...*n (order of symmetric group S_n, number of permutations of n letters).">A000142</a> 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</div> <div class=sectline>Integral representation: a(n) = (1/(2*Pi))*Integral_{x=0..4} x^n*sqrt((4-x)/x). - <a href="/wiki/User:Karol_A._Penson">Karol A. Penson</a>, Apr 12 2001</div> <div class=sectline>E.g.f.: exp(2*x)*(I_0(2*x)-I_1(2*x)), where I_n is Bessel function. - <a href="/wiki/User:Karol_A._Penson">Karol A. Penson</a>, Oct 07 2001</div> <div class=sectline>a(n) = polygorial(n, 6)/polygorial(n, 3). - Daniel Dockery (peritus(AT)gmail.com), Jun 24 2003</div> <div class=sectline>G.f. A(x) satisfies ((A(x) + A(-x)) / 2)^2 = A(4*x^2). - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Jun 27, 2003</div> <div class=sectline>G.f. A(x) satisfies Sum_{k>=1} k(A(x)-1)^k = Sum_{n>=1} 4^{n-1}*x^n. - Shapiro, Woan, Getu</div> <div class=sectline>a(n+m) = Sum_{k} <a href="/A039599" title="Triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).">A039599</a>(n, k)*<a href="/A039599" title="Triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).">A039599</a>(m, k). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Dec 22 2003</div> <div class=sectline>a(n+1) = (1/(n+1))*Sum_{k=0..n} a(n-k)*binomial(2k+1, k+1). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Jan 24 2004</div> <div class=sectline>a(n) = Sum_{k>=0} <a href="/A008313" title="Triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).">A008313</a>(n, k)^2. - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Feb 14 2004</div> <div class=sectline>a(m+n+1) = Sum_{k>=0} <a href="/A039598" title="Triangle formed from odd-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x)....">A039598</a>(m, k)*<a href="/A039598" title="Triangle formed from odd-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x)....">A039598</a>(n, k). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Feb 15 2004</div> <div class=sectline>a(n) = Sum_{k=0..n} (-1)^k*2^(n-k)*binomial(n, k)*binomial(k, floor(k/2)). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Jan 27 2005</div> <div class=sectline>Sum_{n>=0} 1/a(n) = 2 + 4*Pi/3^(5/2) = F(1,2;1/2;1/4) = <a href="/A268813" title="Decimal expansion of sum(k>=0, 1/C(k)), where C(k) is a Catalan Number (A000108).">A268813</a> = 2.806133050770763... (see L'Univers de Pi link). - <a href="/wiki/User:Gerald_McGarvey">Gerald McGarvey</a> and <a href="/wiki/User:Benoit_Cloitre">Benoit Cloitre</a>, Feb 13 2005</div> <div class=sectline>a(n) = Sum_{k=0..floor(n/2)} ((n-2*k+1)*binomial(n, n-k)/(n-k+1))^2, which is equivalent to: a(n) = Sum_{k=0..n} <a href="/A053121" title="Catalan triangle (with 0's) read by rows.">A053121</a>(n, k)^2, for n >= 0. - <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Apr 23 2005</div> <div class=sectline>a((m+n)/2) = Sum_{k>=0} <a href="/A053121" title="Catalan triangle (with 0's) read by rows.">A053121</a>(m, k)*<a href="/A053121" title="Catalan triangle (with 0's) read by rows.">A053121</a>(n, k) if m+n is even. - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, May 26 2005</div> <div class=sectline>E.g.f. Sum_{n>=0} a(n) * x^(2*n) / (2*n)! = BesselI(1, 2*x) / x. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Jun 22 2005</div> <div class=sectline>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. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Jun 27 2005</div> <div class=sectline>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)). - <a href="/wiki/User:Franklin_T._Adams-Watters">Franklin T. Adams-Watters</a>, Feb 08 2006</div> <div class=sectline>Sum_{k>=1} a(k)/4^k = 1. - <a href="/wiki/User:Franklin_T._Adams-Watters">Franklin T. Adams-Watters</a>, Jun 28 2006</div> <div class=sectline>a(n) = <a href="/A047996" title="Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.">A047996</a>(2*n+1, n). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Jul 25 2006</div> <div class=sectline>Binomial transform of <a href="/A005043" title="Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).">A005043</a>. - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Oct 20 2006</div> <div class=sectline>a(n) = Sum_{k=0..n} (-1)^k*<a href="/A116395" title="Riordan array (1/sqrt(1-4*x), (1/sqrt(1-4*x)-1)/2).">A116395</a>(n,k). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Nov 07 2006</div> <div class=sectline>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].</div> <div class=sectline>a(k) = Sum_{i=1..k} |<a href="/A008276" title="Triangle of Stirling numbers of first kind, s(n, n-k+1), n >= 1, 1 <= k <= n. Also triangle T(n,k) giving coefficients in ex...">A008276</a>(i,k)| * (k-1)^(k-i) / k!. - <a href="/wiki/User:André_F._Labossière">André F. Labossière</a>, May 29 2007</div> <div class=sectline>a(n) = Sum_{k=0..n} <a href="/A129818" title="Riordan array (1/(1+x), x/(1+x)^2), inverse array is A039599.">A129818</a>(n,k) * <a href="/A007852" title="Antichains in rooted plane trees on n nodes.">A007852</a>(k+1). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Jun 20 2007</div> <div class=sectline>a(n) = Sum_{k=0..n} <a href="/A109466" title="Riordan array (1, x(1-x)).">A109466</a>(n,k) * <a href="/A127632" title="Expansion of c(x*c(x)), where c(x) is the g.f. for A000108.">A127632</a>(k). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Jun 20 2007</div> <div class=sectline>Row sums of triangle <a href="/A124926" title="Triangle read by rows: T(n,k) = binomial(n,k)*r(k), where r(k) are the Riordan numbers (r(k) = A005043(k); 0 <= k <= n).">A124926</a>. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Oct 22 2007</div> <div class=sectline>Limit_{n->oo} (1 + Sum_{k=0..n} a(k)/<a href="/A004171" title="a(n) = 2^(2n+1).">A004171</a>(k)) = 4/Pi. - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Aug 26 2008</div> <div class=sectline>a(n) = Sum_{k=0..n} <a href="/A120730" title="Another version of Catalan triangle A009766.">A120730</a>(n,k)^2 and a(k+1) = Sum_{n>=k} <a href="/A120730" title="Another version of Catalan triangle A009766.">A120730</a>(n,k). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Oct 18 2008</div> <div class=sectline>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])). - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Oct 27 2008</div> <div class=sectline>a(n) = Sum_{l_1=0..n+1} Sum_{l_2=0..n}...Sum_{l_i=0..n-i}...Sum_{l_n=0..1} delta(l_1,l_2,...,l_i,...,l_n) where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i < l_(i+1) and l_(i+1) <> 0 for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. - <a href="/wiki/User:Thomas_Wieder">Thomas Wieder</a>, Feb 25 2009</div> <div class=sectline>a(n) = <a href="/A000680" title="a(n) = (2n)!/2^n.">A000680</a>(n)/<a href="/A006472" title="a(n) = n!*(n-1)!/2^(n-1).">A006472</a>(n+1). - <a href="/wiki/User:Mark_Dols">Mark Dols</a>, Jul 14 2010; corrected by <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Nov 08 2015</div> <div class=sectline>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. - <a href="/wiki/User:Vladimir_Kruchinin">Vladimir Kruchinin</a>, Jan 18 2011</div> <div class=sectline>Complement of <a href="/A092459" title="Numbers that are not Catalan numbers (A000108).">A092459</a>; <a href="/A010058" title="1 if n is a Catalan number else 0.">A010058</a>(a(n)) = 1. - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Mar 29 2011</div> <div class=sectline>G.f.: 1/(1-x/(1-x/(1-x/(...)))) (continued fraction). - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Mar 18 2011</div> <div class=sectline>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). - <a href="/wiki/User:Tom_Copeland">Tom Copeland</a>, Sep 04 2011</div> <div class=sectline>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 <a href="/A115291" title="Expansion of (1+x)^3/(1-x).">A115291</a>. - <a href="/wiki/User:Tom_Copeland">Tom Copeland</a>, Sep 04 2011</div> <div class=sectline>From <a href="/wiki/User:Tom_Copeland">Tom Copeland</a>, Sep 30 2011: (Start)</div> <div class=sectline>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 <a href="/A125181" title="Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n whose ascent lengths form the k-th partition of th...">A125181</a>.</div> <div class=sectline>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)). (End)</div> <div class=sectline>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). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, Nov 30 2011</div> <div class=sectline>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). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, Nov 30 2011</div> <div class=sectline>E.g.f.: Hypergeometric([1/2],[2],4*x) which coincides with the e.g.f. given just above, and also by <a href="/wiki/User:Karol_A._Penson">Karol A. Penson</a> further above. - <a href="/wiki/User:Wolfdieter_Lang">Wolfdieter Lang</a>, Jan 13 2012</div> <div class=sectline><a href="/A076050" title="Limiting sequence if we start with 2 and successively replace n with 2,3,4,...,n,n+1.">A076050</a>(a(n)) = n + 1 for n > 0. - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Feb 17 2012</div> <div class=sectline>a(n) = <a href="/A208355" title="Right edge of the triangle in A208101.">A208355</a>(2*n-1) = <a href="/A208355" title="Right edge of the triangle in A208101.">A208355</a>(2*n) for n > 0. - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Mar 04 2012</div> <div class=sectline>a(n+1) = <a href="/A214292" title="Triangle read by rows: T(n,k) = T(n-1,k-1) + T(n-1,k), 0 < k < n with T(n,0) = n and T(n,n) = -n.">A214292</a>(2*n+1,n) = <a href="/A214292" title="Triangle read by rows: T(n,k) = T(n-1,k-1) + T(n-1,k), 0 < k < n with T(n,0) = n and T(n,n) = -n.">A214292</a>(2*n+2,n). - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Jul 12 2012</div> <div class=sectline>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). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, Sep 20 2012</div> <div class=sectline>G.f.: hypergeom([1/2,1],[2],4*x). - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Apr 06 2013</div> <div class=sectline>Special values of Jacobi polynomials, in Maple notation: a(n) = 4^n*JacobiP(n,1,-1/2-n,-1)/(n+1). - <a href="/wiki/User:Karol_A._Penson">Karol A. Penson</a>, Jul 28 2013</div> <div class=sectline>For n > 0: a(n) = sum of row n in triangle <a href="/A001263" title="Triangle of Narayana numbers T(n,k) = C(n-1,k-1)*C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle.">A001263</a>. - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Oct 10 2013</div> <div class=sectline>a(n) = binomial(2n,n-1)/n and a(n) mod n = binomial(2n,n) mod n = <a href="/A059288" title="a(n) = binomial(2*n,n) mod n.">A059288</a>(n). - <a href="/wiki/User:Jonathan_Sondow">Jonathan Sondow</a>, Dec 14 2013</div> <div class=sectline>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. - <a href="/wiki/User:Mircea_Merca">Mircea Merca</a>, Feb 27 2014</div> <div class=sectline>a(n) = Sum_{k=1..n} binomial(n+k-1,n)/n if n > 0. <a href="/wiki/User:Alexander_Adamchuk">Alexander Adamchuk</a>, Mar 25 2014</div> <div class=sectline>a(n) = -2^(2*n+1) * binomial(n-1/2, -3/2). - <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, May 06 2014</div> <div class=sectline>a(n) = (4*<a href="/A000984" title="Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.">A000984</a>(n) - <a href="/A000984" title="Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.">A000984</a>(n+1))/2. - <a href="/wiki/User:Stanislav_Sykora">Stanislav Sykora</a>, Aug 09 2014</div> <div class=sectline>a(n) = <a href="/A246458" title="Catalan number analogs for A048804, the generalized binomial coefficients for the radical sequence (A007947).">A246458</a>(n) * <a href="/A246466" title="Catalan number analogs for A246465, the generalized binomial coefficients for A003557.">A246466</a>(n). - <a href="/wiki/User:Tom_Edgar">Tom Edgar</a>, Sep 02 2014</div> <div class=sectline>a(n) = (2*n)!*[x^(2*n)]hypergeom([],[2],x^2). - <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Jan 31 2015</div> <div class=sectline>a(n) = 4^(n-1)*hypergeom([3/2, 1-n], [3], 1). - <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Feb 03 2015</div> <div class=sectline>a(2n) = 2*<a href="/A000150" title="Number of dissections of an n-gon, rooted at an exterior edge, asymmetric with respect to that edge.">A000150</a>(2n); a(2n+1) = 2*<a href="/A000150" title="Number of dissections of an n-gon, rooted at an exterior edge, asymmetric with respect to that edge.">A000150</a>(2n+1) + a(n). - <a href="/wiki/User:John_Bodeen">John Bodeen</a>, Jun 24 2015</div> <div class=sectline>a(n) = Sum_{t=1..n+1} n^(t-1)*abs(Stirling1(n+1, t)) / Sum_{t=1..n+1} abs(Stirling1(n+1, t)), for n > 0, see (10) in Cereceda link. - <a href="/wiki/User:Michel_Marcus">Michel Marcus</a>, Oct 06 2015</div> <div class=sectline>a(n) ~ 4^(n-2)*(128 + 160/N^2 + 84/N^4 + 715/N^6 - 10180/N^8)/(N^(3/2)*Pi^(1/2)) where N = 4*n+3. - <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Oct 14 2015</div> <div class=sectline>a(n) = Sum_{k=1..floor((n+1)/2)} (-1)^(k-1)*binomial(n+1-k,k)*a(n-k) if n > 0; and a(0) = 1. - <a href="/wiki/User:David_Pasino">David Pasino</a>, Jun 29 2016</div> <div class=sectline>Sum_{n>=0} (-1)^n/a(n) = 14/25 - 24*arccsch(2)/(25*sqrt(5)) = 14/25 - 24*<a href="/A002390" title="Decimal expansion of natural logarithm of golden ratio.">A002390</a>/(25*sqrt(5)) = 0.353403708337278061333... - <a href="/wiki/User:Ilya_Gutkovskiy">Ilya Gutkovskiy</a>, Jun 30 2016</div> <div class=sectline>C(n) = (1/n) * Sum_{i+j+k=n-1} C(i)*C(j)*C(k)*(k+1), n >= 1. - <a href="/wiki/User:Yuchun_Ji">Yuchun Ji</a>, Feb 21 2016</div> <div class=sectline>C(n) = 1 + Sum_{i+j+k<n-1} C(i)*C(j)*C(k). - <a href="/wiki/User:Yuchun_Ji">Yuchun Ji</a>, Sep 01 2016</div> <div class=sectline>a(n) = <a href="/A001700" title="a(n) = binomial(2*n+1, n+1): number of ways to put n+1 indistinguishable balls into n+1 distinguishable boxes = number of (n...">A001700</a>(n) - <a href="/A162551" title="a(n) = 2 * C(2*n,n-1).">A162551</a>(n) = binomial(2*n+1,n+1). - 2*binomial(2*n,n-1). - <a href="/wiki/User:Taras_Goy">Taras Goy</a>, Aug 09 2018</div> <div class=sectline>G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x) = 2F1(1/2,1;2;4*x). G.f. A(x) satisfies A = 1 + x*A^2. - <a href="/wiki/User:R._J._Mathar">R. J. Mathar</a>, Nov 17 2018</div> <div class=sectline>C(n) = 1 + Sum_{i=0..n-1} <a href="/A000245" title="a(n) = 3*(2*n)!/((n+2)!*(n-1)!).">A000245</a>(i). - <a href="/wiki/User:Yuchun_Ji">Yuchun Ji</a>, Jan 10 2019</div> <div class=sectline>From <a href="/wiki/User:A.H.M._Smeets">A.H.M. Smeets</a>, Apr 11 2020: (Start)</div> <div class=sectline>(1+sqrt(1+4*x))/2 = 1-Sum_{i >= 0} a(i)*(-x)^(i+1), for any complex x with |x| < 1/4; and sqrt(x+sqrt(x+sqrt(x+...))) = 1-Sum_{i >= 0} a(i)*(-x)^(i+1), for any complex x with |x| < 1/4 and x <> 0. (End)</div> <div class=sectline>a(3n+1)*a(5n+4)*a(15n+10) = a(3n+2)*a(5n+2)*a(15n+11). The first case of Catalan product equation of a triple partition of 23n+15. - <a href="/wiki/User:Yuchun_Ji">Yuchun Ji</a>, Sep 27 2020</div> <div class=sectline>a(n) = 4^n * (-1)^(n+1) * 3F2[{n + 1,n + 1/2,n}, {3/2,1}, -1], n >= 1. - <a href="/wiki/User:Sergii_Voloshyn">Sergii Voloshyn</a>, Oct 22 2020</div> <div class=sectline>a(n) = 2^(1 + 2 n) * (-1)^(n)/(1 + n) * 3F2[{n, 1/2 + n, 1 + n}, {1/2, 1}, -1], n >= 1. - <a href="/wiki/User:Sergii_Voloshyn">Sergii Voloshyn</a>, Nov 08 2020</div> <div class=sectline>a(n) = (1/Pi)*4^(n+1)*Integral_{x=0..Pi/2} cos(x)^(2*n)*sin(x)^2 dx. - <a href="/wiki/User:Greg_Dresden">Greg Dresden</a>, May 30 2021</div> <div class=sectline>From <a href="/wiki/User:Peter_Bala">Peter Bala</a>, Aug 17 2021: (Start)</div> <div class=sectline>G.f. A(x) satisfies A(x) = 1/sqrt(1 - 4*x) * A( -x/(1 - 4*x) ) and (A(x) + A(-x))/2 = 1/sqrt(1 - 4*x) * A( -2*x/(1 - 4*x) ); these are the cases k = 0 and k = -1 of the general formula 1/sqrt(1 - 4*x) * A( (k-1)*x/(1 - 4*x) ) = Sum_{n >= 0} ((k^(n+1) - 1)/(k - 1))*Catalan(n)*x^n.</div> <div class=sectline>2 - sqrt(1 - 4*x)/A( k*x/(1 - 4*x) ) = 1 + Sum_{n >= 1} (1 + (k + 1)^n) * Catalan(n-1)*x^n. (End)</div> <div class=sectline>Sum_{n>=0} a(n)*(-1/4)^n = 2*(sqrt(2)-1) (<a href="/A163960" title="Decimal expansion of 2*(sqrt(2) - 1).">A163960</a>). - <a href="/wiki/User:Amiram_Eldar">Amiram Eldar</a>, Mar 22 2022</div> <div class=sectline>0 = a(n)*(16*a(n+1) - 10*a(n+2)) + a(n+1)*(2*a(n+1) + a(n+2)) for all n>=0. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Dec 12 2022</div> <div class=sectline>G.f.: (offset 1) 1/G(x), with G(x) = 1 - 2*x - x^2/G(x) (Jacobi continued fraction). - <a href="/wiki/User:Nikolaos_Pantelidis">Nikolaos Pantelidis</a>, Feb 01 2023</div> <div class=sectline>a(n) = K^(2n+1, n, 1) for all n >= 0, where K^(n, s, x) is the Krawtchouk polynomial defined to be Sum_{k=0..s} (-1)^k * binomial(n-x, s-k) * binomial(x, k). - <a href="/wiki/User:Vladislav_Shubin">Vladislav Shubin</a>, Aug 17 2023</div> <div class=sectline>From <a href="/wiki/User:Peter_Bala">Peter Bala</a>, Feb 03 2024: (Start)</div> <div class=sectline>The g.f. A(x) satisfies the following functional equations:</div> <div class=sectline>A(x) = 1 + x/(1 - 4*x) * A(-x/(1 - 4*x))^2,</div> <div class=sectline>A(x^2) = 1/(1 - 2*x) * A(- x/(1 - 2*x))^2 and, for arbitrary k,</div> <div class=sectline>1/(1 - k*x) * A(x/(1 - k*x))^2 = 1/(1 - (k+4)*x) * A(-x/(1 - (k+4)*x))^2. (End)</div> <div class=sectline>a(n) = <a href="/A363448" title="Number of noncrossing partitions of the n-set with no pair of singletons {i} and {j} that can be merged into {i,j} and leave...">A363448</a>(n) + <a href="/A363449" title="Number of noncrossing partitions of the n-set with some pair of singletons {i} and {j} that can be merged into {i,j} and lea...">A363449</a>(n). - <a href="/wiki/User:Julien_Rouyer">Julien Rouyer</a>, Jun 28 2024</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>From <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a> and Greg Stevenson, Jul 11 2011: (Start)</div> <div class=sectline>The following products of 3 transpositions lead to a 4-cycle in S_4:</div> <div class=sectline>(1,2)*(1,3)*(1,4);</div> <div class=sectline>(1,2)*(1,4)*(3,4);</div> <div class=sectline>(1,3)*(1,4)*(2,3);</div> <div class=sectline>(1,4)*(2,3)*(2,4);</div> <div class=sectline>(1,4)*(2,4)*(3,4). (End)</div> <div class=sectline>G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + ...</div> <div class=sectline>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. - <a href="/wiki/User:Dennis_P._Walsh">Dennis P. Walsh</a>, Apr 11 2012</div> <div class=sectline>From <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Jun 30 2014: (Start)</div> <div class=sectline>The a(4) = 14 branching sequences of the (ordered) trees with 4 non-root nodes are (dots denote zeros):</div> <div class=sectline>01: [ 1 1 1 1 . ]</div> <div class=sectline>02: [ 1 1 2 . . ]</div> <div class=sectline>03: [ 1 2 . 1 . ]</div> <div class=sectline>04: [ 1 2 1 . . ]</div> <div class=sectline>05: [ 1 3 . . . ]</div> <div class=sectline>06: [ 2 . 1 1 . ]</div> <div class=sectline>07: [ 2 . 2 . . ]</div> <div class=sectline>08: [ 2 1 . 1 . ]</div> <div class=sectline>09: [ 2 1 1 . . ]</div> <div class=sectline>10: [ 2 2 . . . ]</div> <div class=sectline>11: [ 3 . . 1 . ]</div> <div class=sectline>12: [ 3 . 1 . . ]</div> <div class=sectline>13: [ 3 1 . . . ]</div> <div class=sectline>14: [ 4 . . . . ]</div> <div class=sectline>(End)</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline><a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a> := n->binomial(2*n, n)/(n+1);</div> <div class=sectline>G000108 := (1 - sqrt(1 - 4*x)) / (2*x);</div> <div class=sectline>spec := [ A, {A=Prod(Z, Sequence(A))}, unlabeled ]: [ seq(combstruct[count](spec, size=n+1), n=0..42) ];</div> <div class=sectline>with(combstruct): bin := {B=Union(Z, Prod(B, B))}: seq(count([B, bin, unlabeled], size=n+1), n=0..25); # <a href="/wiki/User:Zerinvary_Lajos">Zerinvary Lajos</a>, Dec 05 2007</div> <div class=sectline>gser := series(G000108, x=0, 42): seq(coeff(gser, x, n), n=0..41); # <a href="/wiki/User:Zerinvary_Lajos">Zerinvary Lajos</a>, May 21 2008</div> <div class=sectline>seq((2*n)!*coeff(series(hypergeom([], [2], x^2), x, 2*n+2), x, 2*n), n=0..30); # <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Jan 31 2015</div> <div class=sectline>A000108List := proc(m) local A, P, n; A := [1, 1]; P := [1];</div> <div class=sectline>for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), A[-1]]);</div> <div class=sectline>A := [op(A), P[-1]] od; A end: A000108List(31); # <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Mar 24 2022</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>Table[(2 n)!/n!/(n + 1)!, {n, 0, 20}]</div> <div class=sectline>Table[4^n Gamma[n + 1/2]/(Sqrt[Pi] Gamma[n + 2]), {n, 0, 20}] (* <a href="/wiki/User:Eric_W._Weisstein">Eric W. Weisstein</a>, Oct 31 2024 *)</div> <div class=sectline>Table[Hypergeometric2F1[1 - n, -n, 2, 1], {n, 0, 20}] (* <a href="/wiki/User:Richard_L._Ollerton">Richard L. Ollerton</a>, Sep 13 2006 *)</div> <div class=sectline>Table[CatalanNumber @ n, {n, 0, 20}] (* <a href="/wiki/User:Robert_G._Wilson_v">Robert G. Wilson v</a>, Feb 15 2011 *)</div> <div class=sectline>CatalanNumber[Range[0, 20]] (* <a href="/wiki/User:Eric_W._Weisstein">Eric W. Weisstein</a>, Oct 31 2024 *)</div> <div class=sectline>CoefficientList[InverseSeries[Series[x/Sum[x^n, {n, 0, 31}], {x, 0, 31}]]/x, x] (* <a href="/wiki/User:Mats_Granvik">Mats Granvik</a>, Nov 24 2013 *)</div> <div class=sectline>CoefficientList[Series[(1 - Sqrt[1 - 4 x])/(2 x), {x, 0, 20}], x] (* <a href="/wiki/User:Stefano_Spezia">Stefano Spezia</a>, Aug 31 2018 *)</div> <div class=sectline>With[{n=21}, CoefficientList[Exp[2x] (BesselI[0, 2x]-BesselI[1, 2x])+O[x]^n, x] Range[0, n-1]!] (* <a href="/wiki/User:Oliver_Seipel">Oliver Seipel</a>, Nov 16 2024. after <a href="/wiki/User:Karol_A._Penson">Karol A. Penson</a> *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(PARI) a(n)=binomial(2*n, n)/(n+1) \\ <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Aug 25 2012</div> <div class=sectline>(PARI) a(n) = (2*n)! / n! / (n+1)!</div> <div class=sectline>(PARI) a(n) = my(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));</div> <div class=sectline>(PARI) {a(n) = if( n<1, n==0, polcoeff( serreverse( x / (1 + x)^2 + x * O(x^n)), n))}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a> */</div> <div class=sectline>(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); \\ <a href="/wiki/User:R._J._Cano">R. J. Cano</a>, Nov 22 2012</div> <div class=sectline>(PARI) x='x+O('x^40); Vec((1-sqrt(1-4*x))/(2*x)) \\ <a href="/wiki/User:Altug_Alkan">Altug Alkan</a>, Oct 13 2015</div> <div class=sectline>(MuPAD) combinat::dyckWords::count(n) $ n = 0..38 // <a href="/wiki/User:Zerinvary_Lajos">Zerinvary Lajos</a>, Apr 14 2007</div> <div class=sectline>(Magma) C:= func< n | Binomial(2*n, n)/(n+1) >; [ C(n) : n in [0..60]];</div> <div class=sectline>(Magma) [Catalan(n): n in [0..40]]; // <a href="/wiki/User:Vincenzo_Librandi">Vincenzo Librandi</a>, Apr 02 2011</div> <div class=sectline>(Haskell)</div> <div class=sectline>import Data.List (genericIndex)</div> <div class=sectline>a000108 n = genericIndex a000108_list n</div> <div class=sectline>a000108_list = 1 : catalan [1] where</div> <div class=sectline> catalan cs = c : catalan (c:cs) where</div> <div class=sectline> c = sum $ zipWith (*) cs $ reverse cs</div> <div class=sectline>-- <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Nov 12 2011</div> <div class=sectline>a000108 = map last $ iterate (scanl1 (+) . (++ [0])) [1]</div> <div class=sectline>-- <a href="/wiki/User:David_Spies">David Spies</a>, Aug 23 2015</div> <div class=sectline>(Sage) [catalan_number(i) for i in range(27)] # <a href="/wiki/User:Zerinvary_Lajos">Zerinvary Lajos</a>, Jun 26 2008</div> <div class=sectline>(Sage) # Generalized algorithm of L. Seidel</div> <div class=sectline>def <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>_list(n) :</div> <div class=sectline> D = [0]*(n+1); D[1] = 1</div> <div class=sectline> b = True; h = 1; R = []</div> <div class=sectline> for i in range(2*n-1) :</div> <div class=sectline> if b :</div> <div class=sectline> for k in range(h, 0, -1) : D[k] += D[k-1]</div> <div class=sectline> h += 1; R.append(D[1])</div> <div class=sectline> else :</div> <div class=sectline> for k in range(1, h, 1) : D[k] += D[k+1]</div> <div class=sectline> b = not b</div> <div class=sectline> return R</div> <div class=sectline><a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>_list(31) # <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Jun 02 2012</div> <div class=sectline>(Maxima) <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>(n):=binomial(2*n, n)/(n+1)$ makelist(<a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>(n), n, 0, 30); /* <a href="/wiki/User:Martin_Ettl">Martin Ettl</a>, Oct 24 2012 */</div> <div class=sectline>(Python)</div> <div class=sectline>from gmpy2 import divexact</div> <div class=sectline><a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a> = [1, 1]</div> <div class=sectline>for n in range(1, 10**3):</div> <div class=sectline> <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>.append(divexact(<a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>[-1]*(4*n+2), (n+2))) # <a href="/wiki/User:Chai_Wah_Wu">Chai Wah Wu</a>, Aug 31 2014</div> <div class=sectline>(Python)</div> <div class=sectline># Works in Sage also.</div> <div class=sectline><a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a> = [1]</div> <div class=sectline>for n in range(1000):</div> <div class=sectline> <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>.append(<a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>[-1]*(4*n+2)//(n+2)) # <a href="/wiki/User:Günter_Rote">Günter Rote</a>, Nov 08 2023</div> <div class=sectline>(GAP) <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>:=List([0..30], n->Binomial(2*n, n)/(n+1)); # <a href="/wiki/User:Muniru_A_Asiru">Muniru A Asiru</a>, Feb 17 2018</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Cf. <a href="/A000142" title="Factorial numbers: n! = 1*2*3*4*...*n (order of symmetric group S_n, number of permutations of n letters).">A000142</a>, <a href="/A000245" title="a(n) = 3*(2*n)!/((n+2)!*(n-1)!).">A000245</a>, <a href="/A000344" title="a(n) = 5*binomial(2n, n-2)/(n+3).">A000344</a>, <a href="/A000588" title="a(n) = 7*binomial(2n,n-3)/(n+4).">A000588</a>, <a href="/A000957" title="Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with...">A000957</a>, <a href="/A000984" title="Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.">A000984</a>, <a href="/A001392" title="a(n) = 9*binomial(2n,n-4)/(n+5).">A001392</a>, <a href="/A001453" title="Catalan numbers - 1.">A001453</a>, <a href="/A001791" title="a(n) = binomial coefficient C(2n, n-1).">A001791</a>, <a href="/A002057" title="Fourth convolution of Catalan numbers: a(n) = 4*binomial(2*n+3,n)/(n+4).">A002057</a>, <a href="/A002420" title="Expansion of sqrt(1 - 4*x) in powers of x.">A002420</a>, <a href="/A003046" title="Product of first n Catalan numbers.">A003046</a>, <a href="/A003517" title="Number of permutations of [n+1] with exactly 1 increasing subsequence of length 3.">A003517</a>, <a href="/A003518" title="a(n) = 8*binomial(2*n+1,n-3)/(n+5).">A003518</a>, <a href="/A003519" title="a(n) = 10*C(2n+1, n-4)/(n+6).">A003519</a>, <a href="/A006480" title="De Bruijn's S(3,n): (3n)!/(n!)^3.">A006480</a>, <a href="/A008276" title="Triangle of Stirling numbers of first kind, s(n, n-k+1), n >= 1, 1 <= k <= n. Also triangle T(n,k) giving coefficients in ex...">A008276</a>, <a href="/A008549" title="Number of ways of choosing at most n-1 items from a set of size 2*n+1.">A008549</a>, <a href="/A014137" title="Partial sums of Catalan numbers (A000108).">A014137</a>, <a href="/A014138" title="Partial sums of (Catalan numbers starting 1, 2, 5, ...).">A014138</a>, <a href="/A014140" title="Apply partial sum operator twice to Catalan numbers.">A014140</a>, <a href="/A022553" title="Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n o...">A022553</a> (inv. Eul. trans.), <a href="/A024492" title="Catalan numbers with odd index: a(n) = binomial(4*n+2, 2*n+1)/(2*n+2).">A024492</a>, <a href="/A032357" title="Convolution of Catalan numbers and powers of -1.">A032357</a>, <a href="/A032443" title="a(n) = Sum_{i=0..n} binomial(2*n, i).">A032443</a>, <a href="/A039599" title="Triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).">A039599</a>, <a href="/A048990" title="Catalan numbers with even index (A000108(2*n), n >= 0): a(n) = binomial(4*n, 2*n)/(2*n+1).">A048990</a>, <a href="/A059288" title="a(n) = binomial(2*n,n) mod n.">A059288</a>, <a href="/A068875" title="Expansion of (1 + x*C)*C, where C = (1 - (1 - 4*x)^(1/2))/(2*x) is the g.f. for Catalan numbers, A000108.">A068875</a>, <a href="/A069640" title="Let M_n be the n X n matrix with M_n(i,j)=1/(i+j+1); then a(n)=1/det(M_n).">A069640</a>, <a href="/A086117" title="Denominator of mean deviation of a symmetrical binomial distribution on n elements.">A086117</a>, <a href="/A088327" title="G.f.: exp(Sum_{k>=1} B(x^k)/k), where B(x) = x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + ... = (C(x)-1)/x and C is the g.f. for th...">A088327</a> (Eul. trans.), <a href="/A094216" title="Triangle read by rows giving the coefficients of formulas generating each variety of S1(n,k) (unsigned Stirling numbers of f...">A094216</a>, <a href="/A094638" title="Triangle read by rows: T(n,k) = |s(n,n+1-k)|, where s(n,k) are the signed Stirling numbers of the first kind A008276 (1 <= k...">A094638</a>, <a href="/A094639" title="Partial sums of squares of Catalan numbers (A000108).">A094639</a>, <a href="/A098597" title="Numerator of Catalan(n)/2^(2n+1). Also, numerators of (2n-1)!!/(n+1)!. Odd part of the n-th Catalan number.">A098597</a>, <a href="/A099731" title="This table shows the coefficients of sum formulas of n-th Fibonacci numbers (A000045). The k-th row (k>=1) contains T(i,k) f...">A099731</a>, <a href="/A119822" title="Decimal representation of continued fraction 1, 2, 5, 14, 42, ... (Catalan numbers).">A119822</a>, <a href="/A120304" title="Catalan numbers minus 2.">A120304</a>, <a href="/A124926" title="Triangle read by rows: T(n,k) = binomial(n,k)*r(k), where r(k) are the Riordan numbers (r(k) = A005043(k); 0 <= k <= n).">A124926</a>, <a href="/A129763" title="a(n) = Sum_{k=1..n} binomial(n+k-1, n)^2 / n.">A129763</a>, <a href="/A137697" title="a(n) = x(n) * 2^((n mod 2 - 1)/2), with x(n)=Sum(x(k)*x(n-k-1):0<=k<n), x(0)=SQRT(2).">A137697</a>, <a href="/A154559" title="Triangle read by rows, A007318 * (A129186 * (A001006 * 0^(n-k))).">A154559</a>, <a href="/A161581" title="a(n) = (3n)!/(n!(n+1)!(n+2)!).">A161581</a>, <a href="/A167892" title="a(n) = Sum_{k=1..n} Catalan(k)^2.">A167892</a>, <a href="/A167893" title="a(n) = Sum_{k=1..n} Catalan(k)^3.">A167893</a>, <a href="/A179277" title="A(x) = C(x) * C(x^2) * C(x^4) * C(x^8) *...; C = Catalan, A000108.">A179277</a>, <a href="/A211611" title="a(n) = Sum_{k=1..n-1} C(k)^n, where C(k) is a Catalan number.">A211611</a>, <a href="/A275431" title="Triangle read by rows: T(n,k) = number of ways to insert n pairs of parentheses in k words.">A275431</a> (multisets).</div> <div class=sectline>A row of <a href="/A060854" title="Array T(m,n) read by antidiagonals: T(m,n) (m >= 1, n >= 1) = number of ways to arrange the numbers 1,2,...,m*n in an m X n ...">A060854</a>.</div> <div class=sectline>See <a href="/A001003" title="Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers.">A001003</a>, <a href="/A001190" title="Wedderburn-Etherington numbers: unlabeled binary rooted trees (every node has outdegree 0 or 2) with n endpoints (and 2n-1 n...">A001190</a>, <a href="/A001699" title="Number of binary trees of height n; or products (ways to insert parentheses) of height n when multiplication is non-commutat...">A001699</a>, <a href="/A000081" title="Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).">A000081</a> for other ways to count parentheses.</div> <div class=sectline>Enumerates objects encoded by <a href="/A014486" title="List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and ...">A014486</a>.</div> <div class=sectline>A diagonal of any of the essentially equivalent arrays <a href="/A009766" title="Catalan's triangle T(n,k) (read by rows): each term is the sum of the entries above and to the left, i.e., T(n,k) = Sum_{j=0...">A009766</a>, <a href="/A030237" title="Catalan's triangle with right border removed (n > 0, 0 <= k < n).">A030237</a>, <a href="/A033184" title="Catalan triangle A009766 transposed.">A033184</a>, <a href="/A059365" title="Another version of the Catalan triangle: T(r,s) = binomial(2*r-s-1,r-1) - binomial(2*r-s-1,r), r>=0, 0 <= s <= r.">A059365</a>, <a href="/A099039" title="Riordan array (1,c(-x)), where c(x) = g.f. of Catalan numbers.">A099039</a>, <a href="/A106566" title="Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 1, 1, 1, 1, 1, 1, 1, ... ] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ... ] whe...">A106566</a>, <a href="/A130020" title="Triangle T(n,k), 0<=k<=n, read by rows given by [1,0,0,0,0,0,0,...] DELTA [0,1,1,1,1,1,1,...] where DELTA is the operator de...">A130020</a>, <a href="/A047072" title="Array A read by diagonals: A(h,k)=number of paths consisting of steps from (0,0) to (h,k) such that each step has length 1 d...">A047072</a>.</div> <div class=sectline>Cf. <a href="/A051168" title="Triangular array T(h,k) for 0 <= k <= h read by rows: T(h,k) = number of binary Lyndon words with k ones and h-k zeros.">A051168</a> (diagonal of the square array described).</div> <div class=sectline>Cf. <a href="/A033552" title="Number of partitions into Catalan numbers.">A033552</a>, <a href="/A176137" title="Number of partitions of n into distinct Catalan numbers, cf. A000108.">A176137</a> (partitions into Catalan numbers).</div> <div class=sectline>Cf. <a href="/A000753" title="Boustrophedon transform of Catalan numbers.">A000753</a>, <a href="/A000736" title="Boustrophedon transform of Catalan numbers 1, 1, 1, 2, 5, 14, ...">A000736</a> (Boustrophedon transforms).</div> <div class=sectline>Cf. <a href="/A120303" title="Largest prime factor of Catalan number A000108(n).">A120303</a> (largest prime factor of Catalan number).</div> <div class=sectline>Cf. <a href="/A121839" title="Decimal expansion of Sum_{k>=1} 1/C(k), where C(k) is a Catalan Number (A000108).">A121839</a> (reciprocal Catalan constant), <a href="/A268813" title="Decimal expansion of sum(k>=0, 1/C(k)), where C(k) is a Catalan Number (A000108).">A268813</a>.</div> <div class=sectline>Cf. <a href="/A038003" title="Odd Catalan numbers: a(n) = A000108(2^n-1).">A038003</a>, <a href="/A119861" title="Number of distinct prime factors of the odd Catalan numbers A038003(n).">A119861</a>, <a href="/A119908" title="Largest squared prime factor of the odd Catalan number (A038003(n)) or 1, if it is squarefree.">A119908</a>, <a href="/A120274" title="Largest prime factor of the odd Catalan number A038003(n).">A120274</a>, <a href="/A120275" title="Smallest prime factor of the odd Catalan number A038003(n).">A120275</a> (odd Catalan number).</div> <div class=sectline>Cf. <a href="/A002390" title="Decimal expansion of natural logarithm of golden ratio.">A002390</a> (decimal expansion of natural logarithm of golden ratio).</div> <div class=sectline>Coefficients of square root of the g.f. are <a href="/A001795" title="Coefficients of Legendre polynomials.">A001795</a>/<a href="/A046161" title="a(n) = denominator of binomial(2n,n)/4^n.">A046161</a>.</div> <div class=sectline>For a(n) mod 6 see <a href="/A259667" title="Catalan numbers mod 6.">A259667</a>.</div> <div class=sectline>For a(n) in base 2 see <a href="/A264663" title="Catalan numbers written in base 2.">A264663</a>.</div> <div class=sectline>Hankel transforms with first terms omitted: <a href="/A001477" title="The nonnegative integers.">A001477</a>, <a href="/A006858" title="Expansion of g.f. x*(1 + x)*(1 + 6*x + x^2)/(1 - x)^7.">A006858</a>, <a href="/A091962" title="From enumerating paths in the plane.">A091962</a>, <a href="/A078920" title="Upper triangle of Catalan Number Wall.">A078920</a>, <a href="/A123352" title="Triangle read by rows, giving Kekulé numbers for certain benzenoids (see the Cyvin-Gutman book for details).">A123352</a>, <a href="/A368025" title="Array read by ascending antidiagonals: A(n,k) is the determinant of the n-th order Hankel matrix of Catalan numbers M(n) who...">A368025</a>.</div> <div class=sectline>Cf. <a href="/A001147" title="Double factorial of odd numbers: a(n) = (2*n-1)!! = 1*3*5*...*(2*n-1).">A001147</a>, <a href="/A163960" title="Decimal expansion of 2*(sqrt(2) - 1).">A163960</a>.</div> <div class=sectline>Cf. <a href="/A332602" title="Tridiagonal matrix M read by antidiagonals: main diagonal is 1,2,2,2,2,..., two adjacent diagonals are 1,1,1,1,1,...">A332602</a> (conjectured production matrix).</div> <div class=sectline>Polyominoes: <a href="/A001683" title="Number of one-sided triangulations of the disk; or flexagons of order n; or unlabeled plane trivalent trees (n-2 internal ve...">A001683</a>(n+2) (oriented), <a href="/A000207" title="Number of inequivalent ways of dissecting a regular (n+2)-gon into n triangles by n-1 non-intersecting diagonals under rotat...">A000207</a> (unoriented), <a href="/A369314" title="Number of chiral pairs of polyominoes composed of n triangular cells of the hyperbolic regular tiling with Schläfli symbol ...">A369314</a> (chiral), <a href="/A208355" title="Right edge of the triangle in A208101.">A208355</a>(n-1) (achiral), <a href="/A001764" title="a(n) = binomial(3*n,n)/(2*n+1) (enumerates ternary trees and also noncrossing trees).">A001764</a> {4,oo}.</div> <div class=sectline>Sequence in context: <a href="/A115140" title="O.g.f. inverse of Catalan A000108 o.g.f.">A115140</a> <a href="/A120588" title="G.f. is 1 + x*c(x), where c(x) is the g.f. of the Catalan numbers (A000108).">A120588</a> <a href="/A168491" title="a(n) = (-1)^n*Catalan(n).">A168491</a> * <a href="/A057413" title="Number of staircase polygons of perimeter 2n with any number of (staircase polygon) holes on square lattice (not allowing ro...">A057413</a> <a href="/A126567" title="Sequence generated from the E6 Cartan matrix.">A126567</a> <a href="/A125501" title="The (1,1)-entry in the matrix M^n, where M is the 7 X 7 Cartan matrix [2,-1,0,0,0,0,0; -1,2,-1,0,0,0,0; 0,-1,2,-1,0,0,-1; 0,...">A125501</a></div> <div class=sectline>Adjacent sequences: <a href="/A000105" title="Number of free polyominoes (or square animals) with n cells.">A000105</a> <a href="/A000106" title="2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees.">A000106</a> <a href="/A000107" title="Number of rooted trees with n nodes and a single labeled node; pointed rooted trees; vertebrates.">A000107</a> * <a href="/A000109" title="Number of simplicial polyhedra with n vertices; simple planar graphs with n vertices and 3n-6 edges; maximal simple planar g...">A000109</a> <a href="/A000110" title="Bell or exponential numbers: number of ways to partition a set of n labeled elements.">A000110</a> <a href="/A000111" title="Euler or up/down numbers: e.g.f. sec(x) + tan(x). Also for n >= 2, half the number of alternating permutations on n letters ...">A000111</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="an important sequence">core</span>,<span title="a sequence of nonnegative numbers">nonn</span>,<span title="it is very easy to produce terms of sequence">easy</span>,<span title="an eigensequence: a fixed sequence for some transformation">eigen</span>,<span title="an exceptionally nice sequence">nice</span>,<span title="edited within the last two weeks">changed</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a></div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified December 11 20:18 EST 2024. Contains 378626 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>

CINXE.COM

A000108 - OEIS