

A001700


a(n) = binomial(2*n+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)


387



1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078, 5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650, 17672631900, 68923264410, 269128937220, 1052049481860, 4116715363800, 16123801841550, 63205303218876, 247959266474052
(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(2*n+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^(2*n+1) to 2^(2*n+2).  Naohiro Nomoto, Apr 07 2001
Also number of ordered trees with 2*n + 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), diagonal of A165257  Benoit Cloitre, May 07 2002
Also the numerator of the constant term in the expansion of cos^(2*n)(x) or sin^(2*n)(x) when the denominator is 2^(2*n1).  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((2*k1)*x)/2^(n1) for all 2*k  1 <= 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^(2*n)(x)] is [a(n)/2^(2*n1)]. The dc value of [cos^(2*n1)(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 2*k occurs in all Dyck words of length 2*n + 2*k. 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(2*ni, j).  Benoit Cloitre, Aug 26 2003
a(n1) = (2*n)!/(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.
The number of compositions of 2*n, say c_1 + c_2 + ... + c_k = 2n, satisfy that Sum_{i = 1..j} c_i < 2*j for all j = 1..k, or equivalently, the number of subsets, say S, of [2*n1] = {1, 2, ..., 2*n1} 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
The number of walks of length 2*n + 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 2*n + 1 with n + 1 ones and n zeros.  Stefan Hollos (stefan(AT)exstrom.com), Dec 10 2007
If Y is a 3subset of an 2*nset 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
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 distinct 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
The integral of 1/(1+x^2)^(n+1) is given by a(n)/2^(2*n  1) * (x/(1 + x^2)^n*P(x) + arctan(x)), where P(x) is a monic polynomial of degree 2*n  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^(2*n + 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^(2*n + 2)x.  John M. Campbell, Jul 19 2011 [Apparently, the contributor means Integral_{x = 0..Pi/2} x * (sin(x))^(2*n + 2).]
a(n1) = C(2*n, n)/2 is the number of ways to assign 2*n people into 2 (unlabeled) groups of size n.  Dennis P. Walsh, Nov 09 2011
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) is the sum of falling diagonals of squares in the comment in A085812 (equivalent to the Cloitre formula of Aug 2002).  John Molokach, Sep 26 2013
Also the number of different possible win/loss round sequences (from the perspective of the eventual winner) in a "best of 2*n + 1" twoplayer 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 is 32 = 2^5.  Bob Selcoe, Jul 16 2014
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(14x)]/2, an o.g.f. for the Catalan numbers A000108, with inverse Cinv(x) = x*(1x) and P(x,t) = x/(1 + t*x) with inverse P(x, t).
O.g.f: G(x) = [1 + sqrt(1 + 4*x/(1  4*x))]/2 = C[P(x, 4)].
Inverse o.g.f: Ginv(x) = x*(1 + x)/(1 + 4*x*(1 + x)) = P(Cinv(x), 4) (shifted signed A001792). A088218(x) = 1 + G(x).
Equals A001813/2 omitting the leading 1 there. (End)
Placing n distinguishable balls into n indistinguishable boxes gives A000110(n) (the number of set partitions).  N. J. A. Sloane, Jun 19 2015
a(n) is the number of compositions of 2*n + 2 such that the sum of the elements at odd positions is equal to the sum of the elements at even positions. a(2) = 10 because there are 10 such compositions of 6: (3, 3), (1, 3, 2), (2, 3, 1), (1, 1, 2, 2), (1, 2, 2, 1), (2, 2, 1, 1), (2, 1, 1, 2), (1, 2, 1, 1, 1), (1, 1, 1, 2, 1), (1, 1, 1, 1, 1, 1).  Ran Pan, Oct 08 2015
a(n1) is also the Schur function of the partition (n) of n evaluated at x_1 = x_2 = ... = x_n = 1, i.e., the number of semistandard Young tableaux of shape (n) (weakly increasing rows with n boxes with numbers from {1, 2, ..., n}).  Wolfdieter Lang, Oct 11 2015
Also the number of ordered (rooted planar) forests with a total of n+1 edges and no trivial trees.  Nachum Dershowitz, Mar 30 2016
a(n) is the number of sets (i1,...in) of length n so that n >= i1 >= i2 >= ...>= in >= 1. For instance, n=3 as there are only 10 such sets (3,3,3) (3,3,2) (3,3,1) (3,2,2) (3,2,1) (3,1,1) (2,2,2) (2,2,1) (2,1,1) (1,1,1,) 3,2,1 is each used 10 times respectively.  Anton Zakharov, Jul 04 2016
The repeated middle term in the odd rows of Pascal's triangle, or half the central binomial coefficient in the even rows of Pascal's triangle, n >= 2.  Enrique Navarrete, Feb 12 2018
a(n) is the number of walks of length 2n+1 from the origin with steps (1,1) and (1,1) that stay on or above the xaxis. Equivalently, a(n) is the number of walks of length 2n+1 from the origin with steps (1,0) and (0,1) that stay in the first octant.  Alexander Burstein, Dec 24 2019
Total number of nodes summed over all Dyck paths of semilength n.  Alois P. Heinz, Mar 08 2020
a(n1) is the determinant of the n X n matrix m(i, j) = binomial(n+i1, j).  Fabio Visonà, May 21 2022
Let X_i be iid standard Gaussian random variable N(0,1), and S_n be the partial sum S_n = X_1+...+X_n. Then P(S_1>0,S_2>0,...,S_n>0) = a(n+1)/2^(2n1) = a(n+1) / A004171(n+1). For example, P(S_1>0) = 1/2, P(S_1>0,S_2>0) = 3/8, P(S_1>0,S_2>0,S_3>0) = 5/16, etc. This probability is also equal to the volume of the region x_1 > 0, x_2 > x_1, x_3 > (x_1+x_2), ..., x_n > (x_1+x_2+...+x_(n1)) in the hypercube [1/2, 1/2]^n. This also holds for the Cauchy distribution and other stable distributions with mean 0, skew 0 and scale 1.  Xiaohan Zhang, Nov 01 2022
a(n) is the number of parking functions of size n+1 avoiding the patterns 132, 213, and 321.  Lara Pudwell, Apr 10 2023
Number of vectors in (Z_>=0)^(n+1) such that the sum of the components is n+1. binomial(2*n1, n) provides this property for n.  Michael Richard, Jun 12 2023
Also number of discrete negations on the finite chain L_n={0,1,...,n1,n}, i.e., monotone decreasing unary operators such that N(0)=n and N(n)=0.  Marc Munar, Oct 10 2023


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.
J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
Paul J. Nahin, "An Imaginary Tale, The Story of [Sqrt(1)]," Princeton University Press, Princeton, NJ 1998, p. 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

José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, On OneParameter Catalan Arrays, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.1.
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, 18 (2015), Article 15.5.8.
Nachum Dershowitz, 1700 Forests, arXiv:1608.08740 [cs.DM], 2016.
Leonard E. Dickson, Problem 44, The American Mathematical Monthly, Vol. 2, No. 7/8 (Jul.  Aug., 1895), pp. 229230.
Louis Shapiro, Problem 10753 Amer. Math. Monthly, 106(8) (1999), p. 777.
Eric Weisstein's World of Mathematics, Odd Graph.


FORMULA

a(n1) = binomial(2*n, n)/2 = (2*n)!/(2*n!*n!).
Dfinite with recurrence: a(0) = 1, a(n) = 2*(2*n+1)*a(n1)/(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)*x^(n+1)/(n+1).  Vladimir Kruchinin, Aug 10 2010
G.f.: 2F1([1, 3/2]; [2]; 4*x).  Paul Barry, Jan 23 2009
G.f.: 1/(1  2*x  x/(1  x/(1  x/(1  x/(1  ... (continued fraction).  Paul Barry, May 06 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_{k=0..n} C(k)*binomial(2*(nk), nk), C(k) Catalan.  Wolfdieter Lang, Dec 11 1999
a(n) = Sum_{k=0..n} C(n, k)*C(n+1, k+1).  Benoit Cloitre, Oct 19 2002
a(n) = Sum_{k = 0..n+1} binomial(2*n+2, k)*cos((n  k + 1)*Pi).  Paul Barry, Nov 02 2004
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) = Integral_{x = 0..4} x^n * (x/(4  x))^(1/2)/(2*Pi) dx, n >= 0. 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(n1) = (n+1)*(n+2)*...*(2*n1)/(n1)! (product of n1 consecutive integers, divided by (n1)!).  Jonathan Vos Post, Apr 09 2007; [Corrected and shortened by Giovanni Ciriani, Mar 26 2019]
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
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, ...
...
a(n) = (n + 1)*hypergeom([n, n], [2], 1).  Peter Luschny, Oct 24 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
a(n) = 2*4^n*Gamma(3/2 + n)/(sqrt(Pi)*Gamma(2+n)).  Peter Luschny, Dec 14 2015
a(n) ~ 2*4^n*(1  (5/8)/n + (73/128)/n^2  (575/1024)/n^3 + (18459/32768)/n^4)/sqrt(n*Pi).  Peter Luschny, Dec 16 2015
a(n) = (1)^(n)*B(n, n+1, n1)/n!, where B(n,a,x) is a generalized Bernoulli polynomial.  Vladimir Kruchinin, Apr 06 2016
Sum_{n >= 0} 1/a(n) = 2*(9 + 2*sqrt(3)*Pi)/27 = A248179.
Sum_{n >= 0} (1)^n/a(n) = 2*(5 + 4*sqrt(5)*arcsinh(1/2))/25 = 2*(5*A145433  1).
Sum_{n >= 0} (1)^n*a(n)/n! = BesselI(2,2)*exp(2) = A229020*A092553. (End)
a(n1) = 1 + (1/n)*Sum_{t=1..n/2} (2*cos((2*t1)*Pi/(2*n)))^(2*n).  Greg Dresden, Oct 11 2022
a(n) = Product_{1 <= i <= j <= n} (i + j + 1)/(i + j  1). Cf. A006013.  Peter Bala, Feb 21 2023
Sum_{n >= 0} a(n)*x^(n+1)/(n+1) = x + 3*x^2/2 + 10*x^3/3 + 35*x^4/4 + ... = the series reversion of exp(x)*(1  exp(x)).  Peter Bala, Sep 06 2023


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
a(2) = 10: Semistandard Young tableaux for partition (3) of 3 (the indeterminates x_i, i = 1, 2, 3 are omitted and only their indices are given): 111, 112, 113, 122, 123, 133, 222, 223, 233, 333.  Wolfdieter Lang, Oct 11 2015


MAPLE

A001700List := proc(m) local A, P, n; A := [1]; P := [1];
for n from 1 to m  2 do P := ListTools:PartialSums([op(P), 2*P[1]]);
A := [op(A), P[1]] od; A end: A001700List(27); # Peter Luschny, Mar 24 2022


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)
(PARI) z='z+O('z^50); Vec((1/sqrt(14*z)1)/(2*z)) \\ Altug Alkan, Oct 11 2015
(Haskell)
(Python)
from __future__ import division
for n in range(10**3):
(Maxima)
B(n, a, x):=coeff(taylor(exp(x*t)*(t/(exp(t)1))^a, t, 0, 20), t, n)*n!;
(GAP) List([0..30], n>Binomial(2*n+1, n+1)); # Muniru A Asiru, Feb 26 2019


CROSSREFS

Cf. A000110, A007318, A030662, A046097, A060897A060900, A049027, A076025, A076026, A060150, A001263, A005773, A001405, A132813, A134285.
a(n) = (2*n+1)*Catalan(n) [A000108] = A035324(n+1, 1) (first column of triangle).
Diagonals 1 and 2 of triangle A100257.


KEYWORD

easy,nonn,nice,core


AUTHOR



EXTENSIONS



STATUS

approved



