A001700 - OEIS (original) (raw)

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, j-1) + m(i-1, 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*n-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((2*k-1)*x)/2^(n-1) for all 2*k - 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^(2*n)(x)] is [a(n)/2^(2*n-1)]. The dc value of [cos^(2*n-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 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*n-i, j). - Benoit Cloitre, Aug 26 2003

a(n-1) = (2*n)!/(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.

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*n-1] = {1, 2, ..., 2*n-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

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 3-subset of an 2*n-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 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(n-1) = 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(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) 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" 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 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(1-4x)]/2, an o.g.f. for the Catalan numbers 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 - 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

The sequence is the INVERTi transform of A049027: (1, 4, 17, 74, 326, ...). - Gary W. Adamson, Jun 23 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(n-1) 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 x-axis. 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(n-1) is the determinant of the n X n matrix m(i, j) = binomial(n+i-1, 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^(2n-1) = 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_(n-1)) 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*n-1, n) provides this property for n. - Michael Richard, Jun 12 2023

Also number of discrete negations on the finite chain L_n={0,1,...,n-1,n}, i.e., monotone decreasing unary operators such that N(0)=n and N(n)=0. - Marc Munar, Oct 10 2023

a(n) is the number of Dyck paths of semilength n+1 having one of its peaks marked. - Juan B. Gil, Jan 03 2024

a(n) is the dimension of the (n+1)-st symmetric power of an (n+1)-dimensional vector space. - Mehmet A. Ates, Feb 15 2024

a(n) is the independence number of the twisted odd graph O^(sigma)_(n+2). - Miquel A. Fiol, Aug 26 2024

a(n) is the number of non-descending sequences with length n and the last number is less or equal to n. a(n) is also the number of integer partitions (of any positive integer) with length n and largest part is less or equal to n. - Zlatko Damijanic, Dec 06 2024