A001700 - OEIS

%I M2848 N1144 #663 Sep 19 2024 21:41:30

%S 1,3,10,35,126,462,1716,6435,24310,92378,352716,1352078,5200300,

%T 20058300,77558760,300540195,1166803110,4537567650,17672631900,

%U 68923264410,269128937220,1052049481860,4116715363800,16123801841550,63205303218876,247959266474052

%N 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.

%C 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).

%C 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

%C 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.)

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

%C Also number of digitally balanced numbers [A031443] from 2^(2*n+1) to 2^(2*n+2). - _Naohiro Nomoto_, Apr 07 2001

%C 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

%C 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

%C 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

%C 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_

%C 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

%C 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

%C 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

%C 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.

%C 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

%C 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

%C 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

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

%C Also the Catalan transform of A000225 shifted one index, i.e., dropping A000225(0). - _R. J. Mathar_, Nov 11 2008

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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).]

%C 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

%C Equals row sums of triangle A205945. - _Gary W. Adamson_, Feb 01 2012

%C 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

%C 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

%C For n > 0: largest terms of Zigzag matrices as defined in A088961. - _Reinhard Zumkeller_, Oct 25 2013

%C 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

%C 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

%C From _Tom Copeland_, Nov 09 2014: (Start)

%C 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).

%C 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).

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

%C 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).

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

%C Placing n distinguishable balls into n indistinguishable boxes gives A000110(n) (the number of set partitions). - _N. J. A. Sloane_, Jun 19 2015

%C The sequence is the INVERTi transform of A049027: (1, 4, 17, 74, 326, ...). - _Gary W. Adamson_, Jun 23 2015

%C 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

%C 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

%C Also the number of ordered (rooted planar) forests with a total of n+1 edges and no trivial trees. - _Nachum Dershowitz_, Mar 30 2016

%C 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

%C 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

%C 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

%C Total number of nodes summed over all Dyck paths of semilength n. - _Alois P. Heinz_, Mar 08 2020

%C 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

%C 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

%C a(n) is the number of parking functions of size n+1 avoiding the patterns 132, 213, and 321. - _Lara Pudwell_, Apr 10 2023

%C 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

%C 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

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

%C 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

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

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

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

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

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

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

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

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

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

%H Matuszka Tamás, <a href="/A001700/b001700.txt">Table of n, a(n) for n = 0..1200</a> (first 100 terms from T. D. Noe)

%H J. Abate and W. Whitt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Whitt/whitt6.html">Brownian Motion and the Generalized Catalan Numbers</a>, J. Int. Seq. 14 (2011), #11.2.6, theorem 4.

%H Ayomikun Adeniran and Lara Pudwell, <a href="https://doi.org/10.54550/ECA2023V3S3R17">Pattern avoidance in parking functions</a>, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.

%H José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Agapito/agapito2.html">On One-Parameter Catalan Arrays</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.1.

%H Martin Aigner, <a href="https://doi.org/10.1016/j.disc.2007.06.012">Enumeration via ballot numbers</a>, Discrete Math., 308 (2008), 2544-2563.

%H Elena Barcucci, Andrea Frosini, and Simone Rinaldi, <a href="https://doi.org/10.1016/j.disc.2005.01.006">On directed-convex polyominoes in a rectangle</a>, Discr. Math., 298 (2005), 62-78.

%H Elena Barcucci, Antonio Bernini, and Renzo Pinzani, <a href="http://ceur-ws.org/Vol-2113/paper7.pdf">Exhaustive generation of positive lattice paths</a>, Semantic Sensor Networks Workshop 2018, CEUR Workshop Proceedings (2018), Vol. 2113.

%H Jean-Luc Baril, David Bevan, and Sergey Kirgizov, <a href="https://arxiv.org/abs/1906.11870">Bijections between directed animals, multisets and Grand-Dyck paths</a>, arXiv:1906.11870 [math.CO], 2019.

%H Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, <a href="https://arxiv.org/abs/2404.05672">Enumerating runs, valleys, and peaks in Catalan words</a>, arXiv:2404.05672 [math.CO], 2024. See p. 5.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, Journal of Integer Sequences, 9 (2006), Article 06.2.4.

