0,2

To show for example that C(2n+1, n+1) is the number of monotone maps from 1..n+1 to 1..n+1, notice that we can describe such a map by a nondecreasing sequence of length n+1 with entries from 1 to n+1. The number k of increases in this sequence is anywhere from 0 to n. We can specify these increases by throwing k balls into n+1 boxes, so the total is Sum_{k=0..n} C((n+1)+k-1, k) = C(2n+1, n+1).

Also number of ordered partitions (or compositions) of n+1 into n+1 parts. E.g. a(2)=10: 003 030 300 012 021 102 120 210 201 111 - Mambetov Bektur (bektur1987(AT)mail.ru), Apr 17 2003

Also number of walks of length n on square lattice, starting at origin, staying in first and second quadrants - David W. Wilson (davidwwilson(AT)comcast.net), May 05, 2001. E.g. for n = 2 there are 10 walks, all starting at 0,0: 0,1->0,0; 0,1->1,1; 0,1->0,2; 1,0->0,0; 1,0->1,1; 1,0->2,0; 1,0->1,-1; -1,0->0,0; -1,0->-1,1; -1,0->-2,0.

Also total number of leaves in all ordered trees with n+1 edges.

Also number of digitally balanced numbers [A031443] from 2^(2n+1) to 2^(2n+2). - Naohiro Nomoto (6284968128(AT)geocities.co.jp), Apr 07 2001

Also number of ordered trees with 2n+2 edges having root of even degree and nonroot nodes of outdegree 0 or 2. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 02 2002

Also number of paths of length 2*d(G) connecting two neighboring nodes in optimal chordal graph of degree 4, G(2*d(G)^2+2*d(G)+1, 2d(G)+1), where d(G) = diameter of graph G. - S. Bujnowski (slawb(AT)atr.bydgoszcz.pl), Feb 11 2002

Define an array by m(1,j)=1, m(i,1)=i, m(i,j)=m(i,j-1)+m(i-1,j); then a(n)=m(n,n) - Benoit Cloitre (benoit7848c(AT)orange.fr), May 07 2002

Also the numerator of the constant term in the expansion of Cos^2n(x) or Sin^2n(x) when the denominator is 2^(2n-1). - rgwv

Consider the expansion of cos^n(x) as a linear combination of cosines of multiple angles. If n is odd, then the expansion is a combination of a*cos((2k-1)*x)/2^(n-1) for all 2k-1<=n. If n is even, then the expansion is a combination of a*cos(2k*x)/2^(n-1) terms plus a constant. "The constant term, [a(n)/2^(2n-1)], is due to the fact that [cos^2n(x)] is never negative, i.e. electrical engineers would say the average or 'dc value' of [cos^2n(x)] is [a(n)/2^(2n-1)]. The dc value of [cos^(2n-1)(x)] on the other hand, is zero because it is symmetrical about the horizontal axis, i.e. it is negative and positive equally." Nahin[62] - rgwv Aug 01 2002

Also number of times a fixed Dyck word of length 2k occurs in all Dyck words of length 2n+2k. Example: if the fixed Dyck word is xyxy (k=2), then it occurs a(1)=3 times in the 5 Dyck words of length 6 (n=1): (xy[xy)xy], xyxxyy, xxyyxy, x(xyxy)y, xxxyyy (placed between parentheses). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 02 2003

G.f. is C(x)/sqrt(1-4x) where C(x) is g.f. for Catalan numbers A000108.

a(n+1) is the determinant of the n X n matrix m(i,j)=binomial(2n-i,j) - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 26 2003

a(n-1) = (2n)!/(2*n!*n!), formula in [Davenport] used by Gauss for the special case prime p = 4*n+1: x = a(n-1) mod p and y = x*(2n)! mod p are solutions of p = x^2 + y^2. - Frank Ellermann. Example: For prime 29 = 4*7+1 use a(7-1) = 1716 = (2*7)!/(2*7!*7!), 5 = 1716 mod 29 and 2 = 5*(2*7)! mod 29, then 29 = 5*5 + 2*2.

