login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001700 C(2n+1, n+1): number of ways to put n+1 indistinguishable balls into n+1 distinguishable boxes = number of (n+1)-st degree monomials in n+1 variables = number of monotone maps from 1..n+1 to 1..n+1.
(Formerly M2848 N1144)
230
1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078, 5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650, 17672631900, 68923264410, 269128937220, 1052049481860, 4116715363800, 16123801841550 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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, 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, 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, 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, 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). - Robert G. Wilson v

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] - Robert G. Wilson v, 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, Jan 02 2003

a(n+1) is the determinant of the n X n matrix m(i,j) = binomial(2n-i,j). - Benoit Cloitre, 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, 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, Aug 30 2006

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 Janjic, Dec 16 2007

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

Also the Catalan transform of A000225 shifted one index, i.e., dropping A000225(0). - R. J. Mathar, 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]. - Geoffrey Critzer, 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)). - Paul Barry, Apr 21 2009

Also the number of unique network topologies for a network of n items with 1 to n-1 unidirectional connections to other objects in the network. - Anthony Bachler, May 05 2010

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. - Gary W. Adamson, May 15 2009

a(n) = 2*A000984(n) - A000108(n), that is, a(n) = 2*c(2n,n) - n-th Catalan number. - Joseph Abate, Jun 11 2010

The integral of 1/(1+x^2)^(n+1) is given by a(n)/2^(2n-1) * (x/(1+x^2)^n*P(x) + arctan(x)), where P(x) is a monic polynomial of degree 2n-2 with rational coefficients. - Christiaan van de Woestijne, Jan 25 2011

a(n) is the number of Schroder paths of semilength n in which the (2,0)-steps at level 0 come in 2 colors and there are no (2,0)-steps at a higher level. Example: a(2)=10 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 2^2 = 4 paths of shape HH, 2 paths of shape HUD, 2 paths of shape UDH, and 1 path of each of the shapes UDUD and UUDD. - Emeric Deutsch, May 02 2011

a(n) is the number of Motzkin paths of length n in which the (1,0)-steps at level 0 come in 3 colors and those at a higher level come in 2 colors. Example: a(3)=35 because, denoting  U=(1,1), H=(1,0), and D=(1,-1), we have 3^3 = 27 paths of shape HHH, 3 paths of shape HUD, 3 paths of shape UDH, and 2 paths of shape UHD. - Emeric Deutsch, May 02 2011

Also number of digitally balanced numbers having length 2*(n+1) in binary representation: a(n) = #{m: A070939(A031443(m))=2*(n+1)}. - Reinhard Zumkeller, Jun 08 2011

a(n) equals 2^(2n+3) times the coefficient of Pi in 2F1(1/2,n+2,3/2,-1). - John M. Campbell, Jul 17 2011

For positive n, a(n) equals 4^(n+2) times the coefficient of Pi^2 in integral_{x=0..Pi/2} x sin^(2n+2)x. - John M. Campbell, Jul 19 2011

a(n-1) = C(2n,n)/2 is the number of ways to assign 2n people into 2 (unlabeled) groups of size n. - Dennis P. Walsh, Nov 09 2011

Equals row sums of triangle A205945. - Gary W. Adamson, Feb 01 2012

a(n-1) gives the number of n-regular sequences defined by Erdős and Gallai in 1960 in connection with the degree sequences of simple graphs. - Matuszka Tamás, Mar 06 2013

a(n) = sum of falling diagonals of squares in the comment of A085812 (equivalent to the Cloitre formula of Aug 2002). - John Molokach, Sep 26 2013

For n > 0: largest terms of Zigzag matrices as defined in A088961. - Reinhard Zumkeller, Oct 25 2013

Also the number of different possible win/loss round sequences (from the perspective of the eventual winner) in a "best of 2n+1" two-player game. For example, a(2) = 10 means there are 10 different win/loss sequences in a "best of 5" game (like a tennis match in which the first player to win 3 sets, out of a maximum of 5, wins the match); the 10 sequences are WWW, WWLW, WWLLW, WLWW, WLWLW, WLLWW, LWWW, LWWLW, LWLWW, LLWWW. See also A072600. - Philippe Beaudoin, May 14 2014; corrected by Jon E. Schoenfield, Nov 23 2014