%H Paul Barry, <a href="https://www.emis.de/journals/JIS/VOL22/Barry1/barry411.html">The Central Coefficients of a Family of Pascal-like Triangles and Colored Lattice Paths</a>, J. Int. Seq., 22 (2019), Article 19.1.3.

%H Paul Barry, <a href="https://arxiv.org/abs/1912.01124">A Note on Riordan Arrays with Catalan Halves</a>, arXiv:1912.01124 [math.CO], 2019.

%H Antonio Bernini, Filippo Disanto, Renzo Pinzani, and Simone Rinaldi, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Rinaldi/rinaldi5.html">Permutations defining convex permutominoes</a>, J. Int. Seq. 10 (2007), #07.9.7.

%H Ciprian Borcea and Ileana Streinu, <a href="https://arxiv.org/abs/math/0207126">On the number of embeddings of minimally rigid graphs</a>, arXiv:math/0207126 [math.MG], 2002.

%H Mireille Bousquet-Mélou, <a href="https://doi.org/10.1016/S0012-365X(97)00109-X">New enumerative results on two-dimensional directed animals</a>, Discr. Math., 180 (1998), 73-106. See Eq. (1).

%H M. Bousquet-Mélou and A. Rechnitzer, <a href="http://www.labri.fr/Perso/~bousquet/Articles/Klarner/article.ps.gz">Lattice animals and heaps of dimers</a>.

%H Jean-Paul Bultel and Samuele Giraudo, <a href="https://arxiv.org/abs/1406.6903">Combinatorial Hopf algebras from PROs</a>, arXiv:1406.6903 [math.CO], 2014. <a href="https://doi.org/10.1007/s10801-016-0677-7">[DOI]</a>

%H Libor Caha and Daniel Nagaj, <a href="https://arxiv.org/abs/1805.07168">The pair-flip model: a very entangled translationally invariant spin chain</a>, arXiv:1805.07168 [quant-ph], 2018.

%H David Callan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Callan/callan301.html">A Combinatorial Interpretation for a Super-Catalan Recurrence</a>, Journal of Integer Sequences, 8 (2005), Article 05.1.8.

%H Peter J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs., 3 (2000), #00.1.5.

%H Gi-Sang Cheon, Hana Kim, and Louis W. Shapiro, <a href="https://arxiv.org/abs/1410.1249">Mutation effects in ordered trees</a>, arXiv:1410.1249 [math.CO], 2014.

%H Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Davenport/dav3.html">The Boundary of Ordered Trees</a>, Journal of Integer Sequences, 18 (2015), Article 15.5.8.

%H Nachum Dershowitz, <a href="https://arxiv.org/abs/1608.08740">1700 Forests</a>, arXiv:1608.08740 [cs.DM], 2016.

%H Leonard E. Dickson, <a href="https://doi.org/10.2307/1967509">On the Inscription of Regular Polygons</a>, Annals of Mathematics, Vol. 9, No. 1/6 (1894 - 1895), pp. 73-84.

%H Leonard E. Dickson, <a href="https://doi.org/10.2307/2968251">Problem 44</a>, The American Mathematical Monthly, Vol. 2, No. 7/8 (Jul. - Aug., 1895), pp. 229-230.

%H G. Dresden and Y. Li, <a href="https://arxiv.org/abs/2210.04322">Periodic Weighted Sums of Binomial Coefficients</a>, arXiv:2210.04322 [math.NT], 2022.

%H Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, <a href="https://arxiv.org/abs/2310.06288">Catalan-Spitzer permutations</a>, arXiv:2310.06288 [math.CO], 2023. See p. 20.

%H Miquel A. Fiol, E. Garriga, and J. L. A. Yebra, <a href="https://doi.org/10.1017/S0963548300004181">On twisted odd graphs</a>, Combin. Probab. Comput. 9 (2000), 227-240.

%H Rigoberto Flórez, Leandro Junes, and José L. Ramírez, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Florez/florez4.html">Further Results on Paths in an n-Dimensional Cubic Lattice</a>, Journal of Integer Sequences, 21 (2018), Article 18.1.2.

%H Shishuo Fu and Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.

%H Juan B. Gil, Emma G. Hoover, and Jessica A. Shearer, <a href="https://arxiv.org/abs/2403.04575">Bijections between colored compositions, Dyck paths, and polygon partitions</a>, arXiv:2403.04575 [math.CO], 2024. See p. 4.

