Displaying 1-10 of 51 results found.
Decimal expansion of the sum of the reciprocals of triangular polygorials A006472.
+20
1
2, 3, 9, 4, 8, 3, 3, 0, 9, 9, 2, 7, 3, 4, 0, 4, 7, 1, 6, 5, 2, 2, 6, 3, 2, 6, 3, 6, 4, 3, 6, 3, 7, 3, 1, 5, 1, 9, 6, 8, 6, 3, 7, 0, 0, 7, 0, 9, 1, 3, 6, 2, 4, 4, 4, 7, 2, 6, 7, 9, 7, 5, 6, 3, 8, 5, 7, 2, 9, 5, 5, 5, 9, 4, 8, 3, 3, 3, 3, 4, 6, 4, 0, 5, 2, 4, 5, 5, 9, 4, 9, 9, 7, 1, 2, 3, 1, 5, 0, 7, 8, 9, 2, 5, 2, 2, 3, 6, 9, 3, 1, 1, 0, 3, 7, 8, 4, 9, 6, 1
FORMULA
Equals BesselI(1, 2*sqrt(2))/sqrt(2).
EXAMPLE
2.3948330992734047165226326364363731519686370070913624447267975638...
MATHEMATICA
RealDigits[BesselI[1, 2 Sqrt[2]]/Sqrt[2] 10, 120][[1]]
Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).
(Formerly M1459 N0577)
+10
4053
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
COMMENTS
These were formerly sometimes called Segner numbers.
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.
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))).
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]
Number of noncrossing partitions of the n-set. For example, of the 15 set partitions of the 4-set, only [{13},{24}] is crossing, so there are a(4)=14 noncrossing partitions of 4 elements. - Joerg Arndt, Jul 11 2011 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 A000272. - Joerg Arndt and Greg Stevenson, Jul 11 2011 a(n) is the number of ordered rooted trees with n nodes, not including the root. See the Conway-Guy reference where these rooted ordered trees are called plane bushes. See also the Bergeron et al. reference, Example 4, p. 167. - Wolfdieter Lang, Aug 07 2007 As shown in the paper from Beineke and Pippert (1971), a(n-2)=D(n) is the number of labeled dissections of a disk, related to the number R(n)= A001761(n-2) of labeled planar 2-trees having n vertices and rooted at a given exterior edge, by the formula D(n)=R(n)/(n-2)!. - M. F. Hasler, Feb 22 2012 Shifts one place left when convolved with itself.
For n >= 1, a(n) is also the number of rooted bicolored unicellular maps of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 15 2001
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) = A001147(n).) Arises in Schubert calculus - see Sottile reference.
Inverse Euler transform of sequence is A022553. With interpolated zeros, the inverse binomial transform of the Motzkin numbers A001006. - Paul Barry, Jul 18 2003 The Hankel transforms of this sequence or of this sequence with the first term omitted give A000012 = 1, 1, 1, 1, 1, 1, ...; example: Det([1, 1, 2, 5; 1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132]) = 1 and Det([1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132; 14, 42, 132, 429]) = 1. - Philippe Deléham, Mar 04 2004 a(n) equals the sum of squares of terms in row n of triangle A053121, which is formed from successive self-convolutions of the Catalan sequence. - Paul D. Hanna, Apr 23 2005 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
The multiplicity with which a prime p divides C_n can be determined by first expressing n+1 in base p. For p=2, the multiplicity is the number of 1 digits minus 1. For p an odd prime, count all digits greater than (p+1)/2; also count digits equal to (p+1)/2 unless final; and count digits equal to (p-1)/2 if not final and the next digit is counted. For example, n=62, n+1 = 223_5, so C_62 is not divisible by 5. n=63, n+1 = 224_5, so 5^3 | C_63. - Franklin T. Adams-Watters, Feb 08 2006 Koshy and Salmassi give an elementary proof that the only prime Catalan numbers are a(2) = 2 and a(3) = 5. Is the only semiprime Catalan number a(4) = 14? - Jonathan Vos Post, Mar 06 2006 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. - Franklin T. Adams-Watters, Apr 14 2006 The number of ways to place n indistinguishable balls in n numbered boxes B1,...,Bn such that at most a total of k balls are placed in boxes B1,...,Bk for k=1,...,n. For example, a(3)=5 since there are 5 ways to distribute 3 balls among 3 boxes such that (i) box 1 gets at most 1 ball and (ii) box 1 and box 2 together get at most 2 balls:(O)(O)(O), (O)()(OO), ()(OO)(O), ()(O)(OO), ()()(OOO). - Dennis P. Walsh, Dec 04 2006 a(n) is also the order of the semigroup of order-decreasing and order-preserving full transformations (of an n-element chain) - now known as the Catalan monoid. - Abdullahi Umar, Aug 25 2008 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
Limit_{n->oo} a(n)/a(n-1) = 4. - Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008
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
Starting with offset 1 = A068875: (1, 2, 4, 10, 18, 84, ...) convolved with Fine numbers, A000957: (1, 0, 1, 2, 6, 18, ...). a(6) = 132 = (1, 2, 4, 10, 28, 84) dot (18, 6, 2, 1, 0, 1) = (18 + 12 + 8 + 10 + 0 + 84) = 132. - Gary W. Adamson, May 01 2009 Convolved with A032443: (1, 3, 11, 42, 163, ...) = powers of 4, A000302: (1, 4, 16, ...). - Gary W. Adamson, May 15 2009 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. - Geoffrey Critzer, Sep 12 2009 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). - Groux Roland, Nov 13 2009 Leonhard Euler used the formula C(n) = Product_{i=3..n} (4*i-10)/(i-1) in his 'Betrachtungen, auf wie vielerley Arten ein gegebenes polygonum durch Diagonallinien in triangula zerschnitten werden könne' and computes by recursion C(n+2) for n = 1..8. (Berlin, 4th September 1751, in a letter to Goldbach.) - Peter Luschny, Mar 13 2010 a(n) is also the number of quivers in the mutation class of type B_n or of type C_n. - Christian Stump, Nov 02 2010 Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color while satisfying the following conditions: 1. No two colors are chosen the same positive number of times. 2. For any two colors (c, d) that are chosen at least once, color c is chosen more times than color d iff color c appears more times in the original set than color d. If the second requirement is lifted, the number of acceptable ways equals A000110(n+1). See related comments for A016098, A085082. (End) Deutsch and Sagan prove the Catalan number C_n is odd if and only if n = 2^a - 1 for some nonnegative integer a. Lin proves for every odd Catalan number C_n, we have C_n == 1 (mod 4). - Jonathan Vos Post, Dec 09 2010 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). - Geoffrey Critzer, Dec 16 2010 Postnikov (2005) defines "generalized Catalan numbers" associated with buildings (e.g., Catalan numbers of Type B, see A000984). - N. J. A. Sloane, Dec 10 2011 Number of permutations in S(n) for which length equals depth. - Bridget Tenner, Feb 22 2012 a(n) is the number of binary sequences of length 2n+1 in which the number of ones first exceed the number of zeros at entry 2n+1. See the example below in the example section. - Dennis P. Walsh, Apr 11 2012 Number of binary necklaces of length 2*n+1 containing n 1's (or, by symmetry, 0's). All these are Lyndon words and their representatives (as cyclic maxima) are the binary Dyck words. - Joerg Arndt, Nov 12 2012 Number of sequences consisting of n 'x' letters and n 'y' letters such that (counting from the left) the 'x' count >= 'y' count. For example, for n=3 we have xxxyyy, xxyxyy, xxyyxy, xyxxyy and xyxyxy. - Jon Perry, Nov 16 2012 a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps come in 2 colors. Example: a(4)=14 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 8 paths of shape HHH, 2 paths of shape UHD, 2 paths of shape UDH, and 2 paths of shape HUD. - José Luis Ramírez Ramírez, Jan 16 2013 If p is an odd prime, then (-1)^((p-1)/2)*a((p-1)/2) mod p = 2. - Gary Detlefs, Feb 20 2013 Conjecture: For any positive integer n, the polynomial Sum_{k=0..n} a(k)*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013 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. - Bob Selcoe, Nov 16 2013 [Corrected by Jianing Song, May 21 2021] No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02 2013 Prime p divides a((p+1)/2) for p > 3. See A120303(n) = Largest prime factor of Catalan number. Reciprocal Catalan Constant C = 1 + 4*sqrt(3)*Pi/27 = 1.80613.. = A121839. Log(Phi) = (125*C - 55) / (24*sqrt(5)), where C = Sum_{k>=1} (-1)^(k+1)*1/a(k). See A002390 = Decimal expansion of natural logarithm of golden ratio. 3-d analog of the Catalan numbers: (3n)!/(n!(n+1)!(n+2)!) = A161581(n) = A006480(n) / ((n+1)^2*(n+2)), where A006480(n) = (3n)!/(n!)^3 De Bruijn's S(3,n). (End) For a relation to the inviscid Burgers's, or Hopf, equation, see A001764. - Tom Copeland, Feb 15 2014 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.
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).
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.
(End)
Number of sequences [s(0), s(1), ..., s(n)] with s(n)=0, Sum_{j=0..n} s(j) = n, and Sum_{j=0..k} s(j)-1 >= 0 for k < n-1 (and necessarily Sum_{j=0..n-1} s(j)-1 = 0). These are the branching sequences of the (ordered) trees with n non-root nodes, see example. - Joerg Arndt, Jun 30 2014 Number of stack-sortable permutations of [n], these are the 231-avoiding permutations; see the Bousquet-Mélou reference. - Joerg Arndt, Jul 01 2014 a(n) is the number of increasing strict binary trees with 2n-1 nodes that avoid 132. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 07 2014 In a one-dimensional medium with elastic scattering (zig-zag walk), first recurrence after 2n+1 scattering events has the probability C(n)/2^(2n+1). - Joachim Wuttke, Sep 11 2014 The o.g.f. C(x) = (1 - sqrt(1-4x))/2, for the Catalan numbers, with comp. inverse Cinv(x) = x*(1-x) and the functions P(x) = x / (1 + t*x) and its inverse Pinv(x,t) = -P(-x,t) = x / (1 - t*x) form a group under composition that generates or interpolates among many classic arrays, such as the Motzkin (Riordan, A005043), Fibonacci ( A000045), and Fine ( A000957) numbers and polynomials ( A030528), and enumerating arrays for Motzkin, Dyck, and Łukasiewicz lattice paths and different types of trees and non-crossing partitions ( A091867, connected to sums of the refined Narayana numbers A134264). - Tom Copeland, Nov 04 2014 Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015 The Catalan number series A000108(n+3), offset n=0, gives Hankel transform revealing the square pyramidal numbers starting at 5, A000330(n+2), offset n=0 (empirical observation). - Tony Foster III, Sep 05 2016 Hankel transforms of the Catalan numbers with the first 2, 4, and 5 terms omitted give A001477, A006858, and A091962, 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 A078920/ A123352/ A368025. - Andrey Zabolotskiy, Oct 13 2016 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. - N. J. A. Sloane, Feb 09 2017 Coefficients of the generating series associated to the Magmatic and Dendriform operadic algebras. Cf. p. 422 and 435 of the Loday et al. paper. - Tom Copeland, Jul 08 2018 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). - Tony Foster III, Aug 30 2018 Also the number of Catalan trees, or planted plane trees (Bona, 2015, p. 299, Theorem 4.6.3). - N. J. A. Sloane, Dec 25 2018 Number of coalescent histories for a caterpillar species tree and a matching caterpillar gene tree with n+1 leaves (Rosenberg 2007, Corollary 3.5). - Noah A Rosenberg, Jan 28 2019 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). - Derek Orr, Mar 15 2019 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)/ A098597(n), where b is the 0-offset sequence with the terms of A120777 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)/ A098597(5). - Rick L. Shepherd, Sep 02 2019 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). - Charles R Greathouse IV, Sep 28 2019 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.) - Tom Copeland, Nov 17 2019 Number of permutations in S_n whose principal order ideals in the weak order are modular lattices. - Bridget Tenner, Jan 16 2020 Number of permutations in S_n whose principal order ideals in the weak order are distributive lattices. - Bridget Tenner, Jan 16 2020 Legendre gives the following formula for computing the square root modulo 2^m:
sqrt(1 + 8*a) mod 2^m = (1 + 4*a*Sum_{i=0..m-4} C(i)*(-2*a)^i) mod 2^m
as cited by L. D. Dickson, History of the Theory of Numbers, Vol. 1, 207-208. - Peter Schorn, Feb 11 2020 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. - Kai Zheng, Aug 28 2020 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. - Yuchun Ji, Jan 18 2021 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). - Amiram Eldar, Apr 15 2021 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 A001190 for the case where multiplication is commutative. - Jianing Song, Apr 29 2022 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. - Andrea Arlette España, Nov 06 2022 a(n) is the number of 132-avoiding stabilized-interval-free permutations of size n+1. - Juan B. Gil, Jun 22 2023 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. - Robert A. Russell, Jan 27 2024 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) - Bridget Tenner, Apr 16 2024
REFERENCES
The large number of references and links demonstrates the ubiquity of the Catalan numbers.
R. Alter, Some remarks and results on Catalan numbers, pp. 109-132 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 2, edited R. C. Mullin et al., 1971.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, many references.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 53.
J. H. Conway and R. K. Guy, The Book of Numbers, New York: Springer-Verlag, 1995, ch. 4, pp. 96-106.
S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see pp. 183, 196, etc.).
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.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 167-202, 1999.
E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001.
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.
Tomislav Doslic and Darko Veljan, Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182-2212. MR2404544 (2009j:05019)
S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105.
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.
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)
I. M. H. Etherington, Non-associate powers and a functional equation. The Mathematical Gazette, 21 (1937): 36-39; addendum 21 (1937), 153.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
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.
K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167.
Susanna Fishel, Myrto Kallipoliti and Eleni Tzanaki, Facets of the Generalized Cluster Complex and Regions in the Extended Catalan Arrangement of Type A, The electronic Journal of Combinatorics 20(4) (2013), #P7.
D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.
H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.
Fürlinger, J.; Hofbauer, J., q-Catalan numbers. J. Combin. Theory Ser. A 40 (1985), no. 2, 248-264. MR0814413 (87e:05017)
M. Gardner, Time Travel and Other Mathematical Bewilderments, Chap. 20 pp. 253-266, W. H. Freeman NY 1988.
James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).
M. C. Golumbic and A. N. Trenk, Tolerance graphs, Vol. 89, Cambridge University Press, 2004, pp. 32.
S Goodenough, C Lavault, Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups, The Electronic Journal of Combinatorics, 22(4) (2015), #P4.16,
H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.
D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.
M. Griffiths, The Backbone of Pascal's Triangle, United Kingdom Mathematics Trust (2008), 53-63 and 85-93.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 530.
N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876.
Peter Hajnal and Gabor V. Nagy, A bijective proof of Shapiro's Catalan convolution, Elect. J. Combin., 21 (2014), #P2.42.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.23).
F. Harary, G. Prins, and W. T. Tutte, The number of plane trees. Indag. Math. 26, 319-327, 1964.
J. Harris, Algebraic Geometry: A First Course (GTM 133), Springer-Verlag, 1992, pages 245-247.
S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964.
Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
Higgins, Peter M. Combinatorial results for semigroups of order-preserving mappings. Math. Proc. Camb. Phil. Soc. (1993), 113: 281-296.
B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 513, Eq. (7.282).
F. Hurtado, M. Noy, Ears of triangulations and Catalan numbers, Discrete Mathematics, Volume 149, Issues 1-3, Feb 22 1996, Pages 319-324.
M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.
R. H. Jeurissen, Raney and Catalan, Discrete Math., 308 (2008), 6298-6307.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 36.
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)
Klarner, D. A. A Correspondence Between Sets of Trees. Indag. Math. 31, 292-296, 1969.
M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
D. E. Knuth, The Art of Computer Programming, 2nd Edition, Vol. 1, Addison-Wesley, 1973, pp. 238.
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.6 (p. 450).
Thomas Koshy and Mohammad Salmassi, "Parity and Primality of Catalan Numbers", College Mathematics Journal, Vol. 37, No. 1 (Jan 2006), pp. 52-53.
M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.
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.
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.
P. Lafar and C. T. Long, A combinatorial problem, Amer. Math. Mnthly, 69 (1962), 876-883.
Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200.
P. J. Larcombe, On pre-Catalan Catalan numbers: Kotelnikow (1766), Mathematics Today, 35 (1999), p. 25.
P. J. Larcombe, On the history of the Catalan numbers: a first record in China, Mathematics Today, 35 (1999), p. 89.
P. J. Larcombe, The 18th century Chinese discovery of the Catalan numbers, Math. Spectrum, 32 (1999/2000), 5-7.
P. J. Larcombe and P. D. C. Wilson, On the trail of the Catalan sequence, Mathematics Today, 34 (1998), 114-117.
P. J. Larcombe and P. D. C. Wilson, On the generating function of the Catalan sequence: a historical perspective, Congress. Numer., 149 (2001), 97-108.
G. S. Lueker, Some techniques for solving recurrences, Computing Surveys, 12 (1980), 419-436.
J. J. Luo, Antu Ming, the first inventor of Catalan numbers in the world [in Chinese], Neimenggu Daxue Xuebao, 19 (1998), 239-245.
C. L. Mallows, R. J. Vanderbei, Which Young Tableaux Can Represent an Outer Sum?, Journal of Integer Sequences, Vol. 18, 2015, #15.9.1.
Toufik Mansour, Matthias Schork, and Mark Shattuck, Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979-2991. MR2956089
Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.
M. E. Mays and Jerzy Wojciechowski, A determinant property of Catalan numbers. Discrete Math. 211, No. 1-3, 125-133 (2000). Zbl 0945.05037
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344.
A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.
Miller, Steven J., ed. Benford's Law: Theory and Applications. Princeton University Press, 2015.
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.
C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly, 64 (1957), 143-154.
A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).
Papoulis, Athanasios. "A new method of inversion of the Laplace transform."Quart. Appl. Math 14.405-414 (1957): 124.
S. G. Penrice, Stacks, bracketings and CG-arrangements, Math. Mag., 72 (1999), 321-324.
C. A. Pickover, Wonders of Numbers, Chap. 71, Oxford Univ. Press NY 2000.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.
G. Pólya, On the number of certain lattice polygons. J. Combinatorial Theory 6 1969 102-105. MR0236031 (38 #4329)
C. Pomerance, Divisors of the middle binomial coefficient, Amer. Math. Monthly, 112 (2015), 636-644.
Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
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.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
T. Santiago Costa Oliveira, "Catalan traffic" and integrals on the Grassmannian of lines, Discr. Math., 308 (2007), 148-152.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
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).
L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory, A 20 (1976), 375-376.
L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
L. W. Shapiro, W.-J. Woan and S. Getu, The Catalan numbers via the World Series, Math. Mag., 66 (1993), 20-22.
D. M. Silberger, Occurrences of the integer (2n-2)!/n!(n-1)!, Roczniki Polskiego Towarzystwa Math. 13 (1969): 91-96.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
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.
Solomon, A. Catalan monoids, monoids of local endomorphisms and their presentations. Semigroup Forum 53 (1996), 351-368.
R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, Vol. 2, 1999; see especially Chapter 6.
R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.
Richard P. Stanley, "Catalan Numbers", Cambridge University Press, 2015.
J. J. Sylvester, On reducible cyclodes, Coll. Math. Papers, Vol. 2, see especially page 670, where Catalan numbers appear.
Thiel, Marko. "A new cyclic sieving phenomenon for Catalan objects." Discrete Mathematics 340.3 (2017): 426-429.
I. Vun and P. Belcher, Catalan numbers, Mathematical Spectrum, 30 (1997/1998), 3-5.
D. Wells, Penguin Dictionary of Curious and Interesting Numbers, Entry 42 p 121, Penguin Books, 1987.
D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 41.
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.
LINKS
P. C. Allaart and K. Kawamura, The Takagi function: a survey, Real Analysis Exchange, 37 (2011/12), 1-54; arXiv:1110.1691 [math.CA]. See Section 3.2. 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: math/0611106, 2006-2007. C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, INRIA report 3661, preprint for FPSAC 99, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55. 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 Math. Annalen 191 (1971), 87-98. M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]. Aubrey Blecher, Charlotte Brennan and Arnold Knopfmacher, Water capacity of Dyck paths, Advances in Applied Mathematics (2019) Vol. 112, 101945. M. Bousquet-Mélou and Gilles Schaeffer, Walks on the slit plane, Probability Theory and Related Fields, Vol. 124, no. 3 (2002), 305-344. David Callan and Emeric Deutsch, The Run Transform, Discrete Math. 312 (2012), no. 19, 2927-2937, arXiv:1112.3639 [math.CO], 2011. Peter J. Cameron, Some treelike objects, The Quarterly Journal of Mathematics, Vol. 38, No. 2 (1987), 155-183. See pp. 155, 162. A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff. Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seqs., Vol. 6, 2003. Kai Lai Chung and W. Feller, On Fluctuations in Coin-Tossing, Proceedings of the National Academy of Sciences of the United States of America, Vol. 35, No. 10 (1949), 605-608. Laura Colmenarejo, Aleyah Dawkins, Jennifer Elder, Pamela E. Harris, Kimberly J. Harry, Selvi Kara, Dorian Smith, and Bridget Eileen Tenner, On the lucky and displacement statistics of Stirling permutations, arXiv:2403.03280 [math.CO], 2024. Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8. I. M. H. Etherington, Some problems of non-associative combinations (I), 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. S. Gilliand, C. Johnson, S. Rush, D. Wood, The sock matching problem, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 691-697. F. Harary & R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy) G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy] Colin L. Mallows and Lou Shapiro, Balls on the Lawn, J. Integer Sequences, Vol. 2, 1999, #5. D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printerDiscrete Applied Mathematics, 144 (2004), 359-373; FUN with algorithm'01, Isola d'Elba, 2001. R. J. Nowakowski, G. Renault, E. Lamoureux, S. Mellon and T. Miller, The Game of timber!, 2013. C. D. Olds (Proposer) and H. W. Becker (Discussion), Problem 4277, Amer. Math. Monthly 56 (1949), 697-699. [Annotated scanned copy] Vincent Pilaud, Pebble trees, arXiv:2205.06686 [math.CO], 2022. L. W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976), no. 1, 83-90. [Annotated scanned copy] P. J. Stockmeyer, The charm bracelet problem and its applications, 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] Eric Weisstein's World of Mathematics, Dyck Path.
FORMULA
a(n) = binomial(2*n, n)/(n+1) = (2*n)!/(n!*(n+1)!) = A000984(n)/(n+1). Recurrence: a(n) = 2*(2*n-1)*a(n-1)/(n+1) with a(0) = 1.
Recurrence: a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).
G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x), and satisfies A(x) = 1 + x*A(x)^2.
a(n) = Product_{k=2..n} (1 + n/k).
a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i). - Touchard
It is known that a(n) is odd if and only if n=2^k-1, k=0, 1, 2, 3, ... - Emeric Deutsch, Aug 04 2002, corrected by M. F. Hasler, Nov 08 2015 Using the Stirling approximation in A000142 we get the asymptotic expansion a(n) ~ 4^n / (sqrt(Pi * n) * (n + 1)). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 13 2001 Integral representation: a(n) = (1/(2*Pi))*Integral_{x=0..4} x^n*sqrt((4-x)/x). - Karol A. Penson, Apr 12 2001 E.g.f.: exp(2*x)*(I_0(2*x)-I_1(2*x)), where I_n is Bessel function. - Karol A. Penson, Oct 07 2001 a(n) = polygorial(n, 6)/polygorial(n, 3). - Daniel Dockery (peritus(AT)gmail.com), Jun 24 2003
G.f. A(x) satisfies ((A(x) + A(-x)) / 2)^2 = A(4*x^2). - Michael Somos, Jun 27, 2003 G.f. A(x) satisfies Sum_{k>=1} k(A(x)-1)^k = Sum_{n>=1} 4^{n-1}*x^n. - Shapiro, Woan, Getu
a(n+1) = (1/(n+1))*Sum_{k=0..n} a(n-k)*binomial(2k+1, k+1). - Philippe Deléham, Jan 24 2004 a(n) = Sum_{k=0..n} (-1)^k*2^(n-k)*binomial(n, k)*binomial(k, floor(k/2)). - Paul Barry, Jan 27 2005 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} A053121(n, k)^2, for n >= 0. - Paul D. Hanna, Apr 23 2005 E.g.f. Sum_{n>=0} a(n) * x^(2*n) / (2*n)! = BesselI(1, 2*x) / x. - Michael Somos, Jun 22 2005 Given g.f. A(x), then B(x) = x * A(x^3) satisfies 0 = f(x, B(X)) where f(u, v) = u - v + (u*v)^2 or B(x) = x + (x * B(x))^2 which implies B(-B(x)) = -x and also (1 + B^3) / B^2 = (1 - x^3) / x^2. - Michael Somos, Jun 27 2005 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].
Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example, the present sequence is Phi([1]) (also Phi([1,1])). - Gary W. Adamson, Oct 27 2008 a(n) = Sum_{l_1=0..n+1} Sum_{l_2=0..n}...Sum_{l_i=0..n-i}...Sum_{l_n=0..1} delta(l_1,l_2,...,l_i,...,l_n) where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i < l_(i+1) and l_(i+1) <> 0 for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009 Let A(x) be the g.f., then B(x)=x*A(x) satisfies the differential equation B'(x)-2*B'(x)*B(x)-1=0. - Vladimir Kruchinin, Jan 18 2011 G.f.: 1/(1-x/(1-x/(1-x/(...)))) (continued fraction). - Joerg Arndt, Mar 18 2011 With F(x) = (1-2*x-sqrt(1-4*x))/(2*x) an o.g.f. in x for the Catalan series, G(x) = x/(1+x)^2 is the compositional inverse of F (nulling the n=0 term). - Tom Copeland, Sep 04 2011 With H(x) = 1/(dG(x)/dx) = (1+x)^3 / (1-x), the n-th Catalan number is given by (1/n!)*((H(x)*d/dx)^n)x evaluated at x=0, i.e., F(x) = exp(x*H(u)*d/du)u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)), and H(x) is the o.g.f. for A115291. - Tom Copeland, Sep 04 2011 With F(x) = (1-sqrt(1-4*x))/2 an o.g.f. in x for the Catalan series, G(x)= x*(1-x) is the compositional inverse and this relates the Catalan numbers to the row sums of A125181. 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)
G.f.: (1-sqrt(1-4*x))/(2*x) = G(0) where G(k) = 1 + (4*k+1)*x/(k+1-2*x*(k+1)*(4*k+3)/(2*x*(4*k+3)+(2*k+3)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 30 2011 E.g.f.: exp(2*x)*(BesselI(0,2*x) - BesselI(1,2*x)) = G(0) where G(k) = 1 + (4*k+1)*x/((k+1)*(2*k+1)-x*(k+1)*(2*k+1)*(4*k+3)/(x*(4*k+3)+(k+1)*(2*k+3)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 30 2011 E.g.f.: Hypergeometric([1/2],[2],4*x) which coincides with the e.g.f. given just above, and also by Karol A. Penson further above. - Wolfdieter Lang, Jan 13 2012 G.f.: 1 + 2*x/(U(0)-2*x) where U(k) = k*(4*x+1) + 2*x + 2 - x*(2*k+3)*(2*k+4)/U(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 20 2012 G.f.: hypergeom([1/2,1],[2],4*x). - Joerg Arndt, Apr 06 2013 Special values of Jacobi polynomials, in Maple notation: a(n) = 4^n*JacobiP(n,1,-1/2-n,-1)/(n+1). - Karol A. Penson, Jul 28 2013 a(n-1) = Sum_{t1+2*t2+...+n*tn=n} (-1)^(1+t1+t2+...+tn)*multinomial(t1+t2 +...+tn,t1,t2,...,tn)*a(1)^t1*a(2)^t2*...*a(n)^tn. - Mircea Merca, Feb 27 2014 a(n) = -2^(2*n+1) * binomial(n-1/2, -3/2). - Peter Luschny, May 06 2014 a(n) = (2*n)!*[x^(2*n)]hypergeom([],[2],x^2). - Peter Luschny, Jan 31 2015 a(n) = 4^(n-1)*hypergeom([3/2, 1-n], [3], 1). - Peter Luschny, Feb 03 2015 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. - Michel Marcus, Oct 06 2015 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. - Peter Luschny, Oct 14 2015 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. - David Pasino, Jun 29 2016 Sum_{n>=0} (-1)^n/a(n) = 14/25 - 24*arccsch(2)/(25*sqrt(5)) = 14/25 - 24* A002390/(25*sqrt(5)) = 0.353403708337278061333... - Ilya Gutkovskiy, Jun 30 2016 C(n) = (1/n) * Sum_{i+j+k=n-1} C(i)*C(j)*C(k)*(k+1), n >= 1. - Yuchun Ji, Feb 21 2016 C(n) = 1 + Sum_{i+j+k<n-1} C(i)*C(j)*C(k). - Yuchun Ji, Sep 01 2016 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. - R. J. Mathar, Nov 17 2018 (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)
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. - Yuchun Ji, Sep 27 2020 a(n) = 4^n * (-1)^(n+1) * 3F2[{n + 1,n + 1/2,n}, {3/2,1}, -1], n >= 1. - Sergii Voloshyn, Oct 22 2020 a(n) = 2^(1 + 2 n) * (-1)^(n)/(1 + n) * 3F2[{n, 1/2 + n, 1 + n}, {1/2, 1}, -1], n >= 1. - Sergii Voloshyn, Nov 08 2020 a(n) = (1/Pi)*4^(n+1)*Integral_{x=0..Pi/2} cos(x)^(2*n)*sin(x)^2 dx. - Greg Dresden, May 30 2021 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.
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)
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. - Michael Somos, Dec 12 2022 G.f.: (offset 1) 1/G(x), with G(x) = 1 - 2*x - x^2/G(x) (Jacobi continued fraction). - Nikolaos Pantelidis, Feb 01 2023 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). - Vladislav Shubin, Aug 17 2023 The g.f. A(x) satisfies the following functional equations:
A(x) = 1 + x/(1 - 4*x) * A(-x/(1 - 4*x))^2,
A(x^2) = 1/(1 - 2*x) * A(- x/(1 - 2*x))^2 and, for arbitrary k,
1/(1 - k*x) * A(x/(1 - k*x))^2 = 1/(1 - (k+4)*x) * A(-x/(1 - (k+4)*x))^2. (End)
EXAMPLE
From Joerg Arndt and Greg Stevenson, Jul 11 2011: (Start) The following products of 3 transpositions lead to a 4-cycle in S_4:
(1,2)*(1,3)*(1,4);
(1,2)*(1,4)*(3,4);
(1,3)*(1,4)*(2,3);
(1,4)*(2,3)*(2,4);
(1,4)*(2,4)*(3,4). (End)
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + ...
For n=3, a(3)=5 since there are exactly 5 binary sequences of length 7 in which the number of ones first exceed the number of zeros at entry 7, namely, 0001111, 0010111, 0011011, 0100111, and 0101011. - Dennis P. Walsh, Apr 11 2012 The a(4) = 14 branching sequences of the (ordered) trees with 4 non-root nodes are (dots denote zeros):
01: [ 1 1 1 1 . ]
02: [ 1 1 2 . . ]
03: [ 1 2 . 1 . ]
04: [ 1 2 1 . . ]
05: [ 1 3 . . . ]
06: [ 2 . 1 1 . ]
07: [ 2 . 2 . . ]
08: [ 2 1 . 1 . ]
09: [ 2 1 1 . . ]
10: [ 2 2 . . . ]
11: [ 3 . . 1 . ]
12: [ 3 . 1 . . ]
13: [ 3 1 . . . ]
14: [ 4 . . . . ]
(End)
MAPLE
A000108 := n->binomial(2*n, n)/(n+1);
G000108 := (1 - sqrt(1 - 4*x)) / (2*x);
spec := [ A, {A=Prod(Z, Sequence(A))}, unlabeled ]: [ seq(combstruct[count](spec, size=n+1), n=0..42) ];
with(combstruct): bin := {B=Union(Z, Prod(B, B))}: seq(count([B, bin, unlabeled], size=n+1), n=0..25); # Zerinvary Lajos, Dec 05 2007 gser := series(G000108, x=0, 42): seq(coeff(gser, x, n), n=0..41); # Zerinvary Lajos, May 21 2008 seq((2*n)!*coeff(series(hypergeom([], [2], x^2), x, 2*n+2), x, 2*n), n=0..30); # Peter Luschny, Jan 31 2015 A000108List := proc(m) local A, P, n; A := [1, 1]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), A[-1]]);
A := [op(A), P[-1]] od; A end: A000108List(31); # Peter Luschny, Mar 24 2022
MATHEMATICA
Table[(2 n)!/n!/(n + 1)!, {n, 0, 20}]
Table[4^n Gamma[n + 1/2]/(Sqrt[Pi] Gamma[n + 2]), {n, 0, 20}] (* Eric W. Weisstein, Oct 31 2024 *) CoefficientList[InverseSeries[Series[x/Sum[x^n, {n, 0, 31}], {x, 0, 31}]]/x, x] (* Mats Granvik, Nov 24 2013 *) CoefficientList[Series[(1 - Sqrt[1 - 4 x])/(2 x), {x, 0, 20}], x] (* Stefano Spezia, Aug 31 2018 *)
PROG
(PARI) a(n)=binomial(2*n, n)/(n+1) \\ M. F. Hasler, Aug 25 2012 (PARI) a(n) = (2*n)! / n! / (n+1)!
(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));
(PARI) {a(n) = if( n<1, n==0, polcoeff( serreverse( x / (1 + x)^2 + x * O(x^n)), n))}; /* Michael Somos */ (PARI) (recur(a, b)=if(b<=2, (a==2)+(a==b)+(a!=b)*(1+a/2), (1+a/b)*recur(a, b-1))); a(n)=recur(n, n); \\ R. J. Cano, Nov 22 2012 (PARI) x='x+O('x^40); Vec((1-sqrt(1-4*x))/(2*x)) \\ Altug Alkan, Oct 13 2015 (MuPAD) combinat::dyckWords::count(n) $ n = 0..38 // Zerinvary Lajos, Apr 14 2007 (Magma) C:= func< n | Binomial(2*n, n)/(n+1) >; [ C(n) : n in [0..60]];
(Haskell)
import Data.List (genericIndex)
a000108 n = genericIndex a000108_list n
a000108_list = 1 : catalan [1] where
catalan cs = c : catalan (c:cs) where
c = sum $ zipWith (*) cs $ reverse cs
a000108 = map last $ iterate (scanl1 (+) . (++ [0])) [1]
(Sage) [catalan_number(i) for i in range(27)] # Zerinvary Lajos, Jun 26 2008 (Sage) # Generalized algorithm of L. Seidel
D = [0]*(n+1); D[1] = 1
b = True; h = 1; R = []
for i in range(2*n-1) :
if b :
for k in range(h, 0, -1) : D[k] += D[k-1]
h += 1; R.append(D[1])
else :
for k in range(1, h, 1) : D[k] += D[k+1]
b = not b
return R
(Python)
from gmpy2 import divexact
for n in range(1, 10**3):
(Python)
# Works in Sage also.
for n in range(1000):
CROSSREFS
Cf. A000142, A000245, A000344, A000588, A000957, A000984, A001392, A001453, A001791, A002057, A002420, A003046, A003517, A003518, A003519, A006480, A008276, A008549, A014137, A014138, A014140, A022553 (inv. Eul. trans.), A024492, A032357, A032443, A039599, A048990, A059288, A068875, A069640, A086117, A088327 (Eul. trans.), A094216, A094638, A094639, A098597, A099731, A119822, A120304, A124926, A129763, A137697, A154559, A161581, A167892, A167893, A179277, A211611, A275431 (multisets). Enumerates objects encoded by A014486. Cf. A051168 (diagonal of the square array described). Cf. A120303 (largest prime factor of Catalan number). Cf. A002390 (decimal expansion of natural logarithm of golden ratio). Cf. A332602 (conjectured production matrix).
KEYWORD
core,nonn,easy,eigen,nice,changed
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 ( A001250).
(Formerly M1492 N0587)
+10
336
1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981, 1903757312, 19391512145, 209865342976, 2404879675441, 29088885112832, 370371188237525, 4951498053124096, 69348874393137901, 1015423886506852352, 15514534163557086905, 246921480190207983616, 4087072509293123892361
COMMENTS
Number of linear extensions of the "zig-zag" poset. See ch. 3, prob. 23 of Stanley. - Mitch Harris, Dec 27 2005 Number of increasing 0-1-2 trees on n vertices. - David Callan, Dec 22 2006 Also the number of refinements of partitions. - Heinz-Richard Halder (halder.bichl(AT)t-online.de), Mar 07 2008
The ratio a(n)/n! is also the probability that n numbers x1,x2,...,xn randomly chosen uniformly and independently in [0,1] satisfy x1 > x2 < x3 > x4 < ... xn. - Pietro Majer, Jul 13 2009 For n >= 2, a(n-2) = number of permutations w of an ordered n-set {x_1 < ... x_n} with the following properties: w(1) = x_n, w(n) = x_{n-1}, w(2) > w(n-1), and neither any subword of w, nor its reversal, has the first three properties. The count is unchanged if the third condition is replaced with w(2) < w(n-1). - Jeremy L. Martin, Mar 26 2010 A partition of zigzag permutations of order n+1 by the smallest or the largest, whichever is behind. This partition has the same recurrent relation as increasing 1-2 trees of order n, by induction the bijection follows. - Wenjin Woan, May 06 2011 As can be seen from the asymptotics given in the FORMULA section, one has lim_{n->oo} 2*n*a(n-1)/a(n) = Pi; see A132049/ A132050 for the simplified fractions. - M. F. Hasler, Apr 03 2013 M. Josuat-Verges, J.-C. Novelli and J.-Y. Thibon (2011) give a far-reaching generalization of the bijection between Euler numbers and alternating permutations. - N. J. A. Sloane, Jul 09 2015 Number of treeshelves avoiding pattern T321. Treeshelves are ordered binary (0-1-2) increasing trees where every child is connected to its parent by a left or a right link, see A278678 for more definitions and examples. - Sergey Kirgizov, Dec 24 2016 Number of sequences (e(1), ..., e(n-1)), 0 <= e(i) < i, such that no three terms are equal. [Theorem 7 of Corteel, Martinez, Savage, and Weselcouch] - Eric M. Schmidt, Jul 17 2017 Number of self-dual edge-labeled trees with n vertices under "mind-body" duality. Also number of self-dual rooted edge-labeled trees with n vertices. See my paper linked below. - Nikos Apostolakis, Aug 01 2018 The ratio a(n)/n! is the volume of the convex polyhedron defined as the set of (x_1,...,x_n) in [0,1]^n such that x_i + x_{i+1} <= 1 for every 1 <= i <= n-1; see the solutions by Macdonald and Nelsen to the Amer. Math. Monthly problem referenced below. - Sanjay Ramassamy, Nov 02 2018 Number of total cyclic orders on {0,1,...,n} such that the triple (i-1,i,i+1) is positively oriented for every 1 <= i <= n-1; see my paper on cyclic orders linked below. - Sanjay Ramassamy, Nov 02 2018 The number of binary, rooted, unlabeled histories with n+1 leaves (following the definition of Rosenberg 2006). Also termed Tajima trees, Tajima genealogies, or binary, rooted, unlabeled ranked trees (Palacios et al. 2015). See Disanto & Wiehe (2013) for a proof. - Noah A Rosenberg, Mar 10 2019 Also the number of non-isomorphic balanced reduced multisystems with n + 1 distinct atoms and maximum depth. A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem. The labeled version is A006472. For example, non-isomorphic representatives of the a(0) = 1 through a(4) = 5 multisystems are (commas elided): {1} {12} {{1}{23}} {{{1}}{{2}{34}}} {{{{1}}}{{{2}}{{3}{45}}}}
{{{12}}{{3}{4}}} {{{{1}}}{{{23}}{{4}{5}}}}
{{{{1}{2}}}{{{3}}{{45}}}}
{{{{1}{23}}}{{{4}}{{5}}}}
{{{{12}}}{{{3}}{{4}{5}}}}
Also the number of balanced reduced multisystems with n + 1 equal atoms and maximum depth. This is possibly the meaning of Heinz-Richard Halder's comment (see also A002846, A213427, A265947). The non-maximum-depth version is A318813. For example, the a(0) = 1 through a(4) = 5 multisystems are (commas elided): {1} {11} {{1}{11}} {{{1}}{{1}{11}}} {{{{1}}}{{{1}}{{1}{11}}}}
{{{11}}{{1}{1}}} {{{{1}}}{{{11}}{{1}{1}}}}
{{{{1}{1}}}{{{1}}{{11}}}}
{{{{1}{11}}}{{{1}}{{1}}}}
{{{{11}}}{{{1}}{{1}{1}}}}
(End)
With s_n denoting the sum of n independent uniformly random numbers chosen from [-1/2,1/2], the probability that the closest integer to s_n is even is exactly 1/2 + a(n)/(2*n!). (See Hambardzumyan et al. 2023, Appendix B.) - Suhail Sherif, Mar 31 2024 The number of permutations of size n+1 that require exactly n passes through a stack (i.e. have reverse-tier n-1) with an algorithm that prioritizes outputting the maximum possible prefix of the identity in a given pass and reverses the remainder of the permutation for prior to the next pass. - Rebecca Smith, Jun 05 2024
REFERENCES
M. D. Atkinson: Partial orders and comparison problems, Sixteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, (Boca Raton, Feb 1985), Congressus Numerantium 47, 77-88.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 34, 932.
L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 258-260, section #11.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262.
Bishal Deb and Alan D. Sokal, Classical continued fractions for some multivariate polynomials generalizing the Genocchi and median Genocchi numbers, arXiv:2212.07232, Dec 14 2022.
H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY, 1965, p. 66.
O. Heimo and A. Karttunen, Series help-mates in 8, 9 and 10 moves (Problems 2901, 2974-2976), Suomen Tehtavaniekat (Proceedings of the Finnish Chess Problem Society) vol. 60, no. 2/2006, pp. 75, 77.
S. K. Jha, A Congruence for the Number of Alternating Permutations, Missouri J. Math. Sci., 33 (No. 1, 2021), 99-104
L. B. W. Jolley, Summation of Series. 2nd ed., Dover, NY, 1961, p. 238.
S. Mukai, An Introduction to Invariants and Moduli, Cambridge, 2003; see p. 444.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 110.
C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 184.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1997 and Vol. 2, 1999; see Problem 5.7.
LINKS
O. Bodini, M. Dien, X. Fontaine, A. Genitrini and H. K. Hwang, Increasing Diamonds, in LATIN 2016: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings Pages pp 207-219 2016 DOI 10.1007/978-3-662-49529-2_16; Lecture Notes in Computer Science Series Volume 9644. Peter J. Cameron and Liam Stott, Trees and cycles, arXiv:2010.14902 [math.CO], 2020. See p. 12. Sean Cleary, Mareike Fischer, Robert C. Griffiths and Raazesh Sainudiin, Some distributions on finite rooted binary trees, UCDMS Research Report NO. UCDMS2015/2, School of Mathematics and Statistics, University of Canterbury, Christchurch, NZ, 2015. Chandler Davis, Problem 4755, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. [Denoted by P_n in solution.] Chandler Davis, Problem 4755: A Permutation Problem, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. [Denoted by P_n in solution.] [Annotated scanned copy] I. G. Macdonald and R. B. Nelsen (independently), Solution to E2701, Amer. Math. Monthly, 86 (1979), 396. J. Millar, N. J. A. Sloane and N. E. Young, A new operation on sequences: the Boustrophedon transform, J. Combin. Theory, 17A 44-54 1996 ( Abstract, pdf, ps). D. J. Newman, W. Weissblum and others, Problem 67-5: "Up-Down" Permutations, SIAM Review, Vol. 9, No. 1 (Jan., 1967), page 121, Vol. 11, No. 1 (Jan., 1969), p. 75, and Vol. 10, No. 2 (Apr., 1968), pp. 225-226. [ Annotated scanned copy] R. P. Stanley, Queue problems revisited, Suomen Tehtavaniekat (Proceedings of the Finnish Chess Problem Society), vol. 59, no. 4 (2005), 193-203.
FORMULA
E.g.f.: (1+sin(x))/cos(x) = tan(x) + sec(x).
E.g.f. for a(n+1) is 1/(cos(x/2) - sin(x/2))^2 = 1/(1-sin(x)) = d/dx(sec(x) + tan(x)).
O.g.f.: A(x) = 1+x/(1-x-x^2/(1-2*x-3*x^2/(1-3*x-6*x^2/(1-4*x-10*x^2/(1-... -n*x-(n*(n+1)/2)*x^2/(1- ...)))))) (continued fraction). - Paul D. Hanna, Jan 17 2006 E.g.f. A(x) = y satisfies 2y' = 1 + y^2. - Michael Somos, Feb 03 2004 2*a(n+1) = Sum_{k=0..n} binomial(n, k)*a(k)*a(n-k).
Asymptotics: a(n) ~ 2^(n+2)*n!/Pi^(n+1). For a proof, see for example Flajolet and Sedgewick.
a(n) = (n-1)*a(n-1) - Sum_{i=2..n-2} (i-1)*E(n-2, n-1-i), where E are the Entringer numbers A008281. - Jon Perry, Jun 09 2003 a(2*k) = (-1)^k euler(2k) and a(2k-1) = (-1)^(k-1)2^(2k)(2^(2k)-1) Bernoulli(2k)/(2k). - C. Ronaldo (aga_new_ac(AT)hotmail.com), Jan 17 2005
a(n) = 2^n|E(n,1/2) + E(n,1)| where E(n,x) are the Euler polynomials. - Peter Luschny, Jan 25 2009 a(n) = 2^(n+2)*n!*S(n+1)/(Pi)^(n+1), where S(n) = Sum_{k = -inf..inf} 1/(4k+1)^n (see the Elkies reference). - Emeric Deutsch, Aug 17 2009 a(n) = i^(n+1) Sum_{k=1..n+1} Sum_{j=0..k} binomial(k,j)(-1)^j (k-2j)^(n+1) (2i)^(-k) k^{-1}. - Ross Tang (ph.tchaa(AT)gmail.com), Jul 28 2010
a(n) = sum((if evenp(n+k) then (-1)^((n+k)/2)*sum(j!*Stirling2(n,j)*2^(1-j)*(-1)^(n+j-k)*binomial(j-1,k-1),j,k,n) else 0),k,1,n), n>0. - Vladimir Kruchinin, Aug 19 2010 If n==1(mod 4) is prime, then a(n)==1(mod n); if n==3(mod 4) is prime, then a(n)==-1(mod n). - Vladimir Shevelev, Aug 31 2010 For m>=0, a(2^m)==1(mod 2^m); If p is prime, then a(2*p)==1(mod 2*p). - Vladimir Shevelev, Sep 03 2010 a(n) = A(n,i)/(1+i)^(n-1), where i = sqrt(-1) and {A(n,x)}n>=1 = [1,1+x,1+4*x+x^2,1+11*x+11*x^2+x^3,...] denotes the sequence of Eulerian polynomials.
Equivalently, a(n) = i^(n+1)*Sum_{k=1..n} (-1)^k*k!*Stirling2(n,k) * ((1+i)/2)^(k-1) = i^(n+1)*Sum_{k = 1..n} (-1)^k*((1+i)/2)^(k-1)* Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*j^n.
This explicit formula for a(n) can be used to obtain congruence results. For example, for odd prime p, a(p) = (-1)^((p-1)/2) (mod p), as noted by Vladimir Shevelev above. For the corresponding type B results see A001586. For the corresponding results for plane increasing 0-1-2 trees see A080635. For generalized Eulerian, Stirling and Bernoulli numbers associated with the zigzag numbers see A145876, A147315 and A185424, respectively. For a recursive triangle to calculate a(n) see A185414. (End)
a(n) = I^(n+1)*2*Li_{-n}(-I) for n > 0. Li_{s}(z) is the polylogarithm. - Peter Luschny, Jul 29 2011 a(n) = 2*Sum_{m=0..(n-2)/2} 4^m*(Sum_{i=m..(n-1)/2} (i-(n-1)/2)^(n-1)*binomial(n-2*m-1,i-m)*(-1)^(n-i-1)), n > 1, a(0)=1, a(1)=1. - Vladimir Kruchinin, Aug 09 2011 a(n) = D^(n-1)(1/(1-x)) evaluated at x = 0, where D is the operator sqrt(1-x^2)*d/dx. Cf. A006154. a(n) equals the alternating sum of the nonzero elements of row n-1 of A196776. This leads to a combinatorial interpretation for a(n); for example, a(4*n+2) gives the number of ordered set partitions of 4*n+1 into k odd-sized blocks, k = 1 (mod 4), minus the number of ordered set partitions of 4*n+1 into k odd-sized blocks, k = 3 (mod 4). Cf A002017. - Peter Bala, Dec 06 2011 Continued fractions:
E.g.f.: tan(x) + sec(x) = 1 + x/U(0); U(k) = 4k+1-x/(2-x/(4k+3+x/(2+x/U(k+1)))).
E.g.f.: for a(n+1) is E(x) = 1/(1-sin(x)) = 1 + x/(1 - x + x^2/G(0)); G(k) = (2*k+2)*(2*k+3)-x^2+(2*k+2)*(2*k+3)*x^2/G(k+1).
E.g.f.: for a(n+1) is E(x) = 1/(1-sin(x)) = 1/(1 - x/(1 + x^2/G(0))) ; G(k) = 8*k+6-x^2/(1 + (2*k+2)*(2*k+3)/G(k+1)).
E.g.f.: for a(n+1) is E(x) = 1/(1 - sin(x)) = 1/(1 - x*G(0)); G(k) = 1 - x^2/(2*(2*k+1)*(4*k+3) - 2*x^2*(2*k+1)*(4*k+3)/(x^2 - 4*(k+1)*(4*k+5)/G(k+1))).
E.g.f.: for a(n+1) is E(x) = 1/(1 - sin(x)) = 1/(1 - x*G(0)) where G(k)= 1 - x^2/( (2*k+1)*(2*k+3) - (2*k+1)*(2*k+3)^2/(2*k+3 - (2*k+2)/G(k+1))).
E.g.f.: tan(x) + sec(x) = 1 + 2*x/(U(0)-x) where U(k) = 4k+2 - x^2/U(k+1).
E.g.f.: tan(x) + sec(x) = 1 + 2*x/(2*U(0)-x) where U(k) = 4*k+1 - x^2/(16*k+12 - x^2/U(k+1)).
E.g.f.: tan(x) + sec(x) = 4/(2-x*G(0))-1 where G(k) = 1 - x^2/(x^2 - 4*(2*k+1)*(2*k+3)/G(k+1)).
G.f.: 1 + x/Q(0), m=+4, u=x/2, where Q(k) = 1 - 2*u*(2*k+1) - m*u^2*(k+1)*(2*k+1)/(1 - 2*u*(2*k+2) - m*u^2*(k+1)*(2*k+3)/Q(k+1)).
G.f.: conjecture: 1 + T(0)*x/(1-x), where T(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - 2*(1-x*(k+1))*(1-x*(k+2))/T(k+1)).
E.g.f.: 1+ 4*x/(T(0) - 2*x), where T(k) = 4*(2*k+1) - 4*x^2/T(k+1):
E.g.f.: T(0)-1, where T(k) = 2 + x/(4*k+1 - x/(2 - x/( 4*k+3 + x/T(k+1)))). (End)
Asymptotic expansion: 4*(2*n/(Pi*e))^(n+1/2)*exp(1/2+1/(12*n) -1/(360*n^3) + 1/(1260*n^5) - ...). (See the Luschny link.) - Peter Luschny, Jul 14 2015 The e.g.f. A(x) = tan(x) + sec(x) satisfies A''(x) = A(x)*A'(x), hence the recurrence a(0) = 1, a(1) = 1, else a(n) = Sum_{i = 0..n-2} binomial(n-2,i)*a(i)*a(n-1-i).
Note, the same recurrence, but with the initial conditions a(0) = 0 and a(1) = 1, produces the sequence [0,1,0,1,0,4,0,34,0,496,...], an aerated version of A002105. (End) a(n) = abs(2*4^n*(H(((-1)^n - 3)/8, -n) - H(((-1)^n - 7)/8, -n))) where H(z, r) are the generalized harmonic numbers.
a(n) = (-1)^binomial(n + 1, 2)*2^(2*n + 1)*(zeta(-n, 1 + (1/8)*(-7 + (-1)^n)) - zeta(-n, 1 + (1/8)*(-3 + (-1)^n))). (End)
a(n) = i*(i^n*Li_{-n}(-i) - (-i)^n*Li_{-n}(i)), where i is the imaginary unit and Li_{s}(z) is the polylogarithm. - Peter Luschny, Aug 28 2020 a(n) = n!*Re([x^n](1 + I^(n^2 - n)*(2 - 2*I)/(exp(x) + I))). - Peter Luschny, Aug 09 2021
EXAMPLE
G.f. = 1 + x + x^2 + 2*x^3 + 5*x^4 + 16*x^5 + 61*x^6 + 272*x^7 + 1385*x^8 + ...
Sequence starts 1,1,2,5,16,... since possibilities are {}, {A}, {AB}, {ACB, BCA}, {ACBD, ADBC, BCAD, BDAC, CDAB}, {ACBED, ADBEC, ADCEB, AEBDC, AECDB, BCAED, BDAEC, BDCEA, BEADC, BECDA, CDAEB, CDBEA, CEADB, CEBDA, DEACB, DEBCA}, etc. - Henry Bottomley, Jan 17 2001
MAPLE
A000111 := n-> n!*coeff(series(sec(x)+tan(x), x, n+1), x, n);
s := series(sec(x)+tan(x), x, 100): A000111 := n-> n!*coeff(s, x, n); A000111:=n->piecewise(n mod 2=1, (-1)^((n-1)/2)*2^(n+1)*(2^(n+1)-1)*bernoulli(n+1)/(n+1), (-1)^(n/2)*euler(n)):seq( A000111(n), n=0..30); A000111:=proc(n) local k: k:=floor((n+1)/2): if n mod 2=1 then RETURN((-1)^(k-1)*2^(2*k)*(2^(2*k)-1)*bernoulli(2*k)/(2*k)) else RETURN((-1)^k*euler(2*k)) fi: end:seq( A000111(n), n=0..30); (C. Ronaldo)
T := n -> 2^n*abs(euler(n, 1/2)+euler(n, 1)): # Peter Luschny, Jan 25 2009 S := proc(n, k) option remember; if k=0 then RETURN(`if`(n=0, 1, 0)) fi; S(n, k-1)+S(n-1, n-k) end:
a := n -> 2^(n+2)*n!*(sum(1/(4*k+1)^(n+1), k = -infinity..infinity))/Pi^(n+1):
# alternative Maple program:
b:= proc(u, o) option remember;
`if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
end:
a:= n-> b(n, 0):
MATHEMATICA
a[n_] := If[EvenQ[n], Abs[EulerE[n]], Abs[(2^(n+1)*(2^(n+1)-1)*BernoulliB[n+1])/(n+1)]]; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Oct 09 2012, after C. Ronaldo *) ee = Table[ 2^n*EulerE[n, 1] + EulerE[n] - 1, {n, 0, 26}]; Table[ Differences[ee, n] // First // Abs, {n, 0, 26}] (* Jean-François Alcover, Mar 21 2013, after Paul Curtz *) a[ n_] := If[ n < 0, 0, (2 I)^n If[ EvenQ[n], EulerE[n, 1/2], EulerE[n, 0] I]]; (* Michael Somos, Aug 15 2015 *) a[ n_] := If[ n < 1, Boole[n == 0], With[{m = n - 1}, m! SeriesCoefficient[ 1 / (1 - Sin[x]), {x, 0, m}]]]; (* Michael Somos, Aug 15 2015 *) s[0] = 1; s[_] = 0; t[n_, 0] := s[n]; t[n_, k_] := t[n, k] = t[n, k-1] + t[n-1, n-k]; a[n_] := t[n, n]; Array[a, 30, 0](* Jean-François Alcover, Feb 12 2016 *) a[0] := 1; a[1] := 1; a[n_] := a[n] = Sum[Binomial[n - 2, k] a[k] a[n - 1 - k], {k, 0, n - 2}]; Map[a, Range[0, 26]] (* Oliver Seipel, May 24 2024 after Peter Bala *) a[0] := 1; a[1] := 1; a[n_] := a[n] = 1/(n (n-1)) Sum[a[n-1-k] a[k] k, {k, 1, n-1}]; Map[#! a[#]&, Range[0, 26]] (* Oliver Seipel, May 27 2024 *)
PROG
(PARI) {a(n) = if( n<1, n==0, n--; n! * polcoeff( 1 / (1 - sin(x + x * O(x^n))), n))}; \\ Michael Somos, Feb 03 2004 (PARI) {a(n) = local(v=[1], t); if( n<0, 0, for(k=2, n+2, t=0; v = vector(k, i, if( i>1, t+= v[k+1-i]))); v[2])}; \\ Michael Somos, Feb 03 2004 (PARI) {a(n) = local(an); if( n<1, n>=0, an = vector(n+1, m, 1); for( m=2, n, an[m+1] = sum( k=0, m-1, binomial(m-1, k) * an[k+1] * an[m-k]) / 2); an[n+1])}; \\ Michael Somos, Feb 03 2004 (PARI) z='z+O('z^66); egf = (1+sin(z))/cos(z); Vec(serlaplace(egf)) \\ Joerg Arndt, Apr 30 2011 (PARI) A000111(n)={my(k); sum(m=0, n\2, (-1)^m*sum(j=0, k=n+1-2*m, binomial(k, j)*(-1)^j*(k-2*j)^(n+1))/k>>k)} \\ M. F. Hasler, May 19 2012 (Maxima) a(n):=sum((if evenp(n+k) then (-1)^((n+k)/2)*sum(j!*stirling2(n, j)*2^(1-j)*(-1)^(n+j-k)*binomial(j-1, k-1), j, k, n) else 0), k, 1, n); /* Vladimir Kruchinin, Aug 19 2010 */ (Maxima)
a(n):=if n<2 then 1 else 2*sum(4^m*(sum((i-(n-1)/2)^(n-1)*binomial(n-2*m-1, i-m)*(-1)^(n-i-1), i, m, (n-1)/2)), m, 0, (n-2)/2); /* Vladimir Kruchinin, Aug 09 2011 */ (Sage) # Algorithm of L. Seidel (1877)
R = []; A = {-1:0, 0:1}; k = 0; e = 1
for i in (0..n) :
Am = 0; A[k + e] = 0; e = -e
for j in (0..i) : Am += A[k]; A[k] = Am; k += e
R.append(Am)
return R
(Haskell)
a000111 0 = 1
a000111 n = sum $ a008280_row (n - 1)
(Python)
# requires python 3.2 or higher
from itertools import accumulate
for n in range(10**2):
blist = list(reversed(list(accumulate(reversed(blist))))) + [0] if n % 2 else [0]+list(accumulate(blist))
(Python)
from mpmath import *
mp.dps = 150
l = chop(taylor(lambda x: sec(x) + tan(x), 0, 26))
[int(fac(i) * li) for i, li in enumerate(l)] # Indranil Ghosh, Jul 06 2017
CROSSREFS
Cf. A181937 for n-alternating permutations. Cf. A109449 for an extension to an exponential Riordan array. For 0-1-2 trees with n nodes and k leaves, see A301344. Matula-Goebel numbers of 0-1-2 trees are A292050. An overview over generalized Euler numbers gives A349264.
KEYWORD
nonn,core,eigen,nice,easy,changed
Number of ultradissimilarity relations on an n-set.
(Formerly M3649)
+10
47
1, 1, 4, 32, 436, 9012, 262760, 10270696, 518277560, 32795928016, 2542945605432, 237106822506952, 26173354092593696, 3375693096567983232, 502995942483693043200, 85750135569136650473360, 16583651916595710735271248, 3611157196483089769387182064, 879518067472225603327860638128
COMMENTS
Number of chains from minimum to maximum in the lattice of set partitions of {1, ..., n} ordered by refinement. - Gus Wiseman, Jul 22 2018
REFERENCES
L. Babai and T. Lengyel, A convergence criterion for recurrent sequences with application to the partition lattice, Analysis 12 (1992), 109-119.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 316-321.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
a(n) = Sum_{i=1..n-1} N_i(n), where N_k(m) = Sum_{j=k..m-1} Stirling2(m, j)*N_{k-1}(j), m=3..n, k=2..m-1; N_1(2)=N_1(3)=...=N_1(n)=1.
a(n) = Sum_{k=1..n-1} Stirling2(n, k)*a(k) [Lengyel]. - Vladeta Jovovic, Apr 16 2003 E.g.f. satisfies Z(z) = 1/2 * (Z(exp(z)-1) - z). [Lengyel]
Asymptotic growth: a(n) ~ C_L*(n!)^2*(2log(2))^(-n)*n^(-1-1/3*log(2)) (Babai and Lengyel), with C_L = 1.0986858055... = A086053 [Flajolet and Salvy]. Sum_{k>=1} a(k-1)/fallfac(n,k) = -1/n^2 + 2*Sum_{k>=1} a(k-1)/n^k, with the falling factorials fallfac(n,k) = Product_{j=0..k-1}(n-j). - Vaclav Kotesovec, Aug 04 2015
EXAMPLE
The (3) = 4 chains from minimum to maximum in the lattice of set partitions of {1,2,3}:
{{1},{2},{3}} < {{1,2,3}}
{{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}
{{1},{2},{3}} < {{2},{1,3}} < {{1,2,3}}
{{1},{2},{3}} < {{3},{1,2}} < {{1,2,3}}
(End)
MATHEMATICA
a[1] = 1; a[n_] := a[n] = Sum[StirlingS2[n, k]*a[k], {k, 1, n-1}]; Array[a, 19]
PROG
(PARI) {a(n) = local(A); if( n<1, 0, for(k=1, n, A = truncate(A) + x*O(x^k); A = x - A + subst(A, x, exp(x + x*O(x^k)) - 1)); n! * polcoeff(A, n))} /* Michael Somos, Sep 22 2007 */
Pentagorials: n-th polygorial for k=5.
+10
21
1, 1, 5, 60, 1320, 46200, 2356200, 164934000, 15173928000, 1775349576000, 257425688520000, 45306921179520000, 9514453447699200000, 2350070001581702400000, 674470090453948588800000, 222575129849803034304000000
FORMULA
a(n) = polygorial(n, 5) = ( A000142(n)/ A000079(n))* A008544(n) = (n!/2^n)*Product_{i=0..n-1} (3*i+2) = (n!/2^n)*3^n*Pochhammer(2/3, n) = (n!/2^n)*3^n*GAMMA(n+2/3)/GAMMA(2/3). a(n) ~ Gamma(1/3) * 3^(n+1/2) * n^(2*n+2/3) / (2^n * exp(2*n)). - Vaclav Kotesovec, Jul 17 2015 D-finite with recurrence a(n+1) = ((n+1)*(3*n+2)/2)*a(n) = A000326(n+1)*a(n). - Muniru A Asiru, Apr 05 2016 E.g.f.: hypergeom([2/3, 1], [], (3/2)*x). - Robert Israel, Apr 05 2016
MAPLE
a := n->(n!/2^n)*mul(3*i+2, i=0..n-1); [seq(a(j), j=0..30)];
MATHEMATICA
Table[k! Pochhammer[2/3, k] (3/2)^k, {k, 0, 20}] (* Jan Mangaldan, Mar 20 2013 *) polygorial[k_, n_] := FullSimplify[ n!/2^n (k -2)^n*Pochhammer[2/(k -2), n]]; Array[polygorial[5, #] &, 17, 0] (* Robert G. Wilson v, Dec 17 2016 *)
AUTHOR
Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
Heptagorials: n-th polygorial for k=7.
+10
20
1, 1, 7, 126, 4284, 235620, 19085220, 2137544640, 316356606720, 59791398670080, 14050978687468800, 4018579904616076800, 1374354327378698265600, 553864793933615401036800, 259762588354865623086259200
FORMULA
a(n) = polygorial(n, 7) = ( A000142(n)/ A000079(n))* A047055(n) = (n!/2^n)*Product_{i=0..n-1}(5*i+2) = (n!/2^n)*5^n*Pochhammer(2/5, n) = (n!/2^n)*5^n*GAMMA(n+2/5)*sin(2*Pi/5)*GAMMA(3/5)/Pi. D-finite with recurrence 2*a(n) = n*(5*n-3)*a(n-1). - R. J. Mathar, Mar 12 2019
MAPLE
a := n->n!/2^n*mul(5*i+2, i=0..n-1); [seq(a(j), j=0..30)];
MATHEMATICA
polygorial[k_, n_] := FullSimplify[ n!/2^n (k -2)^n*Pochhammer[2/(k -2), n]]; Array[ polygorial[7, #] &, 16, 0] (* Robert G. Wilson v, Dec 26 2016 *) Join[{1}, FoldList[Times, PolygonalNumber[7, Range[20]]]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Jul 29 2019 *)
AUTHOR
Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
Hendecagorials: n-th polygorial for k=11.
+10
20
1, 1, 11, 330, 19140, 1818300, 256380300, 50250538800, 13065140088000, 4350691649304000, 1805537034461160000, 913601739437346960000, 553642654099032257760000, 395854497680808064298400000
FORMULA
a(n) = polygorial(n, 11) = ( A000142(n)/ A000079(n))* A084949(n) = (n!/2^n)*Product_{i=0..n-1} (9*i+2) = (n!/2^n)*9^n*Pochhammer(2/9, n) = (n!/2^n)*9^n*GAMMA(n+2/9)/GAMMA(2/9). D-finite with recurrence 2*a(n) = n*(9*n-7)*a(n-1). - R. J. Mathar, Mar 12 2019
MAPLE
a := n->n!/2^n*product(9*i+2, i=0..n-1); [seq(a(j), j=0..30)];
MATHEMATICA
polygorial[k_, n_] := FullSimplify[ n!/2^n (k -2)^n*Pochhammer[2/(k - 2), n]]; Array[polygorial[11, #] &, 16, 0] (* Robert G. Wilson v, Dec 13 2016 *)
AUTHOR
Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
Octagorials: n-th polygorial for k=8.
+10
19
1, 1, 8, 168, 6720, 436800, 41932800, 5577062400, 981562982400, 220851671040000, 61838467891200000, 21086917550899200000, 8603462360766873600000, 4138265395528866201600000, 2317428621496165072896000000
FORMULA
a(n) = polygorial(n, 8) = ( A000142(n)/ A000079(n))* A047657(n) = (n!/2^n)*Product_{i=0..n-1} (6*i+2) = (n!/2^n)*6^n*Pochhammer(1/3, n) = (n!/2)*3^n*sqrt(3)*GAMMA(n+1/3)*GAMMA(2/3)/Pi. D-finite with recurrence a(n) = n*(3*n-2)*a(n-1). - R. J. Mathar, Mar 12 2019
MAPLE
a := n->n!/2^n*product(6*i+2, i=0..n-1); [seq(a(j), j=0..30)];
MATHEMATICA
polygorial[k_, n_] := FullSimplify[ n!/2^n (k -2)^n*Pochhammer[2/(k -2), n]]; Array[polygorial[8, #] &, 16, 0] (* Robert G. Wilson v, Dec 26 2016 *)
PROG
(PARI) a(n) = n! / 2^n * prod(i=0, n-1, 6*i+2) \\ Felix Fröhlich, Dec 13 2016
AUTHOR
Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
Enneagorials: n-th polygorial for k=9.
+10
19
1, 1, 9, 216, 9936, 745200, 82717200, 12738448800, 2598643555200, 678245967907200, 220429939569840000, 87290256069656640000, 41375581377017247360000, 23128949989752641274240000
FORMULA
a(n) = polygorial(n, 9) = ( A000142(n)/ A000079(n))* A084947(n) = (n!/2^n)*Product_{i=0..n-1} (7*i+2) = (n!/2^n)*7^n*Pochhammer(2/7, n) = (n!/2^n)*7^n*GAMMA(n+2/7)/GAMMA(2/7). D-finite with recurrence 2*a(n) = n*(7*n-5)*a(n-1). - R. J. Mathar, Mar 12 2019
MAPLE
a := n->n!/2^n*product(7*i+2, i=0..n-1); [seq(a(j), j=0..30)];
MATHEMATICA
polygorial[k_, n_] := FullSimplify[ n!/2^n (k -2)^n*Pochhammer[2/(k -2), n]]; Array[polygorial[9, #] &, 16, 0] (* Robert G. Wilson v, Dec 26 2016 *)
AUTHOR
Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
Decagorials: n-th polygorial for k=10.
+10
19
1, 1, 10, 270, 14040, 1193400, 150368400, 26314470000, 6104957040000, 1813172240880000, 670873729125600000, 302564051835645600000, 163384587991248624000000, 104075982550425373488000000
FORMULA
a(n) = polygorial(n, 10) = ( A000142(n)/ A000079(n))* A084948(n) = (n!/2^n)*Product_{i=0..n-1} (8*i+2) = (n!/2^n)*8^n*Pochhammer(1/4, n) = (n!/2)*4^n*GAMMA(n+1/4)*sqrt(2)*GAMMA(3/4)/Pi. a(n) = Product_{k=1..n} k*(4k-3). - Daniel Suteu, Nov 01 2017 D-finite with recurrence a(n) -n*(4*n-3)*a(n-1)=0. - R. J. Mathar, May 02 2022
MAPLE
a := n->n!/2^n*product(8*i+2, i=0..n-1); [seq(a(j), j=0..30)];
MATHEMATICA
polygorial[k_, n_] := FullSimplify[ n!/2^n (k -2)^n*Pochhammer[2/(k -2), n]]; Array[polygorial[10, #] &, 14, 0] (* Robert G. Wilson v, Dec 26 2016 *)
AUTHOR
Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
Search completed in 0.065 seconds
| 