When adding 1 to the beginning of the sequence: Convolving a(n)/2^n with itself equals 2^(n+1).  For example, when n=4: convolving {1, 1/1, 3/2, 10/4, 35/8, 126/16} with itself = 32 = 2^5. - Bob Selcoe, Jul 16 2014

From Tom Copeland, Nov 09 2014: (Start)

The shifted array belongs to a family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the o.g.f. [1-sqrt(1-4x/(1+(1-t)x))]/2 and inverse x(1-x)/[1+(t-1)x(1-x)]. See A091867 for more info on this family. Here is t=-3 (mod signs in the results).

Let C(x) = [1 - sqrt(1-4x)]/2, an o.g.f. for the Catalans A000108, with inverse Cinv(x) = x*(1-x) and P(x,t) = x/(1+t*x) with inverse P(x,-t).

O.g.f: G(x) = [-1 + sqrt(1 + 4*x/(1-4x))]/2 = -C[P(-x,4)].

Inverse O.g.f: Ginv(x) = x*(1+x)/[1 + 4x*(1+x)] = -P(Cinv(-x),-4) (shifted signed A001792). A088218 = 1+ G(x).

Equals A001813/2 omitting the leading 1 there. (End) 

REFERENCES

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.

T. Mansour, M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.

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.

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

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

T. D. Noe and Matuszka Tamás, Table of n, a(n) for n = 0..1200 (first 100 terms from T. D. Noe)

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, J. Int. Seq. 10 (2007) # 07.9.7

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

M. Bousquet-Mélou, New enumerative results on two-dimensional directed animals, Discr. Math., 180 (1998), 73-106. See Eq. (1). - From N. J. A. Sloane, Jun 03 2012

J.-P. Bultel, S. Giraudo, Combinatorial Hopf algebras from PROs, arXiv preprint arXiv:1406.6903, 2014

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

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

N. Gromov and P. Vieira, Tailoring Three-Point Functions and Integrability IV. Theta-morphism, arXiv preprint arXiv:1205.5288, 2012. - From N. J. A. Sloane, Oct 23 2012

R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6

Guo-Niu Han, Enumeration of Standard Puzzles

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 145

A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapientiae, Informatica, 4, 2 (2012) 260-288.

Milan Janjic, Two Enumerative Functions

Dmitry Kruchinin, Superposition's properties of logarithmic generating functions, arXiv:1109.1683, 2011.

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.

Asamoah Nkwanta and Earl R. Barnes, Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind, Journal of Integer Sequences, Article 12.3.3, 2012. - From N. J. A. Sloane, Sep 16 2012.

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

Louis Shapiro, Problem 10753 Amer. Math. Monthly, Vol. 106, No. 8 (Oct., 1999), p. 777.

Louis Shapiro et al., Leaves of Ordered Trees: 10753, Amer. Math. Monthly, Vol. 108, No. 9 (Nov., 2001), pp. 873-874

Eric Weisstein's World of Mathematics, Binomial Coefficient

Eric Weisstein's World of Mathematics, Odd Graph

Index entries for "core" sequences

FORMULA

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

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

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

L.g.f. log((1-sqrt(1-4*x))/(2*x)) = sum(n>0, a(n)/n*x^n). - Vladimir Kruchinin, Aug 10 2010

G.f.: 2F1(1,3/2;2;4*x). - Paul Barry, Jan 23 2009