%H N. Gromov and P. Vieira, <a href="https://arxiv.org/abs/1205.5288">Tailoring Three-Point Functions and Integrability IV. Theta-morphism</a>, arXiv:1205.5288 [hep-th], 2012. - From _N. J. A. Sloane_, Oct 23 2012

%H R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, 3 (2000), Article #00.1.6.

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]

%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=145">Encyclopedia of Combinatorial Structures 145</a>.

%H A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, <a href="http://www.acta.sapientia.ro/acta-info/C4-2/info42-7.pdf">Parallel enumeration of degree sequences of simple graphs</a>, Acta Univ. Sapientiae, Informatica, 4(2) (2012) 260-288.

%H Milan Janjic, <a href="http://www.pmfbl.org/janjic/">Two Enumerative Functions</a>.

%H Christian Krattenthaler and Daniel Yaqubi, <a href="https://arxiv.org/abs/1802.05990">Some determinants of path generating functions, II</a>, Adv. Appl. Math. 101 (2018), 232-265.

%H Dmitry Kruchinin, <a href="https://arxiv.org/abs/1109.1683">Superposition's properties of logarithmic generating functions</a>, arXiv:1109.1683 [math.CO], 2011-2015.

%H Markus Kuba and Alois Panholzer, <a href="http://ajc.maths.uq.edu.au/pdf/74/ajc_v74_p216.pdf">Stirling permutations containing a single pattern of length three</a>, Australasian Journal of Combinatorics 74(2) (2019), 216-239.

%H Wolfdieter Lang, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/LANG/lang.html">On generalizations of Stirling number triangles</a>, J. Integer Seqs., 3 (2000), #00.2.4.

%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.

%H H. Li and T. MacHenry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/MacHenry/machenry7.html">Permanents and Determinants, Weighted Isobaric Polynomials, and Integer Sequences</a>, J. Int. Seq. 16 (2013) #13.3.5, example 40.

%H Elżbieta Liszewska and Wojciech Młotkowski, <a href="https://arxiv.org/abs/1907.10725">Some relatives of the Catalan sequence</a>, arXiv:1907.10725 [math.CO], 2019.

%H T. Mansour and M. Shattuck, <a href="https://doi.org/10.1007/s12044-014-0166-7">A statistic on n-color compositions and related sequences</a>, Proc. Indian Acad. Sci. (Math. Sci.) 124(2) (2014), pp. 127-140.

%H M. D. McIlroy, <a href="/A001700/a001700.pdf">Letter to N. J. A. Sloane (no date)</a>.

%H Donatella Merlini and Massimo Nocentini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Merlini/merlini5.html">Algebraic Generating Functions for Languages Avoiding Riordan Patterns</a>, Journal of Integer Sequences, 21 (2018), Article 18.1.3.

%H Hanna Mularczyk, <a href="https://arxiv.org/abs/1908.04025">Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations</a>, arXiv:1908.04025 [math.CO], 2019.

%H M. Munar, S. Massanet, and D. Ruiz-Aguilera, <a href="https://doi.org/10.1016/j.ins.2022.10.121">On the cardinality of some families of discrete connectives</a>, Information Sciences, Volume 621, 2023, 708-728.

%H A. Nkwanta, <a href="https://doi.org/10.1016/j.jspi.2010.01.027">Riordan matrices and higher-dimensional lattice walks</a>, J. Stat. Plann. Infer. 140 (2010), 2321-2334.

%H Asamoah Nkwanta and Earl R. Barnes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Nkwanta/nkwanta2.html">Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind</a>, Journal of Integer Sequences, 15 (2012), Article 12.3.3. - From _N. J. A. Sloane_, Sep 16 2012

%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., 4 (2001), #01.2.1.

%H John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.

%H Louis Shapiro, <a href="http://www.jstor.org/stable/2589028">Problem 10753</a> Amer. Math. Monthly, 106(8) (1999), p. 777.

%H Louis Shapiro et al., <a href="http://www.jstor.org/stable/2695569">Leaves of Ordered Trees: 10753</a>, Amer. Math. Monthly, 108(9) (Nov., 2001), 873-874.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BinomialCoefficient.html">Binomial Coefficient</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/OddGraph.html">Odd Graph</a>.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

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

