cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 40 results. Next

A000108 Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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
Noncrossing partitions are partitions of genus 0. - Robert Coquereaux, Feb 13 2024
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_iA000272. - 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
The invert transform appears to converge to the Catalan numbers when applied infinitely many times to any starting sequence. - Mats Granvik, Gary W. Adamson and Roger L. Bagula, Sep 09 2008, Sep 12 2008
Limit_{n->oo} a(n)/a(n-1) = 4. - Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008
Starting with offset 1 = row sums of triangle A154559. - Gary W. Adamson, Jan 11 2009
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
Let A179277 = A(x). Then C(x) is satisfied by A(x)/A(x^2). - Gary W. Adamson, Jul 07 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
From Matthew Vandermast, Nov 22 2010: (Start)
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 also the number of standard Young tableau of shape (n,n). - Thotsaporn Thanatipanonda, Feb 25 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
a(n) is the size of the Jones monoid on 2n points (cf. A225798). - James Mitchell, Jul 28 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
From Alexander Adamchuk, Dec 27 2013: (Start)
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
From Fung Lam, May 01 2014: (Start)
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.
Special cases are A000108 (q=1), A068764 to A068772 (q=2 to 10), A240880 (q=-3).
(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
Permutations of length n that produce a bipartite permutation graph of order n [see Knuth (1973), Busch (2006), Golumbic and Trenk (2004)]. - Elise Anderson, R. M. Argus, Caitlin Owens, Tessa Stevens, Jun 27 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

Examples

			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
From _Joerg Arndt_, Jun 30 2014: (Start)
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)

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

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).
A row of A060854.
See A001003, A001190, A001699, A000081 for other ways to count parentheses.
Enumerates objects encoded by A014486.
A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Cf. A051168 (diagonal of the square array described).
Cf. A033552, A176137 (partitions into Catalan numbers).
Cf. A000753, A000736 (Boustrophedon transforms).
Cf. A120303 (largest prime factor of Catalan number).
Cf. A121839 (reciprocal Catalan constant), A268813.
Cf. A038003, A119861, A119908, A120274, A120275 (odd Catalan number).
Cf. A002390 (decimal expansion of natural logarithm of golden ratio).
Coefficients of square root of the g.f. are A001795/A046161.
For a(n) mod 6 see A259667.
For a(n) in base 2 see A264663.
Hankel transforms with first terms omitted: A001477, A006858, A091962, A078920, A123352, A368025.
Cf. A001147, A163960.
Cf. A332602 (conjectured production matrix).
Polyominoes: A001683(n+2) (oriented), A000207 (unoriented), A369314 (chiral), A208355(n-1) (achiral), A001764 {4,oo}.

Programs

  • GAP
    A000108:=List([0..30],n->Binomial(2*n,n)/(n+1)); # Muniru A Asiru, Feb 17 2018
  • 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
-- Reinhard Zumkeller, Nov 12 2011
a000108 = map last $ iterate (scanl1 (+) . (++ [0])) [1]
-- David Spies, Aug 23 2015
  • Magma
    C:= func< n | Binomial(2*n,n)/(n+1) >; [ C(n) : n in [0..60]];
  • Magma
    [Catalan(n): n in [0..40]]; // Vincenzo Librandi, Apr 02 2011
  • 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 *)
Table[Hypergeometric2F1[1 - n, -n, 2, 1], {n, 0, 20}] (* Richard L. Ollerton, Sep 13 2006 *)
Table[CatalanNumber @ n, {n, 0, 20}] (* Robert G. Wilson v, Feb 15 2011 *)
CatalanNumber[Range[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 *)
  • Maxima
    A000108(n):=binomial(2*n,n)/(n+1)$ makelist(A000108(n),n,0,30); /* Martin Ettl, Oct 24 2012 */
  • MuPAD
    combinat::dyckWords::count(n) $ n = 0..38 // Zerinvary Lajos, Apr 14 2007
  • 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
  • Python
    from gmpy2 import divexact
A000108 = [1, 1]
for n in range(1, 10**3):
    A000108.append(divexact(A000108[-1]*(4*n+2),(n+2))) # Chai Wah Wu, Aug 31 2014
  • Python
    # Works in Sage also.
A000108 = [1]
for n in range(1000):
    A000108.append(A000108[-1]*(4*n+2)//(n+2)) # Günter Rote, Nov 08 2023
  • Sage
    [catalan_number(i) for i in range(27)] # Zerinvary Lajos, Jun 26 2008
  • Sage
    # Generalized algorithm of L. Seidel
def A000108_list(n) :
    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
A000108_list(31) # Peter Luschny, Jun 02 2012

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+m) = Sum_{k} A039599(n, k)*A039599(m, k). - Philippe Deléham, Dec 22 2003
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} A008313(n, k)^2. - Philippe Deléham, Feb 14 2004
a(m+n+1) = Sum_{k>=0} A039598(m, k)*A039598(n, k). - Philippe Deléham, Feb 15 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
Sum_{n>=0} 1/a(n) = 2 + 4*Pi/3^(5/2) = F(1,2;1/2;1/4) = A268813 = 2.806133050770763... (see L'Univers de Pi link). - Gerald McGarvey and Benoit Cloitre, Feb 13 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
a((m+n)/2) = Sum_{k>=0} A053121(m, k)*A053121(n, k) if m+n is even. - Philippe Deléham, May 26 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) = a(n-1)*(4-6/(n+1)). a(n) = 2a(n-1)*(8a(n-2)+a(n-1))/(10a(n-2)-a(n-1)). - Franklin T. Adams-Watters, Feb 08 2006
Sum_{k>=1} a(k)/4^k = 1. - Franklin T. Adams-Watters, Jun 28 2006
a(n) = A047996(2*n+1, n). - Philippe Deléham, Jul 25 2006
Binomial transform of A005043. - Philippe Deléham, Oct 20 2006
a(n) = Sum_{k=0..n} (-1)^k*A116395(n,k). - Philippe Deléham, Nov 07 2006
a(n) = (1/(s-n))*Sum_{k=0..n} (-1)^k (k+s-n)*binomial(s-n,k) * binomial(s+n-k,s) with s a nonnegative free integer [H. W. Gould].
a(k) = Sum_{i=1..k} |A008276(i,k)| * (k-1)^(k-i) / k!. - André F. Labossière, May 29 2007
a(n) = Sum_{k=0..n} A129818(n,k) * A007852(k+1). - Philippe Deléham, Jun 20 2007
a(n) = Sum_{k=0..n} A109466(n,k) * A127632(k). - Philippe Deléham, Jun 20 2007
Row sums of triangle A124926. - Gary W. Adamson, Oct 22 2007
Limit_{n->oo} (1 + Sum_{k=0..n} a(k)/A004171(k)) = 4/Pi. - Reinhard Zumkeller, Aug 26 2008
a(n) = Sum_{k=0..n} A120730(n,k)^2 and a(k+1) = Sum_{n>=k} A120730(n,k). - Philippe Deléham, Oct 18 2008
Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example, the present sequence is Phi([1]) (also Phi([1,1])). - 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
a(n) = A000680(n)/A006472(n+1). - Mark Dols, Jul 14 2010; corrected by M. F. Hasler, Nov 08 2015
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
Complement of A092459; A010058(a(n)) = 1. - Reinhard Zumkeller, Mar 29 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
From Tom Copeland, Sep 30 2011: (Start)
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
A076050(a(n)) = n + 1 for n > 0. - Reinhard Zumkeller, Feb 17 2012
a(n) = A208355(2*n-1) = A208355(2*n) for n > 0. - Reinhard Zumkeller, Mar 04 2012
a(n+1) = A214292(2*n+1,n) = A214292(2*n+2,n). - Reinhard Zumkeller, Jul 12 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
For n > 0: a(n) = sum of row n in triangle A001263. - Reinhard Zumkeller, Oct 10 2013
a(n) = binomial(2n,n-1)/n and a(n) mod n = binomial(2n,n) mod n = A059288(n). - Jonathan Sondow, Dec 14 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) = Sum_{k=1..n} binomial(n+k-1,n)/n if n > 0. Alexander Adamchuk, Mar 25 2014
a(n) = -2^(2*n+1) * binomial(n-1/2, -3/2). - Peter Luschny, May 06 2014
a(n) = (4*A000984(n) - A000984(n+1))/2. - Stanislav Sykora, Aug 09 2014
a(n) = A246458(n) * A246466(n). - Tom Edgar, Sep 02 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(2n) = 2*A000150(2n); a(2n+1) = 2*A000150(2n+1) + a(n). - John Bodeen, Jun 24 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+kYuchun Ji, Sep 01 2016
a(n) = A001700(n) - A162551(n) = binomial(2*n+1,n+1). - 2*binomial(2*n,n-1). - Taras Goy, Aug 09 2018
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
C(n) = 1 + Sum_{i=0..n-1} A000245(i). - Yuchun Ji, Jan 10 2019
From A.H.M. Smeets, Apr 11 2020: (Start)
(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
From Peter Bala, Aug 17 2021: (Start)
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)
Sum_{n>=0} a(n)*(-1/4)^n = 2*(sqrt(2)-1) (A163960). - Amiram Eldar, Mar 22 2022
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
From Peter Bala, Feb 03 2024: (Start)
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)
a(n) = A363448(n) + A363449(n). - Julien Rouyer, Jun 28 2024

A001147 Double factorial of odd numbers: a(n) = (2*n-1)!! = 1*3*5*...*(2*n-1).

Original entry on oeis.org