a(n)=sum{k=0..n+1, binomial(2n+2,k)*cos((n-k+1)*pi)} - Paul Barry (pbarry(AT)wit.ie), Nov 02 2004

The number of compositions of 2n, say c_1+c_2+...c_k=2n, satisfy that Sum_(i=1..j)c_i <2j for all j=1..k, or equivalently, the number of subsets, say S, of [2n-1]={1,2,...2n-1} with at least n elements such that if 2k is in S, then there must be at least k elements in S smaller than 2k. E.g. a(2)=3 because we can write 4=1+1+1+1=1+1+2=1+2+1 - Ricky X. F. Chen (ricky_chen(AT)mail.nankai.edu.cn), Jul 30 2006

a(n) = A122366(n,n). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Aug 30 2006

a(n) = A000984+A001791. Example: 1+0=1 2+1=3 6+4=10 20+15=35 70+56=126 etc... - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jan 23 2007

The number of walks of length 2n+1 on an infinite linear lattice that begin at the origin and end at node (1). Also the number of paths on a square lattice from the origin to (n+1,n) that use steps (1,0) and (0,1). Also number of binary numbers of length 2n+1 with n+1 1's and n 0's. - Stefan Hollos (stefan(AT)exstrom.com), Dec 10 2007

If Y is a 3-subset of an 2n-set X then, for n>=3, a(n-1) is the number of n-subsets of X having at least two elements in common with Y. - Milan R. Janjic (agnus(AT)blic.net), Dec 16 2007

Also the number of rankings (preferential arrangements) of n unlabeled elements onto n levels when empty levels are allowed. - Thomas Wieder (thomas.wieder(AT)t-online.de), May 24 2008

Also the Catalan transform of A000225 shifted one index, ie, dropping A000225(0). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 11 2008]

With offset 1. The number of solutions in nonnegative integers to X1+X2+...+Xn=n. The number of terms in the expansion of (X1+X2+...+Xn)^n. The coefficient of x^n in the expansion of (1+x+x^2+...)^n. The number of distinct image sets of all functions taking [n]into[n]. [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Feb 22 2009]

The Hankel transform of the aerated sequence 1,0,3,0,10,0,... is 1,3,3,5,5,7,7,.... (A109613(n+1)). [From Paul Barry (pbarry(AT)wit.ie), Apr 21 2009]

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 15 2009: (Start)

Equals INVERT transform of the Catalan numbers starting with offset 1.

E.g.: a(3) = 35 = (1, 2, 5) dot (10, 3, 1) + 14 = 21 + 14 = 35. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.

E. Barcucci, A. Frosini and S. Rinaldi, On directed-convex polyominoes in a rectangle, Discr. Math., 298 (2005). 62-78.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, preprint, 2007.

M. Bousquet-M\'{e}lou, New enumerative results on two-dimensional directed animals, Discr. Math., 180 (1998), 73-106.

David Callan, A Combinatorial Interpretation for a Super-Catalan Recurrence, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.8.

H. Davenport, The Higher Arithmetic. Cambridge Univ. Press, 7th ed., 1999, ch. V.3 (p. 122).

A. Frosini, R. Pinzani and S. Rinaldi, About half the middle binomial coefficient, Pure Math. Appl., 11 (2000), 497-508.

Charles Jordan, Calculus of Finite Differences, Chelsea 1965, p. 449.

M. D. McIlroy, personal communication.

J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.

Phil J. Nahin, "An Imaginary Tale, The Story of [Sqrt(-1)]," Princeton University Press, Princeton, NJ 1998, pg 62.

Problem 10753, Amer. Math. Monthly, 2000.

T. D. Noe, Table of n, a(n) for n = 0..100

Milan Janjic, Two Enumerative Functions

C. Borcea and I. Streinu, On the number of embeddings of minimally rigid graphs.

M. Bousquet-M\'{e}lou, New enumerative results on two-dimensional directed animals

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 145

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Thomas Wieder, Home Page.

Thomas Wieder, (Old) Home Page.

Index entries for "core" sequences