%F D-finite with recurrence: a(0) = 1, a(n) = 2*(2*n+1)*a(n-1)/(n+1) for n > 0.

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

%F 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

%F G.f.: 2F1([1, 3/2]; [2]; 4*x). - _Paul Barry_, Jan 23 2009

%F G.f.: 1/(1 - 2*x - x/(1 - x/(1 - x/(1 - x/(1 - ... (continued fraction). - _Paul Barry_, May 06 2009

%F G.f.: c(x)^2/(1 - x*c(x)^2), c(x) the g.f. of A000108. - _Paul Barry_, Sep 07 2009

%F 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

%F Convolution of A000108 (Catalan) and A000984 (central binomial): Sum_{k=0..n} C(k)*binomial(2*(n-k), n-k), C(k) Catalan. - _Wolfdieter Lang_, Dec 11 1999

%F a(n) = Sum_{k=0..n} C(n+k, k). - _Benoit Cloitre_, Aug 20 2002

%F a(n) = Sum_{k=0..n} C(n, k)*C(n+1, k+1). - _Benoit Cloitre_, Oct 19 2002

%F a(n) = Sum_{k = 0..n+1} binomial(2*n+2, k)*cos((n - k + 1)*Pi). - _Paul Barry_, Nov 02 2004

%F a(n) = 4^n*binomial(n+1/2, n)/(n+1). - _Paul Barry_, May 10 2005

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

%F 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) = 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

%F 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

%F a(n) = A122366(n,n). - _Reinhard Zumkeller_, Aug 30 2006

%F a(n) = C(2*n, n) + C(2*n, n-1) = A000984(n) + A001791(n). - _Zerinvary Lajos_, Jan 23 2007

%F a(n-1) = (n+1)*(n+2)*...*(2*n-1)/(n-1)! (product of n-1 consecutive integers, divided by (n-1)!). - _Jonathan Vos Post_, Apr 09 2007; [Corrected and shortened by _Giovanni Ciriani_, Mar 26 2019]

%F a(n-1) = (2*n - 1)!/(n!*(n - 1)!). - _William A. Tedeschi_, Feb 27 2008

%F a(n) = (2*n + 1)*A000108(n). - _Paul Barry_, Aug 21 2007

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

%F Row sums of triangle A132813. - _Gary W. Adamson_, Sep 01 2007

%F Row sums of triangle A134285. - _Gary W. Adamson_, Nov 19 2007

%F a(n) = 2*A000984(n) - A000108(n), that is, a(n) = 2*C(2*n, n) - n-th Catalan number. - _Joseph Abate_, Jun 11 2010

%F 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

%F a(n)= Sum_{k=0..n} A038231(n,k) * (-1)^k * A000108(k). - _Philippe Deléham_, Nov 27 2009

%F 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

%F 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:

%F    1, 1, 0, 0, 0, ...

%F    2, 1, 1, 0, 0, ...

%F    3, 1, 1, 1, 0, ...

%F    4, 1, 1, 1, 1, ...

%F    ...

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

%F    3, 1, 0, 0, 0, ...

%F    1, 1, 1, 0, 0, ...

%F    1, 1, 1, 1, 0, ...

%F    1, 1, 1, 1, 1, ...

%F    ...

%F - _Gary W. Adamson_, Jul 14 2011

%F a(n) = (n + 1)*hypergeom([-n, -n], [2], 1). - _Peter Luschny_, Oct 24 2011

%F a(n) = Pochhammer(n+1, n+1)/(n+1)!. - _Peter Luschny_, Nov 07 2011

%F 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

%F a(n) = 2*A000984(n) - A000108(n). [Abate & Whitt]

%F a(n) = 2^(2*n+1)*binomial(n+1/2, -1/2). - _Peter Luschny_, May 06 2014

%F For n > 1: a(n-1) = A166454(2*n, n), central terms in A166454. - _Reinhard Zumkeller_, Mar 04 2015

%F a(n) = 2*4^n*Gamma(3/2 + n)/(sqrt(Pi)*Gamma(2+n)). - _Peter Luschny_, Dec 14 2015

%F 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

%F a(n) = (-1)^(n)*B(n, n+1, -n-1)/n!, where B(n,a,x) is a generalized Bernoulli polynomial. - _Vladimir Kruchinin_, Apr 06 2016

%F a(n) = Gamma(2 + 2*n)/(n!*Gamma(2 + n)). _Andres Cicuttin_, Apr 06 2016

%F a(n) = (n + (n + 1))!/(Gamma(n)*Gamma(1 + n)*A002378(n)), for n > 0. _Andres Cicuttin_, Apr 07 2016

%F From _Ilya Gutkovskiy_, Jul 04 2016: (Start)

%F Sum_{n >= 0} 1/a(n) = 2*(9 + 2*sqrt(3)*Pi)/27 = A248179.

%F Sum_{n >= 0} (-1)^n/a(n) = 2*(5 + 4*sqrt(5)*arcsinh(1/2))/25 = 2*(5*A145433 - 1).

%F Sum_{n >= 0} (-1)^n*a(n)/n! = BesselI(2,2)*exp(-2) = A229020*A092553. (End)

%F Conjecture: a(n) = Sum_{k=2^n..2^(n+1)-1} A178244(k). - _Mikhail Kurkov_, Feb 20 2021

%F a(n-1) = 1 + (1/n)*Sum_{t=1..n/2} (2*cos((2*t-1)*Pi/(2*n)))^(2*n). - _Greg Dresden_, Oct 11 2022

%F a(n) = Product_{1 <= i <= j <= n} (i + j + 1)/(i + j - 1). Cf. A006013. - _Peter Bala_, Feb 21 2023

%F 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

%e 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

%e 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

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

%p A001700List := proc(m) local A, P, n; A := [1]; P := [1];

%p for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), 2*P[-1]]);

%p A := [op(A), P[-1]] od; A end: A001700List(27); # _Peter Luschny_, Mar 24 2022

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

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

%o (Sage) [rising_factorial(n+1,n+1)/factorial(n+1) for n in (0..22)] # _Peter Luschny_, Nov 07 2011

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

%o (PARI) z='z+O('z^50); Vec((1/sqrt(1-4*z)-1)/(2*z)) \\ _Altug Alkan_, Oct 11 2015

