

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)


223



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)+k1, 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,j1)+m(i1,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^(2n1).  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((2k1)*x)/2^(n1) for all 2k1<=n. If n is even, then the expansion is a combination of a*cos(2k*x)/2^(n1) terms plus a constant. "The constant term, [a(n)/2^(2n1)], 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^(2n1)]. The dc value of [cos^(2n1)(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(2ni,j).  Benoit Cloitre, Aug 26 2003
a(n1) = (2n)!/(2*n!*n!), formula in [Davenport] used by Gauss for the special case prime p = 4*n+1: x = a(n1) 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(71) = 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((nk+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 [2n1]={1,2,...2n1} 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 3subset of an 2nset X then, for n>=3, a(n1) is the number of nsubsets 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 n1 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*a000984a000108, that is, a(n) = 2*c(2n,n)catalan.  Joseph Abate, Jun 11 2010
The integral of 1/(1+x^2)^(n+1) is given by a(n)/2^(2n1) * (x/(1+x^2)^n*P(x) + arctan(x)), where P(x) is a monic polynomial of degree 2n2 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 eah 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 int 0...pi/2 x sin^(2n+2)x.  John M. Campbell, Jul 19 2011
a(n1) = 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(n1) gives the number of nregular 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 in a "best of n+1" twoplayer game. For example, a(2) = 10 means there are 10 different win/loss sequences in a "best of 3" game (like a 3 set tennis match). For example: (win, win, win), (loss, win, win, win) etc. See also A072600.  Philippe Beaudoin, May 14 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


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), 497508.
Charles Jordan, Calculus of Finite Differences, Chelsea 1965, p. 449.
T. Mansour, M. Shattuck, A statistic on ncolor compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127140.
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), 3346.
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), 25442563.
E. Barcucci, A. Frosini and S. Rinaldi, On directedconvex polyominoes in a rectangle, Discr. Math., 298 (2005). 6278.
Paul Barry, On IntegerSequenceBased 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. BousquetMélou, New enumerative results on twodimensional directed animals, Discr. Math., 180 (1998), 73106. See Eq. (1).  From N. J. A. Sloane, Jun 03 2012
David Callan, A Combinatorial Interpretation for a SuperCatalan 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 ThreePoint Functions and Integrability IV. Thetamorphism, 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
GuoNiu Han, Enumeration of Standard Puzzles
GuoNiu 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) 260288.
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 Catalantype 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. 873874
Eric Weisstein's World of Mathematics, Binomial Coefficient
Eric Weisstein's World of Mathematics, Odd Graph
Index entries for "core" sequences


FORMULA

a(n1) = binomial(2*n, n)/2 = (2*n)!/(2*n!*n!).
a(0) = 1, a(n) = 2*(2*n+1)*a(n1)/(n+1) for n > 0.
G.f.: (1/sqrt(14*x)1)/(2*x).
L.g.f. log((1sqrt(14*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/(12xx/(1x/(1x/(1x/(1... (continued fraction).  Paul Barry, May 06 2009
G.f.: c(x)^2/(1x*c(x)^2), c(x) the g.f. of A000108.  Paul Barry, Sep 07 2009
O.g.f.: c(x)/sqrt(14*x) = (2  c(x))/(14*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*(nk), nk), 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 nth moment of a positive function on [0, 4]: a(n)=int(x^n*((x/(4x))^(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, n1) = A000984(n) + A001791(n).  Zerinvary Lajos, Jan 23 2007
a(n) = n*(n+1)*(n+2)*...*(2*n1)/n! (product of n consecutive integers, divided by n!).  Jonathan Vos Post, Apr 09 2007
a(n1) = (2*n1)!/(n!*(n1)!).  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,i1]=1, A[i,j]=Catalan(ji), (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+22*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


CROSSREFS

Cf. A007318, A030662, A046097, A060897A060900, 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,n1).  Bruno Berselli, Jan 20 2014
Sequence in context: A167403 * A088218 A110556 A072266 A085282 A149036
Adjacent sequences: A001697 A001698 A001699 * A001701 A001702 A001703


KEYWORD

easy,nonn,nice,core


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