G.f.: 1/(1-2x-x/(1-x/(1-x/(1-x/(1-... (continued fraction). - Paul Barry, May 06 2009

G.f.: c(x)^2/(1-x*c(x)^2), c(x) the g.f. of A000108. - Paul Barry, Sep 07 2009

O.g.f.: c(x)/sqrt(1-4*x) = (2 - c(x))/(1-4*x), with c(x) the o.g.f. of A000108. Added second formula. - Wolfdieter Lang, Sep 02 2012

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, Dec 11 1999

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

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

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

E.g.f.: sum(n>=0, a(n)*x^(2*n+1)/(2*n+1)!) = BesselI(1, 2*x). - 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, 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, Apr 25 2006

a(n) = C(2*n, n) + C(2*n, n-1) = A000984(n) + A001791(n). - Zerinvary Lajos, Jan 23 2007

a(n) = n*(n+1)*(n+2)*...*(2*n-1)/n! (product of n consecutive integers, divided by n!). - Jonathan Vos Post, Apr 09 2007

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

a(n) = (2*n+1)*A000108(n). - Paul Barry, Aug 21 2007

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

Row sums of triangle A132813. - Gary W. Adamson, Sep 01 2007

Row sums of triangle A134285. - Gary W. Adamson, Nov 19 2007

Conjectured: 4^n GaussHypergeometric(1/2,-n;2;1) --Solution for the path which stays in the first and second quadrant. - Benjamin Phillabaum, Feb 20 2011

a(n)= sum(0<=k<=n, A038231(n,k)*(-1)^k*A000108(k)). - Philippe Deléham, Nov 27 2009

Let A be the Toeplitz matrix of order n defined by: A[i,i-1]=-1, A[i,j]=Catalan(j-i), (i<=j), and A[i,j]=0, otherwise. Then, for n>=1, a(n)=(-1)^n*charpoly(A,-2). - Milan Janjic, Jul 08 2010

a(n) is the upper left term of M^(n+1), where M is the infinite matrix in which a column of (1,2,3,...) is prepended to an infinite lower triangular matrix of all 1's and the rest zeros, as follows:

1, 1, 0, 0, 0,...

2, 1, 1, 0, 0,...

3, 1, 1, 1, 0,...

4, 1, 1, 1, 1,...

...

Alternatively, a(n) is the upper left term of M^n where M is the infinite matrix:

3, 1, 0, 0, 0,...

1, 1, 1, 0, 0,...

1, 1, 1, 1, 0,...

1, 1, 1, 1, 1,...

...

- Gary W. Adamson, Jul 14 2011

a(n) = (n+1)*hypergeom([-n, -n], [2], 1). - Peter Luschny, Oct 24 2011

a(n) = pochhammer(n+1,n+1)/(n+1)!. - Peter Luschny, Nov 07 2011

E.g.f.: 1+6*x/(U(0)-6*x); U(k)=k^2+(4*x+3)*k+6*x+2-2*x*(k+1)*(k+2)*(2*k+5)/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2011

a(n) = 2^(2*n+1)*binomial(n+1/2, -1/2). - Peter Luschny, May 06 2014

EXAMPLE

There are a(2)=10 ways to put 3 indistinguishable balls into 3 distinguishable boxes, namely, (OOO)()(), ()(OOO)(), ()()(OOO), (OO)(O)(), (OO)()(O), (O)(OO)(), ()(OO)(O), (O)()(OO), ()(O)(OO), and (O)(O)(O). - Dennis P. Walsh, Apr 11 2012

MAPLE

A001700 := n -> binomial(2*n+1, n+1); seq(A001700(n), n=0..20);

MATHEMATICA

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

CoefficientList[ Series[2/((Sqrt[1 - 4 x] + 1)*Sqrt[1 - 4 x]), {x, 0, 22}], x] (* Robert G. Wilson v, Aug 08 2011 *)

PROG

(Sage) [rising_factorial(n+1, n+1)/factorial(n+1) for n in (0..22)] # Peter Luschny, Nov 07 2011

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

(Haskell)

a001700 n = a007318 (2*n+1) (n+1)  -- Reinhard Zumkeller, Oct 25 2013

(MAGMA) [Binomial(2*n, n)/2: n in [1..40]]; // Vincenzo Librandi, Nov 10 2014

CROSSREFS

Cf. A007318, 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) = (2n+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.

Row sums of A103371. - Susanne Wienand, Oct 22 2011

Cf. A002054: C(2n+1,n-1). - Bruno Berselli, Jan 20 2014

Cf. A005043, A091867, A001792, A001813.

Sequence in context: A167403 * A088218 A110556 A072266 A085282 A149036

Adjacent sequences:  A001697 A001698 A001699 * A001701 A001702 A001703

KEYWORD

easy,nonn,nice,core,changed

AUTHOR

N. J. A. Sloane, Apr 30 1991

EXTENSIONS

Name corrected by Paul S. Coombes, Jan 11 2012

Name corrected by Robert Tanniru, Feb 01 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

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

Last modified November 27 14:29 EST 2014. Contains 250210 sequences.