%o (Haskell)

%o a001700 n = a007318 (2*n+1) (n+1)  -- _Reinhard Zumkeller_, Oct 25 2013

%o (Magma) [Binomial(2*n, n)/2: n in [1..40]]; // _Vincenzo Librandi_, Nov 10 2014

%o (Python)

%o from __future__ import division

%o A001700_list, b = [], 1

%o for n in range(10**3):

%o     A001700_list.append(b)

%o     b = b*(4*n+6)//(n+2) # _Chai Wah Wu_, Jan 26 2016

%o (Maxima)

%o B(n,a,x):=coeff(taylor(exp(x*t)*(t/(exp(t)-1))^a,t,0,20),t,n)*n!;

%o makelist((-1)^(n)*B(n,n+1,-n-1)/n!,n,0,10); /* _Vladimir Kruchinin_, Apr 06 2016 */

%o (GAP) List([0..30],n->Binomial(2*n+1,n+1)); # _Muniru A Asiru_, Feb 26 2019

%Y Cf. A000110, A007318, A030662, A046097, A060897-A060900, A049027, A076025, A076026, A060150, A001263, A005773, A001405, A132813, A134285.

%Y Equals A000984(n+1)/2.

%Y a(n) = (2*n+1)*Catalan(n) [A000108] = A035324(n+1, 1) (first column of triangle).

%Y Row sums of triangles A028364, A050166, A039598.

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

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

%Y Diagonals 1 and 2 of triangle A100257.

%Y Second row of array A102539.

%Y Column of array A073165.

%Y Row sums of A103371. - _Susanne Wienand_, Oct 22 2011

%Y Cf. A002054: C(2*n+1, n-1). - _Bruno Berselli_, Jan 20 2014

%Y Cf. A005043, A091867, A001792, A001813, A166454.

%K easy,nonn,nice,core

%O 0,2

%A _N. J. A. Sloane_

%E Name corrected by _Paul S. Coombes_, Jan 11 2012

%E Name corrected by _Robert Tanniru_, Feb 01 2014