1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, 654729075, 13749310575, 316234143225, 7905853580625, 213458046676875, 6190283353629375, 191898783962510625, 6332659870762850625, 221643095476699771875, 8200794532637891559375, 319830986772877770815625
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The solution to Schröder's third problem.
Number of fixed-point-free involutions in symmetric group S_{2n} (cf. A000085).
a(n-2) is the number of full Steiner topologies on n points with n-2 Steiner points. [corrected by Lyle Ramshaw, Jul 20 2022]
a(n) is also the number of perfect matchings in the complete graph K(2n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001
Number of ways to choose n disjoint pairs of items from 2*n items. - Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002
Number of ways to choose n-1 disjoint pairs of items from 2*n-1 items (one item remains unpaired). - Bartosz Zoltak, Oct 16 2012
For n >= 1 a(n) is the number of permutations in the symmetric group S_(2n) whose cycle decomposition is a product of n disjoint transpositions. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 21 2001
a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters (awalters3(AT)yahoo.com), Jan 17 2004. For example, a(3)=15 because the product of the four variables w, x, y and z can be constructed in exactly 15 ways, assuming commutativity but not associativity: 1. w(x(yz)) 2. w(y(xz)) 3. w(z(xy)) 4. x(w(yz)) 5. x(y(wz)) 6. x(z(wy)) 7. y(w(xz)) 8. y(x(wz)) 9. y(z(wx)) 10. z(w(xy)) 11. z(x(wy)) 12. z(y(wx)) 13. (wx)(yz) 14. (wy)(xz) 15. (wz)(xy).
a(n) = E(X^(2n)), where X is a standard normal random variable (i.e., X is normal with mean = 0, variance = 1). So for instance a(3) = E(X^6) = 15, etc. See Abramowitz and Stegun or Hoel, Port and Stone. - Jerome Coleman, Apr 06 2004
Second Eulerian transform of 1,1,1,1,1,1,... The second Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum_{k=0..n} E(n,k)s(k), where E(n,k) is a second-order Eulerian number (A008517). - Ross La Haye, Feb 13 2005
Integral representation as n-th moment of a positive function on the positive axis: a(n) = Integral_{x=0..oo} x^n*exp(-x/2)/sqrt(2*Pi*x) dx, n >= 0. - Karol A. Penson, Oct 10 2005
a(n) is the number of binary total partitions of n+1 (each non-singleton block must be partitioned into exactly two blocks) or, equivalently, the number of unordered full binary trees with n+1 labeled leaves (Stanley, ex 5.2.6). - Mitch Harris, Aug 01 2006
a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is i for iDavid Callan, Sep 25 2006
a(n) is the number of increasing ordered rooted trees on n+1 vertices where "increasing" means the vertices are labeled 0,1,2,...,n so that each path from the root has increasing labels. Increasing unordered rooted trees are counted by the factorial numbers A000142. - David Callan, Oct 26 2006
Number of perfect multi Skolem-type sequences of order n. - Emeric Deutsch, Nov 24 2006
a(n) = total weight of all Dyck n-paths (A000108) when each path is weighted with the product of the heights of the terminal points of its upsteps. For example with n=3, the 5 Dyck 3-paths UUUDDD, UUDUDD, UUDDUD, UDUUDD, UDUDUD have weights 1*2*3=6, 1*2*2=4, 1*2*1=2, 1*1*2=2, 1*1*1=1 respectively and 6+4+2+2+1=15. Counting weights by height of last upstep yields A102625. - David Callan, Dec 29 2006
a(n) is the number of increasing ternary trees on n vertices. Increasing binary trees are counted by ordinary factorials (A000142) and increasing quaternary trees by triple factorials (A007559). - David Callan, Mar 30 2007
From Tom Copeland, Nov 13 2007, clarified in first and extended in second paragraph, Jun 12 2021: (Start)
a(n) has the e.g.f. (1-2x)^(-1/2) = 1 + x + 3*x^2/2! + ..., whose reciprocal is (1-2x)^(1/2) = 1 - x - x^2/2! - 3*x^3/3! - ... = b(0) - b(1)*x - b(2)*x^2/2! - ... with b(0) = 1 and b(n+1) = -a(n) otherwise. By the formalism of A133314, Sum_{k=0..n} binomial(n,k)*b(k)*a(n-k) = 0^n where 0^0 := 1. In this sense, the sequence a(n) is essentially self-inverse. See A132382 for an extension of this result. See A094638 for interpretations.
This sequence aerated has the e.g.f. e^(t^2/2) = 1 + t^2/2! + 3*t^4/4! + ... = c(0) + c(1)*t + c(2)*t^2/2! + ... and the reciprocal e^(-t^2/2); therefore, Sum_{k=0..n} cos(Pi k/2)*binomial(n,k)*c(k)*c(n-k) = 0^n; i.e., the aerated sequence is essentially self-inverse. Consequently, Sum_{k=0..n} (-1)^k*binomial(2n,2k)*a(k)*a(n-k) = 0^n. (End)
From Ross Drewe, Mar 16 2008: (Start)
This is also the number of ways of arranging the elements of n distinct pairs, assuming the order of elements is significant but the pairs are not distinguishable, i.e., arrangements which are the same after permutations of the labels are equivalent.
If this sequence and A000680 are denoted by a(n) and b(n) respectively, then a(n) = b(n)/n! where n! = the number of ways of permuting the pair labels.
For example, there are 90 ways of arranging the elements of 3 pairs [1 1], [2 2], [3 3] when the pairs are distinguishable: A = { [112233], [112323], ..., [332211] }.
By applying the 6 relabeling permutations to A, we can partition A into 90/6 = 15 subsets: B = { {[112233], [113322], [221133], [223311], [331122], [332211]}, {[112323], [113232], [221313], [223131], [331212], [332121]}, ....}
Each subset or equivalence class in B represents a unique pattern of pair relationships. For example, subset B1 above represents {3 disjoint pairs} and subset B2 represents {1 disjoint pair + 2 interleaved pairs}, with the order being significant (contrast A132101). (End)
A139541(n) = a(n) * a(2*n). - Reinhard Zumkeller, Apr 25 2008
a(n+1) = Sum_{j=0..n} A074060(n,j) * 2^j. - Tom Copeland, Sep 01 2008
From Emeric Deutsch, Jun 05 2009: (Start)
a(n) is the number of adjacent transpositions in all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=3 because in 2143=(12)(34), 3412=(13)(24), and 4321=(14)(23) we have 2 + 0 + 1 adjacent transpositions.
a(n) = Sum_{k>=0} k*A079267(n,k).
(End)
Hankel transform is A137592. - Paul Barry, Sep 18 2009
(1, 3, 15, 105, ...) = INVERT transform of A000698 starting (1, 2, 10, 74, ...). - Gary W. Adamson, Oct 21 2009
a(n) = (-1)^(n+1)*H(2*n,0), where H(n,x) is the probabilists' Hermite polynomial. The generating function for the probabilists' Hermite polynomials is as follows: exp(x*t-t^2/2) = Sum_{i>=0} H(i,x)*t^i/i!. - Leonid Bedratyuk, Oct 31 2009
The Hankel transform of a(n+1) is A168467. - Paul Barry, Dec 04 2009
Partial products of odd numbers. - Juri-Stepan Gerasimov, Oct 17 2010
See A094638 for connections to differential operators. - Tom Copeland, Sep 20 2011
a(n) is the number of subsets of {1,...,n^2} that contain exactly k elements from {1,...,k^2} for k=1,...,n. For example, a(3)=15 since there are 15 subsets of {1,2,...,9} that satisfy the conditions, namely, {1,2,5}, {1,2,6}, {1,2,7}, {1,2,8}, {1,2,9}, {1,3,5}, {1,3,6}, {1,3,7}, {1,3,8}, {1,3,9}, {1,4,5}, {1,4,6}, {1,4,7}, {1,4,8}, and {1,4,9}. - Dennis P. Walsh, Dec 02 2011
a(n) is the leading coefficient of the Bessel polynomial y_n(x) (cf. A001498). - Leonid Bedratyuk, Jun 01 2012
For n>0: a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = min(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013
a(n) is also the numerator of the mean value from 0 to Pi/2 of sin(x)^(2n). - Jean-François Alcover, Jun 13 2013
a(n) is the size of the Brauer monoid on 2n points (see A227545). - James Mitchell, Jul 28 2013
For n>1: a(n) is the numerator of M(n)/M(1) where the numbers M(i) have the property that M(n+1)/M(n) ~ n-1/2 (for example, large Kendell-Mann numbers, see A000140 or A181609, as n --> infinity). - Mikhail Gaichenkov, Jan 14 2014
a(n) = the number of upper-triangular matrix representations required for the symbolic representation of a first order central moment of the multivariate normal distribution of dimension 2(n-1), i.e., E[X_1*X_2...*X_(2n-2)|mu=0, Sigma]. See vignette for symmoments R package on CRAN and Phillips reference below. - Kem Phillips, Aug 10 2014
For n>1: a(n) is the number of Feynman diagrams of order 2n (number of internal vertices) for the vacuum polarization with one charged loop only, in quantum electrodynamics. - Robert Coquereaux, Sep 15 2014
Aerated with intervening zeros (1,0,1,0,3,...) = a(n) (cf. A123023), the e.g.f. is e^(t^2/2), so this is the base for the Appell sequence A099174 with e.g.f. e^(t^2/2) e^(x*t) = exp(P(.,x),t) = unsigned A066325(x,t), the probabilist's (or normalized) Hermite polynomials. P(n,x) = (a. + x)^n with (a.)^n = a_n and comprise the umbral compositional inverses for A066325(x,t) = exp(UP(.,x),t), i.e., UP(n,P(.,t)) = x^n = P(n,UP(.,t)), where UP(n,t) are the polynomials of A066325 and, e.g., (P(.,t))^n = P(n,t). - Tom Copeland, Nov 15 2014
a(n) = the number of relaxed compacted binary trees of right height at most one of size n. A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. The number of unbounded relaxed compacted binary trees of size n is A082161(n). See the Genitrini et al. link. - Michael Wallner, Jun 20 2017
Also the number of distinct adjacency matrices in the n-ladder rung graph. - Eric W. Weisstein, Jul 22 2017
From Christopher J. Smyth, Jan 26 2018: (Start)
a(n) = the number of essentially different ways of writing a probability distribution taking n+1 values as a sum of products of binary probability distributions. See comment of Mitch Harris above. This is because each such way corresponds to a full binary tree with n+1 leaves, with the leaves labeled by the values. (This comment is due to Niko Brummer.)
Also the number of binary trees with root labeled by an (n+1)-set S, its n+1 leaves by the singleton subsets of S, and other nodes labeled by subsets T of S so that the two daughter nodes of the node labeled by T are labeled by the two parts of a 2-partition of T. This also follows from Mitch Harris' comment above, since the leaf labels determine the labels of the other vertices of the tree.
(End)
a(n) is the n-th moment of the chi-squared distribution with one degree of freedom (equivalent to Coleman's Apr 06 2004 comment). - Bryan R. Gillespie, Mar 07 2021
Let b(n) = 0 for n odd and b(2k) = a(k); i.e., let the sequence b(n) be an aerated version of this entry. After expanding the differential operator (x + D)^n and normal ordering the resulting terms, the integer coefficient of the term x^k D^m is n! b(n-k-m) / [(n-k-m)! k! m!] with 0 <= k,m <= n and (k+m) <= n. E.g., (x+D)^2 = x^2 + 2xD + D^2 + 1 with D = d/dx. The result generalizes to the raising (R) and lowering (L) operators of any Sheffer polynomial sequence by replacing x by R and D by L and follows from the disentangling relation e^{t(L+R)} = e^{t^2/2} e^{tR} e^{tL}. Consequently, these are also the coefficients of the reordered 2^n permutations of the binary symbols L and R under the condition LR = RL + 1. E.g., (L+R)^2 = LL + LR + RL + RR = LL + 2RL + RR + 1. (Cf. A344678.) - Tom Copeland, May 25 2021
From Tom Copeland, Jun 14 2021: (Start)
Lando and Zvonkin present several scenarios in which the double factorials occur in their role of enumerating perfect matchings (pairings) and as the nonzero moments of the Gaussian e^(x^2/2).
Speyer and Sturmfels (p. 6) state that the number of facets of the abstract simplicial complex known as the tropical Grassmannian G'''(2,n), the space of phylogenetic T_n trees (see A134991), or Whitehouse complex is a shifted double factorial.
These are also the unsigned coefficients of the x[2]^m terms in the partition polynomials of A134685 for compositional inversion of e.g.f.s, a refinement of A134991.
a(n)*2^n = A001813(n) and A001813(n)/(n+1)! = A000108(n), the Catalan numbers, the unsigned coefficients of the x[2]^m terms in the partition polynomials A133437 for compositional inversion of o.g.f.s, a refinement of A033282, A126216, and A086810. Then the double factorials inherit a multitude of analytic and combinatoric interpretations from those of the Catalan numbers, associahedra, and the noncrossing partitions of A134264 with the Catalan numbers as unsigned-row sums. (End)
Connections among the Catalan numbers A000108, the odd double factorials, values of the Riemann zeta function and its derivative for integer arguments, and series expansions of the reduced action for the simple harmonic oscillator and the arc length of the spiral of Archimedes are given in the MathOverflow post on the Riemann zeta function. - Tom Copeland, Oct 02 2021
b(n) = a(n) / (n! 2^n) = Sum_{k = 0..n} (-1)^n binomial(n,k) (-1)^k a(k) / (k! 2^k) = (1-b.)^n, umbrally; i.e., the normalized double factorial a(n) is self-inverse under the binomial transform. This can be proved by applying the Euler binomial transformation for o.g.f.s Sum_{n >= 0} (1-b.)^n x^n = (1/(1-x)) Sum_{n >= 0} b_n (x / (x-1))^n to the o.g.f. (1-x)^{-1/2} = Sum_{n >= 0} b_n x^n. Other proofs are suggested by the discussion in Watson on pages 104-5 of transformations of the Bessel functions of the first kind with b(n) = (-1)^n binomial(-1/2,n) = binomial(n-1/2,n) = (2n)! / (n! 2^n)^2. - Tom Copeland, Dec 10 2022

Examples

			a(3) = 1*3*5 = 15.
From _Joerg Arndt_, Sep 10 2013: (Start)
There are a(3)=15 involutions of 6 elements without fixed points:
  #:    permutation           transpositions
  01:  [ 1 0 3 2 5 4 ]      (0, 1) (2, 3) (4, 5)
  02:  [ 1 0 4 5 2 3 ]      (0, 1) (2, 4) (3, 5)
  03:  [ 1 0 5 4 3 2 ]      (0, 1) (2, 5) (3, 4)
  04:  [ 2 3 0 1 5 4 ]      (0, 2) (1, 3) (4, 5)
  05:  [ 2 4 0 5 1 3 ]      (0, 2) (1, 4) (3, 5)
  06:  [ 2 5 0 4 3 1 ]      (0, 2) (1, 5) (3, 4)
  07:  [ 3 2 1 0 5 4 ]      (0, 3) (1, 2) (4, 5)
  08:  [ 3 4 5 0 1 2 ]      (0, 3) (1, 4) (2, 5)
  09:  [ 3 5 4 0 2 1 ]      (0, 3) (1, 5) (2, 4)
  10:  [ 4 2 1 5 0 3 ]      (0, 4) (1, 2) (3, 5)
  11:  [ 4 3 5 1 0 2 ]      (0, 4) (1, 3) (2, 5)
  12:  [ 4 5 3 2 0 1 ]      (0, 4) (1, 5) (2, 3)
  13:  [ 5 2 1 4 3 0 ]      (0, 5) (1, 2) (3, 4)
  14:  [ 5 3 4 1 2 0 ]      (0, 5) (1, 3) (2, 4)
  15:  [ 5 4 3 2 1 0 ]      (0, 5) (1, 4) (2, 3)
(End)
G.f. = 1 + x + 3*x^2 + 15*x^3 + 105*x^4 + 945*x^5 + 10395*x^6 + 135135*x^7 + ...

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, (26.2.28).
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 317.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228, #19.
  • Hoel, Port and Stone, Introduction to Probability Theory, Section 7.3.
  • F. K. Hwang, D. S. Richards and P. Winter, The Steiner Tree Problem, North-Holland, 1992, see p. 14.
  • C. Itzykson and J.-B. Zuber, Quantum Field Theory, McGraw-Hill, 1980, pages 466-467.
  • 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. 2, 1999; see Example 5.2.6 and also p. 178.
  • R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer-Verlag, New York, 1999, p. 73.
  • G. Watson, The Theory of Bessel Functions, Cambridge Univ. Press, 1922.

Links

Crossrefs

Cf. A000085, A006882, A000165 ((2n)!!), A001818, A009445, A039683, A102992, A001190 (no labels), A000680, A132101.
Cf. A086677; A055142 (for this sequence, |a(n+1)| + 1 is the number of distinct products which can be formed using commutative, nonassociative multiplication and a nonempty subset of n given variables).
Constant terms of polynomials in A098503. First row of array A099020.
Cf. A079267, A000698, A029635, A161198, A076795, A123023, A161124, A051125, A181983, A099174, A087547, A028338 (first column).
Subsequence of A248652.
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A053871 (binomial transform).
Cf. A000108, A001813, A033282, A060540, A086810, A094638, A126216, A133437, A134264, A134685, A134991, A344678.

Programs

  • GAP
    A001147 := function(n) local i, s, t; t := 1; i := 0; Print(t, ", "); for i in [1 .. n] do t := t*(2*i-1); Print(t, ", "); od; end; A001147(100); # Stefano Spezia, Nov 13 2018
  • Haskell
    a001147 n = product [1, 3 .. 2 * n - 1]
a001147_list = 1 : zipWith (*) [1, 3 ..] a001147_list
-- Reinhard Zumkeller, Feb 15 2015, Dec 03 2011
  • Magma
    A001147:=func< n | n eq 0 select 1 else &*[ k: k in [1..2*n-1 by 2] ] >; [ A001147(n): n in [0..20] ]; // Klaus Brockhaus, Jun 22 2011
  • Magma
    I:=[1,3]; [1] cat [n le 2 select I[n]  else (3*n-2)*Self(n-1)-(n-1)*(2*n-3)*Self(n-2): n in [1..25] ]; // Vincenzo Librandi, Feb 19 2015
  • Maple
    f := n->(2*n)!/(n!*2^n);
A001147 := proc(n) doublefactorial(2*n-1); end: # R. J. Mathar, Jul 04 2009
A001147 := n -> 2^n*pochhammer(1/2, n); # Peter Luschny, Aug 09 2009
G(x):=(1-2*x)^(-1/2): f[0]:=G(x): for n from 1 to 29 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n],n=0..19); # Zerinvary Lajos, Apr 03 2009; aligned with offset by Johannes W. Meijer, Aug 11 2009
series(hypergeom([1,1/2],[],2*x),x=0,20); # Mark van Hoeij, Apr 07 2013
  • Mathematica
    Table[(2 n - 1)!!, {n, 0, 19}] (* Robert G. Wilson v, Oct 12 2005 *)
a[ n_] := 2^n Gamma[n + 1/2] / Gamma[1/2]; (* Michael Somos, Sep 18 2014 *)
Join[{1}, Range[1, 41, 2]!!] (* Harvey P. Dale, Jan 28 2017 *)
a[ n_] := If[ n < 0, (-1)^n / a[-n], SeriesCoefficient[ Product[1 - (1 - x)^(2 k - 1), {k, n}], {x, 0, n}]]; (* Michael Somos, Jun 27 2017 *)
(2 Range[0, 20] - 1)!! (* Eric W. Weisstein, Jul 22 2017 *)
  • Maxima
    a(n):=if n=0 then 1 else sum(sum(binomial(n-1,i)*binomial(n-i-1,j)*a(i)*a(j)*a(n-i-j-1),j,0,n-i-1),i,0,n-1); /* Vladimir Kruchinin, May 06 2020 */
  • PARI
    {a(n) = if( n<0, (-1)^n / a(-n), (2*n)! / n! / 2^n)}; /* Michael Somos, Sep 18 2014 */
  • PARI
    x='x+O('x^33); Vec(serlaplace((1-2*x)^(-1/2))) \\ Joerg Arndt, Apr 24 2011
  • Python
    from sympy import factorial2
def a(n): return factorial2(2 * n - 1)
print([a(n) for n in range(101)])  # Indranil Ghosh, Jul 22 2017
  • Sage
    [rising_factorial(n+1,n)/2^n for n in (0..15)] # Peter Luschny, Jun 26 2012

Formula

E.g.f.: 1 / sqrt(1 - 2*x).
D-finite with recurrence: a(n) = a(n-1)*(2*n-1) = (2*n)!/(n!*2^n) = A010050(n)/A000165(n).
a(n) ~ sqrt(2) * 2^n * (n/e)^n.
Rational part of numerator of Gamma(n+1/2): a(n) * sqrt(Pi) / 2^n = Gamma(n+1/2). - Yuriy Brun, Ewa Dominowska (brun(AT)mit.edu), May 12 2001
With interpolated zeros, the sequence has e.g.f. exp(x^2/2). - Paul Barry, Jun 27 2003
The Ramanujan polynomial psi(n+1, n) has value a(n). - Ralf Stephan, Apr 16 2004
a(n) = Sum_{k=0..n} (-2)^(n-k)*A048994(n, k). - Philippe Deléham, Oct 29 2005
Log(1 + x + 3*x^2 + 15*x^3 + 105*x^4 + 945*x^5 + 10395*x^6 + ...) = x + 5/2*x^2 + 37/3*x^3 + 353/4*x^4 + 4081/5*x^5 + 55205/6*x^6 + ..., where [1, 5, 37, 353, 4081, 55205, ...] = A004208. - Philippe Deléham, Jun 20 2006
1/3 + 2/15 + 3/105 + ... = 1/2. [Jolley eq. 216]
Sum_{j=1..n} j/a(j+1) = (1 - 1/a(n+1))/2. [Jolley eq. 216]
1/1 + 1/3 + 2/15 + 6/105 + 24/945 + ... = Pi/2. - Gary W. Adamson, Dec 21 2006
a(n) = (1/sqrt(2*Pi))*Integral_{x>=0} x^n*exp(-x/2)/sqrt(x). - Paul Barry, Jan 28 2008
a(n) = A006882(2n-1). - R. J. Mathar, Jul 04 2009
G.f.: 1/(1-x-2x^2/(1-5x-12x^2/(1-9x-30x^2/(1-13x-56x^2/(1- ... (continued fraction). - Paul Barry, Sep 18 2009
a(n) = (-1)^n*subs({log(e)=1,x=0},coeff(simplify(series(e^(x*t-t^2/2),t,2*n+1)),t^(2*n))*(2*n)!). - Leonid Bedratyuk, Oct 31 2009
a(n) = 2^n*gamma(n+1/2)/gamma(1/2). - Jaume Oliver Lafont, Nov 09 2009
G.f.: 1/(1-x/(1-2x/(1-3x/(1-4x/(1-5x/(1- ...(continued fraction). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009
The g.f. of a(n+1) is 1/(1-3x/(1-2x/(1-5x/(1-4x/(1-7x/(1-6x/(1-.... (continued fraction). - Paul Barry, Dec 04 2009
a(n) = Sum_{i=1..n} binomial(n,i)*a(i-1)*a(n-i). - Vladimir Shevelev, Sep 30 2010
E.g.f.: A(x) = 1 - sqrt(1-2*x) satisfies the differential equation A'(x) - A'(x)*A(x) - 1 = 0. - Vladimir Kruchinin, Jan 17 2011
a(n) = A123023(2*n). - Michael Somos, Jul 24 2011
a(n) = (1/2)*Sum_{i=1..n} binomial(n+1,i)*a(i-1)*a(n-i). See link above. - Dennis P. Walsh, Dec 02 2011
a(n) = Sum_{k=0..n} (-1)^k*binomial(2*n,n+k)*Stirling_1(n+k,k) [Kauers and Ko].
a(n) = A035342(n, 1), n >= 1 (first column of triangle).
a(n) = A001497(n, 0) = A001498(n, n), first column, resp. main diagonal, of Bessel triangle.
From Gary W. Adamson, Jul 19 2011: (Start)
a(n) = upper left term of M^n and sum of top row terms of M^(n-1), where M = a variant of the (1,2) Pascal triangle (Cf. A029635) as the following production matrix:
1, 2, 0, 0, 0, ...
1, 3, 2, 0, 0, ...
1, 4, 5, 2, 0, ...
1, 5, 9, 7, 2, ...
...
For example, a(3) = 15 is the left term in top row of M^3: (15, 46, 36, 8) and a(4) = 105 = (15 + 46 + 36 + 8).
(End)
G.f.: A(x) = 1 + x/(W(0) - x); W(k) = 1 + x + x*2*k - x*(2*k + 3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011
a(n) = Sum_{i=1..n} binomial(n,i-1)*a(i-1)*a(n-i). - Dennis P. Walsh, Dec 02 2011
a(n) = A009445(n) / A014481(n). - Reinhard Zumkeller, Dec 03 2011
a(n) = (-1)^n*Sum_{k=0..n} 2^(n-k)*s(n+1,k+1), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012
a(n) = (2*n)4! = Gauss_factorial(2*n,4) = Product{j=1..2*n, gcd(j,4)=1} j. - Peter Luschny, Oct 01 2012
G.f.: (1 - 1/Q(0))/x where Q(k) = 1 - x*(2*k - 1)/(1 - x*(2*k + 2)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 19 2013
G.f.: 1 + x/Q(0), where Q(k) = 1 + (2*k - 1)*x - 2*x*(k + 1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 2*x*(2*k + 1)/(2*x*(2*k + 1) - 1 + 2*x*(2*k + 2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x/(x + 1/(2*k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
G.f.: G(0), where G(k) = 1 + 2*x*(4*k + 1)/(4*k + 2 - 2*x*(2*k + 1)*(4*k + 3)/(x*(4*k + 3) + 2*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 22 2013
a(n) = (2*n - 3)*a(n-2) + (2*n - 2)*a(n-1), n > 1. - Ivan N. Ianakiev, Jul 08 2013
G.f.: G(0), where G(k) = 1 - x*(k+1)/(x*(k+1) - 1/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Aug 04 2013
a(n) = 2*a(n-1) + (2n-3)^2*a(n-2), a(0) = a(1) = 1. - Philippe Deléham, Oct 27 2013
G.f. of reciprocals: Sum_{n>=0} x^n/a(n) = 1F1(1; 1/2; x/2), confluent hypergeometric Function. - R. J. Mathar, Jul 25 2014
0 = a(n)*(+2*a(n+1) - a(n+2)) + a(n+1)*(+a(n+1)) for all n in Z. - Michael Somos, Sep 18 2014
a(n) = (-1)^n / a(-n) = 2*a(n-1) + a(n-1)^2 / a(n-2) for all n in Z. - Michael Somos, Sep 18 2014
From Peter Bala, Feb 18 2015: (Start)
Recurrence equation: a(n) = (3*n - 2)*a(n-1) - (n - 1)*(2*n - 3)*a(n-2) with a(1) = 1 and a(2) = 3.
The sequence b(n) = A087547(n), beginning [1, 4, 52, 608, 12624, ... ], satisfies the same second-order recurrence equation. This leads to the generalized continued fraction expansion lim_{n -> infinity} b(n)/a(n) = Pi/2 = 1 + 1/(3 - 6/(7 - 15/(10 - ... - n*(2*n - 1)/((3*n + 1) - ... )))). (End)
E.g.f of the sequence whose n-th element (n = 1,2,...) equals a(n-1) is 1-sqrt(1-2*x). - Stanislav Sykora, Jan 06 2017
Sum_{n >= 1} a(n)/(2*n-1)! = exp(1/2). - Daniel Suteu, Feb 06 2017
a(n) = A028338(n, 0), n >= 0. - Wolfdieter Lang, May 27 2017
a(n) = (Product_{k=0..n-2} binomial(2*(n-k),2))/n!. - Stefano Spezia, Nov 13 2018
a(n) = Sum_{i=0..n-1} Sum_{j=0..n-i-1} C(n-1,i)*C(n-i-1,j)*a(i)*a(j)*a(n-i-j-1), a(0)=1, - Vladimir Kruchinin, May 06 2020
From Amiram Eldar, Jun 29 2020: (Start)
Sum_{n>=1} 1/a(n) = sqrt(e*Pi/2)*erf(1/sqrt(2)), where erf is the error function.
Sum_{n>=1} (-1)^(n+1)/a(n) = sqrt(Pi/(2*e))*erfi(1/sqrt(2)), where erfi is the imaginary error function. (End)
G.f. of reciprocals: R(x) = Sum_{n>=0} x^n/a(n) satisfies (1 + x)*R(x) = 1 + 2*x*R'(x). - Werner Schulte, Nov 04 2024

Extensions

Removed erroneous comments: neither the number of n X n binary matrices A such that A^2 = 0 nor the number of simple directed graphs on n vertices with no directed path of length two are counted by this sequence (for n = 3, both are 13). - Dan Drake, Jun 02 2009

A002054 Binomial coefficient C(2n+1, n-1).

Original entry on oeis.org

1, 5, 21, 84, 330, 1287, 5005, 19448, 75582, 293930, 1144066, 4457400, 17383860, 67863915, 265182525, 1037158320, 4059928950, 15905368710, 62359143990, 244662670200, 960566918220, 3773655750150, 14833897694226, 58343356817424, 229591913401900
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) = number of permutations in S_{n+2} containing exactly one 312 pattern. E.g., S_3 has a_1 = 1 permutations containing exactly one 312 pattern, and S_4 has a_2 = 5 permutations containing exactly one 312 pattern, namely 1423, 2413, 3124, 3142, and 4231. This comment is also true if 312 is replaced by any of 132, 213, or 231 (but not 123 or 321, for which see A003517). [Comment revised by N. J. A. Sloane, Nov 26 2022]
Number of valleys in all Dyck paths of semilength n+1. Example: a(2)=5 because UD*UD*UD, UD*UUDD, UUDD*UD, UUD*UDD, UUUDDD, where U=(1,1), D=(1,-1) and the valleys are shown by *. - Emeric Deutsch, Dec 05 2003
Number of UU's (double rises) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDU*UDD, U*UDDUD, U*UDUDD, U*U*UDDD, the double rises being shown by *. - Emeric Deutsch, Dec 05 2003
Number of peaks at level higher than one (high peaks) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUU*DDD, the high peaks being shown by *. - Emeric Deutsch, Dec 05 2003
Number of diagonal dissections of a convex (n+3)-gon into n regions. Number of standard tableaux of shape (n,n,1) (see Stanley reference). - Emeric Deutsch, May 20 2004
Number of dissections of a convex (n+3)-gon by noncrossing diagonals into several regions, exactly n-1 of which are triangular. Example: a(2)=5 because the convex pentagon ABCDE is dissected by any of the diagonals AC, BD, CE, DA, EB into regions containing exactly 1 triangle. - Emeric Deutsch, May 31 2004
Number of jumps in all full binary trees with n+1 internal nodes. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007
a(n) is the total number of nonempty Dyck subpaths in all Dyck paths (A000108) of semilength n. For example, the Dyck path UUDUUDDD has Dyck subpaths stretching over positions 1-8 (the entire path), 2-3, 2-7, 4-7, 5-6 and so contributes 5 to a(4). - David Callan, Jul 25 2008
a(n+1) is the total number of ascents in the set of all n-permutations avoiding the pattern 132. For example, a(2) = 5 because there are 5 ascents in the set 123, 213, 231, 312, 321. - Cheyne Homberger, Oct 25 2013
Number of increasing tableaux of shape (n+1,n+1) with largest entry 2n+1. An increasing tableau is a semistandard tableau with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 5 counts the five tableaux (124)(235), (123)(245), (124)(345), (134)(245), (123)(245). - Oliver Pechenik, May 02 2014
a(n) is the number of noncrossing partitions of 2n+1 into n-1 blocks of size 2 and 1 block of size 3. - Oliver Pechenik, May 02 2014
Number of paths in the half-plane x>=0, from (0,0) to (2n+1,3), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 5 paths: UUUUD, UUUDU, UUDUU, UDUUU, DUUUU. - José Luis Ramírez Ramírez, Apr 19 2015
From Gus Wiseman, Aug 20 2021: (Start)
Also the number of binary numbers with 2n+2 digits and with two more 0's than 1's. For example, the a(2) = 5 binary numbers are: 100001, 100010, 100100, 101000, 110000, with decimal values 33, 34, 36, 40, 48. Allowing first digit 0 gives A001791, ranked by A345910/A345912.
Also the number of integer compositions of 2n+2 with alternating sum -2, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(3) = 21 compositions are:
(35) (152) (1124) (11141) (111113)
(251) (1223) (12131) (111212)
(1322) (13121) (111311)
(1421) (14111) (121112)
(2114) (121211)
(2213) (131111)
(2312)
(2411)
The following pertain to these compositions:
- The unordered version is A344741.
- Ranked by A345924 (reverse: A345923).
- A345197 counts compositions by length and alternating sum.
- A345925 ranks compositions with alternating sum 2 (reverse: A345922).
(End)

Examples

			G.f. = x + 5*x^2 + 21*x^3 + 84*x^4 + 330*x^5 + 1287*x^6 + 5005*x^7 + ...

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
  • George Grätzer, General Lattice Theory. Birkhauser, Basel, 1998, 2nd edition, p. 474, line -3.
  • A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
  • 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).

Links

Crossrefs

Diagonal 4 of triangle A100257. Also a diagonal of A033282.
Equals (1/2) A024483(n+2). Bisection of A037951 and A037955.
Cf. A001263.
Column k=1 of A263771.
Counts terms of A031445 with 2n+2 digits in binary.
Cf. A000097, A000346, A000984, A001622, A001700, A007318, A008549, A031444, A058622, A097805, A116406, A138364, A163493, A202736.
Cf. binomial(2*n+m, n): A000984 (m = 0), A001700 (m = 1), A001791 (m = 2), A002694 (m = 4), A003516 (m = 5), A002696 (m = 6), A030053 - A030056, A004310 - A004318.

Programs

  • GAP
    List([1..25],n->Binomial(2*n+1,n-1)); # Muniru A Asiru, Aug 09 2018
  • Magma
    [Binomial(2*n+1, n-1): n in [1..30]]; // Vincenzo Librandi, Apr 20 2015
  • Maple
    with(combstruct): seq((count(Composition(2*n+2), size=n)), n=1..24); # Zerinvary Lajos, May 03 2007
  • Mathematica
    CoefficientList[Series[8/(((Sqrt[1-4x] +1)^3)*Sqrt[1-4x]), {x,0,22}], x] (* Robert G. Wilson v, Aug 08 2011 *)
a[ n_]:= Binomial[2 n + 1, n - 1]; (* Michael Somos, Apr 25 2014 *)
  • PARI
    {a(n) = binomial( 2*n+1, n-1)};
  • Python
    from _future_ import division
A002054_list, b = [], 1
for n in range(1,10**3):
    A002054_list.append(b)
    b = b*(2*n+2)*(2*n+3)//(n*(n+3)) # Chai Wah Wu, Jan 26 2016
  • Sage
    [binomial(2*n+1, n-1) for n in (1..25)] # G. C. Greubel, Mar 22 2019

Formula

a(n) = Sum_{j=0..n-1} binomial(2*j, j) * binomial(2*n - 2*j, n-j-1)/(j+1). - Yong Kong (ykong(AT)curagen.com), Dec 26 2000
G.f.: z*C^4/(2-C), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function. - Emeric Deutsch, Jul 05 2003
From Wolfdieter Lang, Jan 09 2004: (Start)
a(n) = binomial(2*n+1, n-1) = n*C(n+1)/2, C(n)=A000108(n) (Catalan).
G.f.: (1 - 2*x - (1-3*x)*c(x))/(x*(1-4*x)) with g.f. c(x) of A000108. (End)
G.f.: z*C(z)^3/(1-2*z*C(z)), where C(z) is the g.f. of Catalan numbers. - José Luis Ramírez Ramírez, Apr 19 2015
G.f.: 2F1(5/2, 2; 4; 4*x). - R. J. Mathar, Aug 09 2015
D-finite with recurrence: a(n+1) = a(n)*(2*n+3)*(2*n+2)/(n*(n+3)). - Chai Wah Wu, Jan 26 2016
From Ilya Gutkovskiy, Aug 30 2016: (Start)
E.g.f.: (BesselI(0,2*x) + (1 - 1/x)*BesselI(1,2*x))*exp(2*x).
a(n) ~ 2^(2*n+1)/sqrt(Pi*n). (End)
a(n) = (1/(n+1))*Sum_{i=0..n-1} (n+1-i)*binomial(2n+2,i), n >= 1. - Taras Goy, Aug 09 2018
G.f.: (x - 1 + (1 - 3*x)/sqrt(1 - 4*x))/(2*x^2). - Michael Somos, Jul 28 2021
From Amiram Eldar, Jan 24 2022: (Start)
Sum_{n>=1} 1/a(n) = 5/3 - 2*Pi/(9*sqrt(3)).
Sum_{n>=1} (-1)^(n+1)/a(n) = 52*log(phi)/(5*sqrt(5)) - 7/5, where phi is the golden ratio (A001622). (End)
a(n) = A001405(2*n+1) - A000108(n+1), n >= 1 (from Eremin link, page 7). - Gennady Eremin, Sep 05 2023
G.f.: x/(1 - 4*x)^2 * c(-x/(1 - 4*x))^3, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, Feb 03 2024
From Peter Bala, Oct 13 2024: (Start)
a(n) = Integral_{x = 0..4} x^n * w(x) dx, where the weight function w(x) = 1/(2*Pi) * sqrt(x)*(x - 3)/sqrt(4 - x) (see Penson).
G.f. x*/sqrt(1 - 4*x) * c(x)^3. (End)

A092392 Triangle read by rows: T(n,k) = C(2*n - k,n), 0 <= k <= n.

Original entry on oeis.org

1, 2, 1, 6, 3, 1, 20, 10, 4, 1, 70, 35, 15, 5, 1, 252, 126, 56, 21, 6, 1, 924, 462, 210, 84, 28, 7, 1, 3432, 1716, 792, 330, 120, 36, 8, 1, 12870, 6435, 3003, 1287, 495, 165, 45, 9, 1, 48620, 24310, 11440, 5005, 2002, 715, 220, 55, 10, 1, 184756, 92378, 43758, 19448, 8008, 3003, 1001, 286, 66, 11, 1
Offset: 0

Views

Author

Ralf Stephan, Mar 21 2004

Keywords

Comments

First column is C(2*n,n) or A000984. Central coefficients are C(3*n,n) or A005809. - Paul Barry, Oct 14 2009
T(n,k) = A046899(n,n-k), k = 0..n-1. - Reinhard Zumkeller, Jul 27 2012
From Peter Bala, Nov 03 2015: (Start)
Viewed as the square array [binomial (2*n + k, n + k)]n,k>=0 this is the generalized Riordan array ( 1/sqrt(1 - 4*x),c(x) ) in the sense of the Bala link, where c(x) is the o.g.f. for A000108.
The square array factorizes as ( 1/(2 - c(x)),x*c(x) ) * ( 1/(1 - x),1/(1 - x) ), which equals the matrix product of A100100 with the square Pascal matrix [binomial (n + k,k)]n,k>=0. See the example below. (End)

Examples

			From _Paul Barry_, Oct 14 2009: (Start)
Triangle begins
  1,
  2, 1,
  6, 3, 1,
  20, 10, 4, 1,
  70, 35, 15, 5, 1,
  252, 126, 56, 21, 6, 1,
  924, 462, 210, 84, 28, 7, 1,
  3432, 1716, 792, 330, 120, 36, 8, 1
Production array is
  2, 1,
  2, 1, 1,
  2, 1, 1, 1,
  2, 1, 1, 1, 1,
  2, 1, 1, 1, 1, 1,
  2, 1, 1, 1, 1, 1, 1,
  2, 1, 1, 1, 1, 1, 1, 1,
  2, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 1, 1, 1, 1, 1, 1, 1, 1, 1 (End)
As a square array = A100100 * square Pascal matrix:
  /1   1  1  1 ...\   / 1          \/1 1  1  1 ...\
  |2   3  4  5 ...|   | 1 1        ||1 2  3  4 ...|
  |6  10 15 21 ...| = | 3 2 1      ||1 3  6 10 ...|
  |20 35 56 84 ...|   |10 6 3 1    ||1 4 10 20 ...|
  |70 ...         |   |35 ...      ||1 ...        |
- _Peter Bala_, Nov 03 2015

Links

Crossrefs

Rows 0-14 are A000984, A001700, A001791, A002054, A002694, A003516, A002696, A030053, A004310, A030054, A004311, A030055, A004312, A030056, A004313.
Columns are A000217, A000292, A000332, A000389, A000579.
Diagonals are A005809, A045721, A025174, A004319, A013698, A003408.
Cf. A100100.

Programs

  • Haskell
    a092392 n k = a092392_tabl !! (n-1) !! (k-1)
a092392_row n = a092392_tabl !! (n-1)
a092392_tabl = map reverse a046899_tabl
-- Reinhard Zumkeller, Jul 27 2012
  • Magma
    /* As a triangle */ [[Binomial(2*n-k, n): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Nov 22 2017
  • Maple
    A092392 := proc(n,k)
    binomial(2*n-k,n-k) ;
end proc:
seq(seq(A092392(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Feb 06 2015
  • Mathematica
    Table[Binomial[2 n - k, n], {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Mar 19 2016 *)
  • Maxima
    C(x):=(1-sqrt(1-4*x))/2;
A(x,y):=(1/sqrt(1-4*x))/(1-y*C(x));
taylor(A(x,y),y,0,10,x,0,10); /* Vladimir Kruchinin, Mar 19 2016 */
  • PARI
    for(n=0,10, for(k=0,n, print1(binomial(2*n - k,n), ", "))) \\ G. C. Greubel, Nov 22 2017

Formula

As a number triangle, this is T(n, k) = if(k <= n, C(2*n - k, n), 0). Its row sums are C(2*n + 1, n + 1) = A001700. Its diagonal sums are A176287. - Paul Barry, Apr 23 2005
G.f. of column k: 2^k/[sqrt(1 - 4*x)*(1 + sqrt(1 - 4*x))^k].
As a number triangle, this is the Riordan array (1/sqrt(1 - 4*x), x*c(x)), c(x) the g.f. of A000108. - Paul Barry, Jun 24 2005
G.f.: A(x,y)=1/sqrt(1 - 4*x)/(1-y*x*C(x)), where C(x) is g.f. of Catalan numbers. - Vladimir Kruchinin, Mar 19 2016

Extensions

Diagonal sums comment corrected by Paul Barry, Apr 14 2010
Offset corrected by R. J. Mathar, Feb 08 2013

A059481 Triangle read by rows. T(n, k) = binomial(n+k-1, k) for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 6, 10, 1, 4, 10, 20, 35, 1, 5, 15, 35, 70, 126, 1, 6, 21, 56, 126, 252, 462, 1, 7, 28, 84, 210, 462, 924, 1716, 1, 8, 36, 120, 330, 792, 1716, 3432, 6435, 1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, 1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92378
Offset: 0

Views

Author

Fabian Rothelius, Feb 04 2001

Keywords

Comments

T(n,k) is the number of ways to distribute k identical objects in n distinct containers; containers may be left empty.
T(n,k) is the number of nondecreasing functions f from {1,...,k} to {1,...,n}. - Dennis P. Walsh, Apr 07 2011
Coefficients of Faber polynomials for function x^2/(x-1). - Michael Somos, Sep 09 2003
Consider k-fold Cartesian products CP(n,k) of the vector A(n)=[1,2,3,...,n].
An element of CP(n,k) is a n-tuple T_t of the form T_t=[i_1,i_2,i_3,...,i_k] with t=1,...,n^k.
We count members T of CP(n,k) which satisfy some condition delta(T_t), so delta(.) is an indicator function which attains values of 1 or 0 depending on whether T_t is to be counted or not; the summation sum_{CP(n,k)} delta(T_t) over all elements T_t of CP produces the count.
For the triangle here we have delta(T_t) = 0 if for any two i_j, i_(j+1) in T_t one has i_j > i_(j+1), T(n,k) = Sum_{CP(n,k)} delta(T_t) = Sum_{CP(n,k)} delta(i_j > i_(j+1)).
The indicator function which tests on i_j = i_(j+1) generates A158497, which contains further examples of this type of counting.
Triangle of the numbers of combinations of k elements with repetitions from n elements {1,2,...,n} (when every element i, i=1,...,n, appears in a k-combination either 0, or 1, or 2, ..., or k times). - Vladimir Shevelev, Jun 19 2012
G.f. for Faber polynomials is -log(-t*x-(1-sqrt(1-4*t))/2+1)=sum(n>0, T(n,k)*t^k/n). - Vladimir Kruchinin, Jul 04 2013
Values of complete homogeneous symmetric polynomials with all arguments equal to 1, or, equivalently, the number of monomials of degree k in n variables. - Tom Copeland, Apr 07 2014
Row k >= 0 of the infinite square array A[k,n] = C(n,k), n >= 0, would start with k zeros in front of the first nonzero element C(k,k) = 1; this here is the triangle obtained by taking the first k+1 nonzero terms C(k .. 2k, k) of rows k = 0, 1, 2, ... of that array. - M. F. Hasler, Mar 05 2017

Examples

			The triangle T(n,k), n >= 0, 0 <= k <= n, begins
  1      A000217
  1 1   /     A000292
  1 2  3    /    A000332
  1 3  6  10    /    A000389
  1 4 10  20  35    /     A000579
  1 5 15  35  70 126     /
  1 6 21  56 126 252  462
  1 7 28  84 210 462  924 1716
  1 8 36 120 330 792 1716 3432 6435
.
T(3,2)=6 considers the CP with the 3^2=9 elements (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3), and does not count the 3 of them which are (2,1),(3,1) and (3,2).
T(3,3) = 10 because the ways to distribute the 3 objects into the three containers are: (3,0,0) (0,3,0) (0,0,3) (2,1,0) (1,2,0) (2,0,1) (1,0,2) (0,1,2) (0,2,1) (1,1,1), for a total of 10 possibilities.
T(3,3)=10 since (x^2/(x-1))^3 = (x+1+1/x+O(1/x^2))^3 = x^3+3x^2+6x+10+O(x).
T(4,2)=10 since there are 10 nondecreasing functions f from {1,2} to {1,2,3,4}. Using <f(1),f(2)> to denote such a function, the ten functions are <1,1>, <1,2>, <1,3>, <1,4>, <2,2>, <2,3>, <2,4>, <3,3>, <3,4>, and <4,4>. - _Dennis P. Walsh_, Apr 07 2011
T(4,0) + T(4,1) + T(4,2) + T(4,3) = 1 + 4 + 10 + 20 = 35 = T(4,4). - _Jonathan Sondow_, Jun 28 2014
From _Paul Curtz_, Jun 18 2018: (Start)
Consider the array
2,    1,    1,    1,    1,    1,     ... = A054977(n)
1,    1/2,  1/3,  1/4,  1/5,  1/6,   ... = 1/(n+1) = 1/A000027(n)
1/3,  1/6,  1/10, 1/15, 1/21, 1/28,  ... = 2/((n+2)*(n+3)) = 1/A000217(n+2)
1/10, 1/20, 1/35, 1/56, 1/84, 1/120, ... = 6/((n+3)*(n+4)*(n+5)) =1/A000292(n+2) (see the triangle T(n,k)).
Every row is an autosequence of the second kind. (See OEIS Wiki, Autosequence.)
By decreasing antidiagonals the denominator of the array is a(n).
Successive vertical denominators: A088218(n), A000984(n), A001700(n), A001791(n+1), A002054(n), A002694(n).
Successive diagonal denominators: A165817(n), A005809(n), A045721(n), A025174(n+1), A004319(n). (End)
Without the first row (2, 1, 1, 1, ... ), the array leads to A165257(n) instead of a(n). - _Paul Curtz_, Jun 19 2018

References

  • R. Grimaldi, Discrete and Combinatorial Mathematics, Addison-Wesley, 4th edition, chapter 1.4.

Links

Crossrefs

Columns: T(n,1) = A000027(n), n >= 1. T(n,2) = A000217(n) = A161680(n+1), n >= 2. T(n,3) = A000292(n), n >= 3. T(n,4) = A000332(n+3), n >= 4. T(n,5) = A000389(n+4), n >= 5. T(n,6) = A000579(n+5), n >=6. T(n,k) = A001405(n+k-1) for k <= n <= k+2. [Corrected and extended by M. F. Hasler, Mar 05 2017]
Rows: T(5,k) = A000332(k+4). T(6,k) = A000389(k+5). T(7,k) = A000579(k+6).
Diagonals: T(n,n) = A001700(n-1). T(n,n-1) = A000984(n-1).
T(n,k) = A046899(n-1,k). - R. J. Mathar, Mar 26 2009
Take Pascal's triangle A007318, delete entries to the right of a vertical line just right of center, then scan the diagonals.
For a signed version of this triangle see A027555.
Row sums give A000984.
Cf. A007318, A158497, A100100 (mirrored), A009766.
A000984, A001700, A001791, A002054, A002694, A004319, A005809, A025174, A045721, A088218, A165817, A054977, A165257, A000027, A000217, A006134 (trace of the symmetric Pascal matrix).

Programs

  • GAP
    Flat(List([0..10], n->List([0..n], k->Binomial(n+k-1, k)))); # Stefano Spezia, Oct 30 2018
  • Haskell
    a059481 n k = a059481_tabl !! n !! n
a059481_row n = a059481_tabl !! n
a059481_tabl = map reverse a100100_tabl
-- Reinhard Zumkeller, Jan 15 2014
  • Magma
    &cat [[&*[ Binomial(n+k-1,k)]: k in [0..n]]: n in [0..30] ]; // Vincenzo Librandi, Apr 08 2011
  • Maple
    for n from 0 to 10 do for k from 0 to n do print(binomial(n+k-1,k)) ; od: od: # R. J. Mathar, Mar 31 2009
  • Mathematica
    t[n_, k_] := Binomial[n+k-1, k]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 09 2013 *)
(* The combinatorial objects defined in the first comment can, for n >= 1, be generated by: *) r[n_, k_] := FrobeniusSolve[ConstantArray[1,n],k]; (* Peter Luschny, Jan 24 2019 *)
  • Maxima
    sjoin(v, j) := apply(sconcat, rest(join(makelist(j, length(v)), v)))$ display_triangle(n) := for i from 0 thru n do disp(sjoin(makelist(binomial(i+j-1, j), j, 0, i), " ")); display_triangle(10); /* triangle output */ /* Stefano Spezia, Oct 30 2018 */
  • PARI
    {T(n, k) = binomial( n+k-1, k)}; \\ Michael Somos, Sep 09 2003, edited by M. F. Hasler, Mar 05 2017
  • PARI
    {T(n, k) = if( n<0, 0, polcoeff( Pol(((1 / (x - x^2) + x * O(x^n))^n + O(x)) * x^n), k))}; /* Michael Somos, Sep 09 2003 */
  • Sage
    [[binomial(n+k-1,k) for k in range(n+1)] for n in range(11)] # G. C. Greubel, Nov 21 2018

Formula

T(n,0) + T(n,1) + . . . + T(n,n-1) = T(n,n). - Jonathan Sondow, Jun 28 2014
From Peter Bala, Jul 21 2015: (Start)
T(n, k) = Sum_{j = k..n} (-1)^(k+j)*binomial(2*n,n+j)*binomial(n+j-1,j)* binomial(j,k) (gives the correct value T(n,k) = 0 for k > n).
O.g.f.: 1/2*( x*(2*x - 1)/(sqrt(1 - 4*t*x)*(1 - x - t)) + (1 + 2*x)/sqrt(1 - 4*t*x) + (1 - t)/(1 - x - t) ) = 1 + (1 + t)*x + (1 + 2*t + 3*t^2)*x^2 + (1 + 3*t + 6*t^2 + 10*t^3)*x^3 + ....
n-th row polynomial R(n,t) = [x^n] ( (1 + x)^2/(1 + x(1 - t)) )^n.
exp( Sum_{n >= 1} R(n,t)*x^n/n ) = 1 + (1 + t)*x + (1 + 2*t + 2*t^2)*x^2 + (1 + 3*t + 5*t^2 + 5*t^3)*x^3 + ... is the o.g.f for A009766. (End)
a(n) = abs(A027555(n)). - M. F. Hasler, Mar 05 2017
For n >= k > 0, T(n, k) = Sum_{j=1..n} binomial(k + j - 2, k - 1) = Sum_{j=1..n} A007318(k + j - 2, k - 1). - Stefano Spezia, Oct 30 2018
T(n, k) = RisingFactorial(n, k) / k!. - Peter Luschny, Nov 24 2023

Extensions

Offset changed from 1 to 0 by R. J. Mathar, Jan 15 2013
Edited by M. F. Hasler, Mar 05 2017

A091894 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k ddu's [here u = (1,1) and d = (1,-1)].

Original entry on oeis.org

1, 1, 2, 4, 1, 8, 6, 16, 24, 2, 32, 80, 20, 64, 240, 120, 5, 128, 672, 560, 70, 256, 1792, 2240, 560, 14, 512, 4608, 8064, 3360, 252, 1024, 11520, 26880, 16800, 2520, 42, 2048, 28160, 84480, 73920, 18480, 924, 4096, 67584, 253440, 295680, 110880, 11088, 132
Offset: 0

Views

Author

Emeric Deutsch, Mar 10 2004

Keywords

Comments

Number of Dyck paths of semilength n, having k uu's with midpoint at even height. Example: T(4,1) = 6 because we have u(uu)duddd, u(uu)udddd, udu(uu)ddd, u(uu)dddud, u(uu)ddudd and uud(uu)ddd [here u = (1,1), d = (1,-1) and the uu's with midpoint at even height are shown between parentheses]. Row sums are the Catalan numbers (A000108). T(2n+1,n) = A000108(n) (the Catalan numbers). Sum_{k>=0} k*T(n,k) = binomial(2n-2,n-3) = A002694(n-1).
Sometimes called the Touchard distribution (after Touchard's Catalan number identity). T(n,k) = number of full binary trees on 2n edges with k deep interior vertices (deep interior means you have to traverse at least 2 edges to reach a leaf) = number of binary trees on n-1 edges with k vertices having a full complement of 2 children. - David Callan, Jul 19 2004
From David Callan, Oct 25 2004: (Start)
T(n,k) = number of ordered trees on n edges with k prolific edges. A prolific edge is one whose child vertex has at least two children. For example with n=3, drawing ordered trees down from the root, /|\ has no prolific edge and the only tree with one prolific edge has the shape of an inverted Y, so T(3,1)=1.
Proof: Consider the following bijection, recorded by Emeric Deutsch, from ordered trees on n edges to Dyck n-paths. For a given ordered tree, traverse the tree in preorder (walk-around from root order). To each node of outdegree r there correspond r upsteps followed by 1 downstep; nothing corresponds to the last leaf. This bijection sends prolific edges to noninitial ascents of length >=2, that is, to DUU's. Then reverse the resulting Dyck n-path so that prolific edges correspond to DDU's. (End)
T(n,k) is the number of Łukasiewicz paths of length n having k fall steps (1,-1) that start at an even level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1) = 1 because we have U(2)(D)D, where U(2) = (1,2), D = (1,-1) and the fall steps that start at an even level are shown between parentheses. Row n contains ceiling(n/2) terms (n >= 1). - Emeric Deutsch, Jan 06 2005
Number of binary trees with n-1 edges and k+1 leaves (a binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child). - Emeric Deutsch, Jul 31 2006
Number of full binary trees with 2n edges and k+1 vertices both children of which are leaves (n >= 1; a full binary tree is a rooted tree in which each vertex has either 0 or two children). - Emeric Deutsch, Dec 26 2006
Number of ordered trees with n edges and k jumps. In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007
It is remarkable that we can generate the coefficients of the right hand columns of triangle A175136 with the aid of the coefficients in the rows of the triangle given above. See A175136 for more information. - Johannes W. Meijer, May 06 2011
The antidiagonal sums equal A152225. - Johannes W. Meijer, Sep 13 2012
This array also counts 231-avoiding permutations according to the number of peaks, i.e., positions w[i-1] < w[i] > w[i+1]. For example, 123, 213, 312, and 321 have no peaks, while 132 has one peak. Note also T(n,k) = 2^(n - 1 - 2*k)*A055151(n-1,k). - Kyle Petersen, Aug 02 2013

Examples

			T(4,1) = 6 because we have uduu(ddu)d, uu(ddu)dud, uuu(ddu)dd, uu(ddu)udd, uudu(ddu)d and uuud(ddu)d [here u = (1,1), d = (1,-1) and the ddu's are shown between parentheses].
Triangle begins:
    1;
    1;
    2;
    4,    1;
    8,    6;
   16,   24,    2;
   32,   80,   20;
   64,  240,  120,   5;
  128,  672,  560,  70;
  256, 1792, 2240, 560, 14;
  ...

References

  • T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 4.3.

Links

Crossrefs

The first few columns equal A011782, A001788, 2*A003472, 5*A002409, 14*A140325 and 42*A172242. - Johannes W. Meijer, Sep 13 2012
Cf. A000108, A002694, A127529, A236406, A097610, A125181, A133156, A134264, A207538.

Programs

  • GAP
    T:=Concatenation([1],Flat(List([1..13],n->List([0..Int((n-1)/2)],k->2^(n-2*k-1)*Binomial(n-1,2*k)*Binomial(2*k,k)/(k+1))))); # Muniru A Asiru, Nov 29 2018
  • Maple
    a := proc(n,k) if n=0 and k=0 then 1 elif n=0 then 0 else 2^(n-2*k-1)*binomial(n-1,2*k)*binomial(2*k,k)/(k+1) fi end: 1,seq(seq(a(n,k),k=0..(n-1)/2),n=1..15);
  • Mathematica
    A091894[n_] := Prepend[Table[ CoefficientList[ 2^i (1 - z)^((2 i + 3)/2) Hypergeometric2F1[(i + 3)/2, (i + 4)/2, 2, z], z], {i, 0, n}], {1}] (* computes a table of the first n rows. Stumbled accidentally on it. Perhaps someone can find a relationship here? Thies Heidecke (theidecke(AT)astrophysik.uni-kiel.de), Sep 23 2008 *)
Join[{1},Select[Flatten[Table[2^(n-2k-1) Binomial[n-1,2k] Binomial[2k,k]/ (k+1), {n,20},{k,0,n}]],#!=0&]] (* Harvey P. Dale, Mar 05 2012 *)
p[n_] := 2^n Hypergeometric2F1[(1 - n)/2, -n/2, 2, x]; Flatten[Join[{{1}}, Table[CoefficientList[p[n], x], {n, 0, 12}]]] (* Peter Luschny, Jan 23 2018 *)
  • PARI
    {T(n, k) = if( n<1, n==0 && k==0, polcoeff( polcoeff( serreverse( x / (1 + 2*x*y + x^2) + x * O(x^n)), n), n-1 - 2*k))} /* Michael Somos, Sep 25 2006 */
  • Sage
    [1] + [[2^(n-2*k-1)*binomial(n-1,2*k)*binomial(2*k,k)/(k+1) for k in (0..floor((n-1)/2))] for n in (1..12)] # G. C. Greubel, Nov 30 2018

Formula

T(n,k) = 2^(n - 2*k - 1)*binomial(n-1,2*k)*binomial(2*k,k)/(k + 1), T(0,0) = 1, for 0 <= k <= floor((n-1)/2).
G.f.: G = G(t,z) satisfies: t*z*G^2 - (1 - 2*z + 2*t*z)*G + 1 - z + t*z = 0.
With first row zero, the o.g.f. is g(x,t) = (1 - 2*x - sqrt((1 - 2*x)^2 - 4*t*x^2)) / (2*t*x) with the inverse ginv(x,t) = x / (1 + 2*x + t*x^2), an o.g.f. for shifted A207538 and A133156 mod signs, so A134264 and A125181 can be used to interpret the polynomials of this entry. Cf. A097610. - Tom Copeland, Feb 08 2016
If we delete the first 1 from the data these are the coefficients of the polynomials p(n) = 2^n*hypergeom([(1 - n)/2, - n/2], [2], x). - Peter Luschny, Jan 23 2018

A100100 Triangle T(n,k) = binomial(2*n-k-1, n-k) read by rows.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 10, 6, 3, 1, 35, 20, 10, 4, 1, 126, 70, 35, 15, 5, 1, 462, 252, 126, 56, 21, 6, 1, 1716, 924, 462, 210, 84, 28, 7, 1, 6435, 3432, 1716, 792, 330, 120, 36, 8, 1, 24310, 12870, 6435, 3003, 1287, 495, 165, 45, 9, 1, 92378, 48620, 24310, 11440, 5005, 2002
Offset: 0

Views

Author

Paul Barry, Nov 08 2004

Keywords

Comments

Sometimes called a Catalan triangle, although there are many other triangles that carry that name - see A009766, A008315, A028364, A033184, A053121, A059365, A062103.
Number of nodes of outdegree k in all ordered trees with n edges. Equivalently, number of ascents of length k in all Dyck paths of semilength n. Example: T(3,2) = 3 because the Dyck paths of semilength 3 are UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and UUUDDD, where U = (1,1), D = (1,-1), the ascents of length 2 being shown between parentheses. - Emeric Deutsch, Nov 19 2006
Riordan array (f(x), x*g(x)) where f(x) is the g.f. of A088218 and g(x) is the g.f. of A000108. - Philippe Deléham, Jan 23 2010
T(n,k) is the number of nonnegative paths of upsteps U = (1,1) and downsteps D = (1,-1) of length 2*n with k returns to ground level, the horizontal line through the initial vertex. Example: T(2,1) = 2 counts UDUU, UUDD. Also, T(n,k) = number of these paths whose last descent has length k, that is, k downsteps follow the last upstep. Example: T(2,1) = 2 counts UUUD, UDUD. - David Callan, Nov 21 2011
Belongs to the hitting-time subgroup of the Riordan group. Multiplying this triangle by the square Pascal matrix gives A092392 read as a square array. See the example below. - Peter Bala, Nov 03 2015

Examples

			From _Paul Barry_, Mar 15 2010: (Start)
Triangle begins in row n=0 with columns 0<=k<=n as:
    1;
    1,   1;
    3,   2,   1;
   10,   6,   3,  1;
   35,  20,  10,  4,  1;
  126,  70,  35, 15,  5, 1;
  462, 252, 126, 56, 21, 6, 1;
Production matrix begins
  1, 1;
  2, 1, 1;
  3, 1, 1, 1;
  4, 1, 1, 1, 1;
  5, 1, 1, 1, 1, 1;
  6, 1, 1, 1, 1, 1, 1;
  7, 1, 1, 1, 1, 1, 1, 1;
(End)
A092392 as a square array = A100100 * square Pascal matrix:
/1   1  1  1 ...\   / 1          \/1 1  1  1 ...\
|2   3  4  5 ...|   | 1 1        ||1 2  3  4 ...|
|6  10 15 21 ...| = | 3 2 1      ||1 3  6 10 ...|
|20 35 56 84 ...|   |10 6 3 1    ||1 4 10 20 ...|
|70 ...         |   |35 ...      ||1 ...        |
- _Peter Bala_, Nov 03 2015

Links

Crossrefs

Row sums are A000984. Equivalent to A092392, to which A088218 has been added as a first column. Columns include A088218, A000984, A001700, A001791, A002054, A002694. Diagonal sums are A100217. Matrix inverse is A100218.
Cf. A059481 (mirrored). Cf. A033184, A094527, A113955.

Programs

  • Haskell
    a100100 n k = a100100_tabl !! n !! n
a100100_row n = a100100_tabl !! n
a100100_tabl = [1] : f a092392_tabl where
   f (us : wss'@(vs : wss)) = (vs !! 1 : us) : f wss'
-- Reinhard Zumkeller, Jan 15 2014
  • Magma
    /* As triangle */ [[Binomial(2*n - k - 1, n - k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Nov 21 2018
  • Maple
    A100100 := proc(n,k)
    binomial(2*n-k-1,n-1) ;
end proc:
seq(seq(A100100(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Feb 06 2015
  • Mathematica
    Flatten[Table[Binomial[2 n - k - 1, n - k], {n, 0, 11}, {k, 0, n}]] (* Vincenzo Librandi, Nov 21 2018 *)
  • PARI
    T(n,k)=binomial(2*n-k-1,n-k) \\ Charles R Greathouse IV, Jan 16 2012

Formula

From Peter Bala, Sep 06 2015: (Start)
Matrix product A094527 * P^(-1) = A113955 * P^(-2), where P denotes Pascal's triangle A007318.
Essentially, the logarithmic derivative of A033184. (End)
Let column(k) = [T(n, k), n >= k], then the generating function for column(k) is (2/(sqrt(1-4*x)+1))^(k-1)/sqrt(1-4*x). - Peter Luschny, Mar 19 2021
O.g.f. row polynomials R(n, x) := Sum_{k=0..n} T(n, k)*x^k, i.e. o.g.f. of the triangle, G(z,x) = 1/((2 - c(z))*(1 - x*z*c(z))), with c the o.g.f. of A000108 (Catalan). See the Riordan coomment by Philippe Deléham above. - Wolfdieter Lang, Apr 06 2021

A062264 Coefficient triangle of certain polynomials N(4; m,x).

Original entry on oeis.org

1, 1, 5, 1, 12, 15, 1, 21, 63, 35, 1, 32, 168, 224, 70, 1, 45, 360, 840, 630, 126, 1, 60, 675, 2400, 3150, 1512, 210, 1, 77, 1155, 5775, 11550, 9702, 3234, 330, 1, 96, 1848, 12320, 34650, 44352, 25872, 6336, 495, 1, 117, 2808, 24024, 90090, 162162, 144144, 61776, 11583, 715
Offset: 0

Views

Author

Wolfdieter Lang, Jun 19 2001

Keywords

Comments

The e.g.f. of the m-th (unsigned) column sequence without leading zeros of the generalized (a=4) Laguerre triangle L(4; n+m,m) = A062140(n+m,m), n >= 0, is N(4; m,x)/(1-x)^(5+2*m), with the row polynomials N(4; m,x) := Sum_{k=0..m} T(m,k)*x^k.

Examples

			Triangle begins as:
  1;
  1,   5;
  1,  12,   15;
  1,  21,   63,    35;
  1,  32,  168,   224,     70;
  1,  45,  360,   840,    630,    126;
  1,  60,  675,  2400,   3150,   1512,    210;
  1,  77, 1155,  5775,  11550,   9702,   3234,    330;
  1,  96, 1848, 12320,  34650,  44352,  25872,   6336,    495;
  1, 117, 2808, 24024,  90090, 162162, 144144,  61776,  11583,   715;
  1, 140, 4095, 43680, 210210, 504504, 630630, 411840, 135135, 20020, 1001;

Links

Crossrefs

Family of polynomials (see A062145): A008459 (c=1), A132813 (c=2), A062196 (c=3), A062145 (c=4), this sequence (c=5), A062190 (c=6).
Columns: A028347 (k=2), A104473 (k=3), A104474 (k=4), A104475 (k=5), A027814 (k=6), A103604 (k=7), A104476 (k=8), A104478 (k=9).
Diagonals: A000332 (k=n), A027810 (k=n-1), A105249 (k=n-2), A105250 (k=n-3), A105251 (k=n-4), A105252 (k=n-5), A105253 (k=n-6), A105254 (k=n-7).
Sums: A002694 (row).

Programs

  • Magma
    A062264:= func< n,k | Binomial(n,k)*Binomial(n+4,k) >;
[A062264(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Mar 03 2025
  • Mathematica
    A062264[n_, k_]:= Binomial[n,k]*Binomial[n+4,k];
Table[A062264[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Mar 03 2025 *)
  • SageMath
    def A062264(n,k): return binomial(n,k)*binomial(n+4,k)
print(flatten([[A062264(n,k) for k in range(n+1)] for n in range(13)])) # G. C. Greubel, Mar 03 2025

Formula

T(m, k) = [x^k] N(4; m, x), with N(4; m, x) = ((1-x)^(2*m+5))*(d^m/dx^m)((x^m)/(m!*(1-x)^(m+5))).
N(4; m, x) = Sum_{j=0..m} (binomial(m, j)*(2*m+4-j)!/((m+4)!*(m-j)!)*(x^(m-j))*(1-x)^j).
From G. C. Greubel, Mar 03 2025: (Start)
T(n, k) = binomial(n,k)*binomial(n+4,k).
Sum_{k=0..n} (-1)^k*T(n, k) = (1/4)*( (1+(-1)^n)*(-1)^((n+2)/2)*(n^2 + 5*n - 2)*Catalan((n+2)/2)/(n+1) + 8*(1-(-1)^n)*(-1)^((n+1)/2)*Catalan((n+1)/2) ). (End)

A003516 Binomial coefficients C(2n+1, n-2).

Original entry on oeis.org

1, 7, 36, 165, 715, 3003, 12376, 50388, 203490, 817190, 3268760, 13037895, 51895935, 206253075, 818809200, 3247943160, 12875774670, 51021117810, 202112640600, 800472431850, 3169870830126, 12551759587422
Offset: 2

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the number of royal paths (A006318) from (0,0) to (n,n) with exactly one diagonal step off the line y=x. - David Callan, Mar 25 2004
a(n) is the total number of DDUU's in all Dyck (n+2)-paths. - David Scambler, May 03 2013

Examples

			For n=4, C(2*4+1,4-2) = C(9,2) = 9*8/2 = 36, so a(4) = 36. - _Michael B. Porter_, Sep 10 2016

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Diagonal 6 of triangle A100257.
Third unsigned column (s=2) of A113187. - Wolfdieter Lang, Oct 18 2012
Cf. triangle A114492 - Dyck paths with k DDUU's.
Cf. A001622, A115139.
Cf. binomial(2*n+m, n): A000984 (m = 0), A001700 (m = 1), A001791 (m = 2), A002054 (m = 3), A002694 (m = 4), A002696 (m = 6), A030053 - A030056, A004310 - A004318.

Programs

  • GAP
    List([2..25], n-> Binomial(2*n+1, n-2)); # G. C. Greubel, Mar 21 2019
  • Magma
    [Binomial(2*n+1,n-2): n in [2..25]]; // Vincenzo Librandi, Apr 13 2011
  • Mathematica
    CoefficientList[ Series[ 32/(((Sqrt[1 - 4 x] + 1)^5)*Sqrt[1 - 4 x]), {x, 0, 25}], x] (* Robert G. Wilson v, Aug 08 2011 *)
Table[Binomial[2*n +1,n-2], {n,2,25}] (* G. C. Greubel, Jan 23 2017 *)
  • PARI
    {a(n) = binomial(2*n+1, n-2)}; \\ G. C. Greubel, Mar 21 2019
  • Sage
    [binomial(2*n+1, n-2) for n in (2..25)] # G. C. Greubel, Mar 21 2019

Formula

G.f.: 32*x^2/(sqrt(1-4*x)*(sqrt(1-4*x)+1)^5). - Marco A. Cisneros Guevara, Jul 18 2011
a(n) = Sum_{k=0..n-2} binomial(n+k+2,k). - Arkadiusz Wesolowski, Apr 02 2012
D-finite with recurrence (n+3)*(n-2)*a(n) = 2*n*(2*n+1)*a(n-1). - R. J. Mathar, Oct 13 2012
G.f.: x^2*c(x)^5/sqrt(1-4*x) = ((-1 + 2*x) + (1 - 3*x + x^2) * c(x))/(x^2*sqrt(1-4*x)), with c(x) the o.g.f. of the Catalan numbers A000108. See the W. Lang link under A115139 for powers of c. - Wolfdieter Lang, Sep 10 2016
a(n) ~ 2^(2*n+1)/sqrt(Pi*n). - Ilya Gutkovskiy, Sep 10 2016
From Amiram Eldar, Jan 24 2022: (Start)
Sum_{n>=2} 1/a(n) = 4 - 14*Pi/(9*sqrt(3)).
Sum_{n>=2} (-1)^n/a(n) = 228*log(phi)/(5*sqrt(5)) - 134/15, where phi is the golden ratio (A001622). (End)
G.f.: 2F1([7/2,3],[6],4*x). - Karol A. Penson, Apr 24 2024
a(n) = Integral_{x = 0..4} x^n * w(x) dx, where the weight function w(x) = 1/(2*Pi) * sqrt(x)*(x^2 - 5*x + 5)/sqrt(4 - x). - Peter Bala, Oct 13 2024

A100257 Triangle of expansions of 2^(k-1)*x^k in terms of T(n,x), in descending degrees n of T, with T the Chebyshev polynomials.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 4, 0, 3, 1, 0, 5, 0, 10, 0, 1, 0, 6, 0, 15, 0, 10, 1, 0, 7, 0, 21, 0, 35, 0, 1, 0, 8, 0, 28, 0, 56, 0, 35, 1, 0, 9, 0, 36, 0, 84, 0, 126, 0, 1, 0, 10, 0, 45, 0, 120, 0, 210, 0, 126, 1, 0, 11, 0, 55, 0, 165, 0, 330, 0, 462, 0, 1, 0, 12, 0, 66, 0, 220, 0
Offset: 0

Views

Author

Ralf Stephan, Nov 13 2004

Keywords

Examples

			x^0 = T(0,x)
x^1 = T(1,x) + 0T(0,x)
2x^2 = T(2,x) + 0T(1,x) + 1T(0,x)
4x^3 = T(3,x) + 0T(2,x) + 3T(1,x) + 0T(0,x)
8x^4 = T(4,x) + 0T(3,x) + 4T(2,x) + 0T(1,x) + 3T(0,x)
16x^5 = T(5,x) + 0T(4,x) + 5T(3,x) + 0T(2,x) + 10T(1,x) + 0T(0,x)

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 795.

Links

Crossrefs

Without zeros: A008311. Row sums are A011782. Cf. A092392.
Diagonals are (with interleaved zeros) twice A001700, A001791, A002054, A002694, A003516, A002696, A030053, A004310, A030054, A004311, A030055, A004312, A030056, A004313.

Programs

  • Mathematica
    a[k_, n_] := If[k == 1, 1, If[EvenQ[n] || k < 0 || n > k, 0, If[n >= k - 1, Binomial[2*Floor[k/2], Floor[k/2]]/2, Binomial[k - 1, Floor[n/2]]]]];
Table[a[k, n], {k, 1, 13}, {n, 1, k}] // Flatten (* Jean-François Alcover, May 04 2017, translated from PARI *)
  • PARI
    a(k,n)=if(k==1,1,if(n%2==0||k<0||n>k,0,if(n>=k-1,binomial(2*floor(k/2),floor(k/2))/2,binomial(k-1,floor(n/2)))))
Showing 1-10 of 40 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.