a(n-1) = binomial(2n, n)/2 = (2n)!/(2*n!*n!).

a(0) = 1, a(n) = 2(2n+1)a(n-1)/(n+1) for n > 0.

G.f.: (1/sqrt(1-4*x)-1)/(2*x).

Convolution of A000108 (Catalan) and A000984 (central binomial): Sum(C(k)*binomial(2*(n-k), n-k), k=0..n), C(k) Catalan [ Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de) ]

a(n) = sum(k=0..n, C(n+k, k)) - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 20 2002

a(n) = sum(k=0..n, C(n, k)*C(n+1, k+1)) - Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 19 2002

a(n) = 4^n*binomial(n+1/2, n)/(n+1); - Paul Barry (pbarry(AT)wit.ie), May 10 2005

E.g.f. Sum_{n>=0} a(n)*x^(2n+1)/(2n+1)! = BesselI(1, 2x) . - Michael Somos Jun 22 2005

E.g.f. in Maple notation: exp(2*x)*(BesselI(0, 2*x)+BesselI(1, 2*x)). Integral representation as n-th moment of a positive function on [0, 4]: a(n)=int(x^n*((x/(4-x))^(1/2)), x=0..4)/(2*Pi), n=0, 1... This representation is unique. - Karol A. Penson (penson(AT)lptl.jussieu.fr), Oct 11 2001

Narayana transform of [1, 2, 3,...]. Let M = the Narayana triangle of A001263 as an infinite lower triangular matrix and V = the Vector [1, 2, 3,...]. Then A001700 = M * V. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 25 2006

a(n) = C(2*n, n) + C(2*n, n-1); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jan 23 2007

a(n) = n*(n+1)*...*(2*n-1)/n! = product of n consecutive integers starting with n, dividied by n!. - Jonathan Vos Post (jvospost3(AT)gmail.com), Apr 09 2007

a(n):=(2n+1)*C(n); - Paul Barry (pbarry(AT)wit.ie), Aug 21 2007

Binomial transform of A005773 starting (1, 2, 5, 13, 35, 96,...) and double binomial transform of A001405. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 01 2007

Row sums of triangle A132813. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 01 2007

Row sums of triangle A134285 - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 19 2007

a(n) = (2n-1)!/(n!*(n-1)!) - William A. Tedeschi (fynmun(AT)hotmail.com), Feb 27 2008

G.f.: F(1,3/2;2;4x). [From Paul Barry (pbarry(AT)wit.ie), Jan 23 2009]

G.f.: 1/(1-2x-x/(1-x/(1-x/(1-x/(1-... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), May 06 2009]

G.f.: c(x)^2/(1-xc(x)^2), c(x) the g.f. of A000108. [From Paul Barry (pbarry(AT)wit.ie), Sep 07 2009]

A001700 := n -> binomial(2*n+1, n+1);

seq((count(Composition(2*n), size=n+1)), n=1..24); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 03 2007

with(combinat):seq(numbcomp(2*i, i), i=1..24) ; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 16 2007

Table[ Binomial[2n + 1, n + 1], {n, 0, 23} ]

(PARI) a(n)=binomial(2*n+1, n+1)

Cf. A030662, A046097, A060897-A060900, A049027, A076025, A076026, A060150, A028364, A050166, A039598, A001263, A005773, A001405, A132813, A134285.

Equals A000984(n+1)/2. Cf. A030662, A046097. a(n)= (n+1)*Catalan(n) [A000108] = A035324(n+1, 1) (first column of triangle).

Row sums of triangles A028364, A050166, A039598.

Bisections: a(2*k)= A002458(k), a(2*k+1)= A001448(k+1)/2, k>=0.

Other versions of the same sequence: A088218, A110556, A138364.

Diagonals 1 and 2 of triangle A100257.

Second row of array A102539.

Column of array A073165.

Sequence in context: A122068 A099908 A167403 this_sequence A088218 A110556 A072266

Adjacent sequences: A001697 A001698 A001699 this_sequence A001701 A001702 A001703

easy,nonn,nice,core

N. J. A. Sloane (njas(AT)research.att.com).