This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001405 a(n) = binomial(n, floor(n/2)).
(Formerly M0769 N0294)

%I M0769 N0294

%S 1,1,2,3,6,10,20,35,70,126,252,462,924,1716,3432,6435,12870,24310,

%T 48620,92378,184756,352716,705432,1352078,2704156,5200300,10400600,

%U 20058300,40116600,77558760,155117520,300540195,601080390,1166803110

%N a(n) = binomial(n, floor(n/2)).

%C By symmetry, a(n) = binomial(n, ceiling(n/2)). - _Labos Elemer_, Mar 20 2003

%C Sperner's theorem says that this is the maximal number of subsets of an n-set such that no one contains another.

%C When computed from index -1, [seq(binomial(n,floor(n/2)), n=-1..30)]; -> [1,1,1,2,3,6,10,20,35,70,126,...] and convolved with aerated Catalan numbers [seq(((n+1) mod 2)*binomial(n,n/2)/((n/2)+1), n=0..30)]; -> [1,0,1,0,2,0,5,0,14,0,42,0,132,0,...] shifts left by one: [1,1,2,3,6,10,20,35,70,126,252,...] and if again convolved with aerated Catalan numbers, seems to give A037952 apart from the initial term. - _Antti Karttunen_, Jun 05 2001

%C Number of ordered trees with n+1 edges, having nonroot nodes of outdegree 0 or 2. - _Emeric Deutsch_, Aug 02 2002

%C Gives for n >= 1 the maximum absolute column sum norm of the inverse of the Vandermonde matrix (a_ij) i=0..n-1, j=0..n-1 with a_00=1 and a_ij=i^j for (i,j) != (0,0). - _Torsten Muetze_, Feb 06 2004

%C Image of Catalan numbers A000108 under the Riordan array (1/(1-2x),-x/(1-2x)) or A065109. - _Paul Barry_, Jan 27 2005

%C Number of left factors of Dyck paths, consisting of n steps. Example: a(4)=6 because we have UDUD, UDUU, UUDD, UUDU, UUUD and UUUU, where U=(1,1) and D=(1,-1). - _Emeric Deutsch_, Apr 23 2005

%C Number of dispersed Dyck paths of length n; they are defined as concatenations of Dyck paths and (1,0)-steps on the x-axis; equivalently, Motzkin paths with no (1,0)-steps at positive height. Example: a(4)=6 because we have HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD, where U=(1,1), H=(1,0), and D=(1,-1). - _Emeric Deutsch_, Jun 04 2011

%C a(n) is odd iff n=2^k-1. - _Jon Perry_, May 05 2005

%C An inverse Chebyshev transform of binomial(1,n)=(1,1,0,0,0,...) where g(x)->(1/sqrt(1-4*x^2))*g(x*c(x^2)), with c(x) the g.f. of A000108. - _Paul Barry_, May 13 2005

%C In a random walk on the number line, starting at 0 and with 0 absorbing after the first step, number of ways of ending up at a positive integer after n steps. - _Joshua Zucker_, Jul 31 2005

%C Maximum number of sums of the form Sum_{i=1..n} e(i)*a(i) that are congruent to 0 mod q, where e_i=0 or 1 and gcd(a_i,q)=1, provided that q > ceiling(n/2). - _Ralf Stephan_, Apr 27 2003

%C Also the number of standard tableaux of height <= 2. - _Mike Zabrocki_, Mar 24 2007

%C Hankel transform of this sequence forms A000012 = [1,1,1,1,1,1,1,...]. - _Philippe Deléham_, Oct 24 2007

%C A001263 * [1, -2, 3, -4, 5, ...] = [1, -1, -2, 3, 6, -10, -20, 35, 70, -126, ...]. - _Gary W. Adamson_, Jan 02 2008

%C Equals right border of triangle A153585. - _Gary W. Adamson_, Dec 28 2008

%C Second binomial transform of A168491. - _Philippe Deléham_, Nov 27 2009

%C a(n) is also the number of distinct strings of length n, each of which is a prefix of a string of balanced parentheses; see example. - _Lee A. Newberg_, Apr 26 2010

%C Number of symmetric balanced strings of n pairs of parentheses; see example. - _Joerg Arndt_, Jul 25 2011

%C a(n) is the number of permutation patterns modulo 2. - _Olivier Gérard_, Feb 25 2011

%C Sum_{n>=0} a(n)/10^(n+1) = 0.1123724... = (sqrt(3)-sqrt(2))/(2*sqrt(2)); Sum_{n>=0} a(n)/100^(n+1) = 0.0101020306102035... = (sqrt(51)-sqrt(49))/(2*sqrt(49)). - _Mark Dols_, Jul 15 2010

%C For n >= 2, a(n-1) is the number of incongruent two-color bracelets of 2*n-1 beads, n of which are black (A007123), having a diameter of symmetry. - _Vladimir Shevelev_, May 03 2011

%C The number of permutations of n elements where p(k-2) < p(k) for all k. - _Joerg Arndt_, Jul 23 2011

%C Also size of the equivalence class of S_{n+1} containing the identity permutation under transformations of positionally adjacent elements of the form abc <--> cba where a < b < c, cf. A210668. - _Tom Roby_, May 15 2012

%C a(n) is the number of symmetric Dyck paths of length 2n. - _Matt Watson_, Sep 26 2012

%C a(n) is divisible by A000108([n/2]) = abs(A129996(n-2)). - _Paul Curtz_, Oct 23 2012

%C a(n) is the number of permutations of length n avoiding both 213 and 231 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - _Manda Riehl_, Aug 05 2014

%C Number of symmetric standard Young tableaux of shape (n,n). - _Ran Pan_, Apr 10 2015

%C From _Luciano Ancora_, May 09 2015: (Start)

%C Also "stepped path" in the array formed by partial sums of the all 1's sequence (or a Pascal's triangle displayed as a square). Example:

%C [1], [1], 1, 1, 1, 1, 1, ... A000012

%C 1, [2], [3], 4, 5, 6, 7, ...

%C 1, 3, [6], [10], 15, 21, 28, ...

%C 1, 4, 10, [20], [35], 56, 84, ...

%C 1, 5, 15, 35, [70], [126], 210, ...

%C Sequences in second formula are the mixed diagonals shown in this array. (End)

%C a(n) = A265848(n,n). - _Reinhard Zumkeller_, Dec 24 2015

%C The constant Sum_{n >= 0} a(n)/n! is 1 + A130820. - _Peter Bala_, Jul 02 2016

%C Number of meanders (walks starting at the origin and ending at any altitude >= 0 that may touch but never go below the x-axis) with n steps from {-1,1}. - _David Nguyen_, Dec 20 2016

%C a(n) is also the number of paths of n steps (either up or down by 1) that end at the maximal value achieved along the path. - _Winston Luo_, Jun 01 2017

%C Number of binary n-tuples such that the number of 1's in the even positions is the same as the number of 1's in the odd positions. - _Juan A. Olmos_, Dec 21 2017

%C Equivalently, a(n) is the number of subsets of {1,...,n} containing as many even numbers as odd numbers. - _Gus Wiseman_, Mar 17 2018

%C a(n) is the number of Dyck paths with semilength = n+1, returns to the x-axis = floor((n+3)/2) and up movements in odd positions = floor((n+3)/2). Example: a(4)=6, U=up movement in odd position, u=up movement in even position, d=down movement, -=return to x-axis: Uududd-Ud-Ud-, Ud-Uudd-Uudd-, Uudd-Uudd-Ud-, Ud-Ud-Uududd-, Uudd-Ud-Uudd-, Ud-Uududd-Ud-. - _Roger Ford_, Dec 29 2017

%C Let C_n(R, H) denote the transition matrix from the ribbon basis to the homogeneous basis of the graded component of the algebra of noncommutative symmetric functions of order n. Letting I(2^(n-1)) denote the identity matrix of order 2^(n-1), it has been conjectured that the dimension of the kernel of C_n(R, H) - I(2^(n-1)) is always equal to a(n-1). - _John M. Campbell_, Mar 30 2018

%C The number of U-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are U-equivalent iff the positions of pattern U are identical in these paths. - _Sergey Kirgizov_, Apr 2018

%C All binary self-dual codes of length 2n, for n > 0, must contain at least a(n) codewords of weight n. More to the point, there will always be at least one, perhaps unique, binary self-dual code of length 2n that will contain exactly a(n) codewords that have a hamming weight equal to half the length of the code (n). This code can be constructed by direct summing the unique binary self-dual code of length 2 (up to permutation equivalence) to itself n times. A permutation equivalent code can be constructed by augmenting two identity matrices of length n together. - _Nathan J. Russell_, Nov 25 2018

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.

%D M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 135.

%D K. Engel, Sperner Theory, Camb. Univ. Press, 1997; Theorem 1.1.1.

%D P. Frankl, Extremal sets systems, Chap. 24 of R. L. Graham et al., eds, Handbook of Combinatorics, North-Holland.

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

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

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(b), p. 452.

%H G. C. Greubel, <a href="/A001405/b001405.txt">Table of n, a(n) for n = 0..1000</a>(terms 0 to 200 computed by T. D. Noe)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards Applied Math.Series 55, Tenth Printing, 1972.

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

%H A. Asinowski, G. Rote, <a href="https://arxiv.org/abs/1502.04925">Point sets with many non-crossing matchings</a>, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.

%H Shaun V. Ault and Charles Kicey, <a href="http://dx.doi.org/10.1016/j.disc.2014.05.020">Counting paths in corridors using circular Pascal arrays</a>, Discrete Mathematics (2014).

%H Axel Bacher, <a href="https://arxiv.org/abs/1802.06030">Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths</a>, arXiv:1802.06030 [cs.DS], 2018.

%H Armen G. Bagdasaryan, Ovidiu Bagdasar, <a href="https://doi.org/10.1016/j.endm.2018.05.012">On some results concerning generalized arithmetic triangles</a>, Electronic Notes in Discrete Mathematics (2018) Vol. 67, 71-77.

%H C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, <a href="https://arxiv.org/abs/1609.06473">Explicit formulas for enumeration of lattice paths: basketball and the kernel method</a>, arXiv preprint arXiv:1609.06473 [math.CO], 2016.

%H Elena Barcucci, Antonio Bernini, 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, Sergey Kirgizov and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.

%H J.-L. Baril, A. Petrossian, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Baril/baril3.html">Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two</a>, J. Int. Seq. 18 (2015) 15.7.1

%H P. Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry2/barry73.html">A Note on a One-Parameter Family of Catalan-Like Numbers</a>, JIS 12 (2009) 09.5.4

%H P. Barry and A. Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry1/barry202.html">Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays</a>, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012

%H F. Bergeron, L. Favreau and D. Krob, <a href="http://dx.doi.org/10.1016/0012-365X(94)00148-C">Conjectures on the enumeration of tableaux of bounded height</a>, Discrete Math, vol. 139, no. 1-3 (1995), 463-468.

%H Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, <a href="https://arxiv.org/abs/1310.7003">Pattern-avoiding involutions: exact and asymptotic enumeration</a>, arxiv:1310.7003 [math.CO], 2013.

%H A. Bostan, <a href="https://www-apr.lip6.fr/sem-comb-slides/IHP-bostan.pdf">Computer Algebra for Lattice Path Combinatorics</a>, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.

%H Alin Bostan and Manuel Kauers, <a href="https://arxiv.org/abs/0811.2899">Automatic Classification of Restricted Lattice Walks</a>, arXiv:0811.2899 [math.CO], 2009.

%H H. Bottomley, <a href="/A001405/a001405.gif">Illustration of initial terms</a>

%H J. M. Campbell, <a href="https://doi.org/10.1016/j.disc.2016.09.025">The expansion of immaculate functions in the ribbon basis</a>, Discrete Math., 340 (2017), 1716-1726.

%H F. Disanto, A. Frosini, S. Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Rinaldi/square.html">Square involutions</a>, J. Int. Seq. 14 (2011) # 11.3.5.

%H F. Disanto and S. Rinaldi, <a href="http://puma.dimai.unifi.it/22_1/2-disanto_rinaldi.pdf">Symmetric convex permutominoes and involutions</a>, PU. M. A., Vol. 22 (2011), No. 1, pp. 39-60.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 77

%H J. R. Griggs, <a href="https://arxiv.org/abs/math/9304211">On the distribution of sums of residues</a>, arXiv:math/9304211 [math.NT], 1993.

%H O. Guibert and T. Mansour, <a href="http://www.emis.de/journals/SLC/wpapers/s48guimans.html">Restricted 132-involutions</a>, Séminaire Lotharingien de Combinatoire, B48a, 23 pp, 2002.

%H H. Gupta, <a href="http://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005a66_964.pdf">Enumeration of incongruent cyclic k-gons</a>, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964-999.

%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 Seqs., Vol. 3 (2000), #00.1.6.

%H Zachary Hamaker, Eric Marberg, <a href="https://arxiv.org/abs/1802.09805">Atoms for signed permutations</a>, arXiv:1802.09805 [math.CO], 2018.

%H F. Harary & R. W. Robinson, <a href="/A000108/a000108_18.pdf">The number of achiral trees</a>, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)

%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct 2011.

%H Cheyne Homberger, <a href="https://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint 1410.2657 [math.CO], 2014.

%H W. Cary Huffman and Vera Pless, <a href="https://doi.org/10.1017/CBO9780511807077">Fundamentals of Error Correcting Codes</a>, Cambridge University Press, 2003, Pages 7,252-282,338-393.

%H Christian Krattenthaler, 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 Jean-Philippe Labbé, Carsten Lange, <a href="https://arxiv.org/abs/1802.07978">Cambrian acyclic domains: counting c-singletons</a>, arXiv:1802.07978 [math.CO], 2018.

%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 P. Leroux and E. Rassart, <a href="https://arxiv.org/abs/math/9901135">Enumeration of Symmetry Classes of Parallelogram Polyominoes</a>, arXiv:math/9901135 [math.CO], 1999.

%H Steven Linton, James Propp, Tom Roby, Julian West, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Roby/roby4.html">Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.

%H D. Lubell, <a href="http://dx.doi.org/10.1016/S0021-9800(66)80035-2">A short proof of Sperner's lemma</a>, J. Combin. Theory, 1 (1966), 299.

%H Piera Manara and Claudio Perelli Cippo, <a href="http://puma.dimai.unifi.it/22_2/manara_perelli-cippo.pdf">The fine structure of 4321 avoiding involutions and 321 avoiding involutions</a>, PU. M. A. Vol. 22 (2011), 227-238.

%H Eric Marberg, Brendan Pawlowski, <a href="https://arxiv.org/abs/1806.11208">Stanley symmetric functions for signed involutions</a>, arXiv:1806.11208 [math.CO], 2018.

%H Victor Meally, <a href="/A002868/a002868.pdf">Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.</a>

%H D. Merlini, <a href="http://www.emis.de/journals/DMTCS/pdfpapers/dmAC0121.pdf">Generating functions for the area below some lattice paths</a>, Discrete Mathematics and Theoretical Computer Science AC, 2003, 217-228.

%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

%H M. A. Narcowich, <a href="http://www.jstor.org/stable/2028770">Problem 73-6</a>, SIAM Review, Vol. 16, No. 1, 1974, p. 97.

%H Ran Pan, <a href="http://www.math.ucsd.edu/~projectp/warmups/eP.html">Exercise P</a>, Project P.

%H Alon Regev, Amitai Regev, Doron Zeilberger, <a href="https://arxiv.org/abs/1507.03499">Identities in character tables of S_n</a>, arXiv preprint arXiv:1507.03499 [math.CO], 2015.

%H R. W. Robinson, F. Harary and A. T. Balaban, <a href="/A000625/a000625.pdf">Numbers of chiral and achiral alkanes and monosubstituted alkanes</a>, Tetrahedron 32 (3) (1976), 355-361. (Annotated scanned copy)

%H V. Shevelev, <a href="http://www.math.bgu.ac.il/~shevelev/Shevelev_Neclaces.pdf">Necklaces and convex k-gons</a>, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.

%H V. Shevelev, <a href="https://arxiv.org/abs/0710.1370">A problem of enumeration of two-color bracelets with several variations</a>, arXiv:0710.1370 [math.CO], May 05 2011.

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).

%H P. K. Stockmeyer, <a href="https://doi.org/10.1007/BFb0066456">The charm bracelet problem and its applications</a>, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

%H C. G. Wagner, <a href="/A001405/a001405.pdf">Letter to N. J. A. Sloane, Sep 30 1974</a>

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

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

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

%F a(n) = max C(n, k), 1 <= k <= n.

%F a(2*n) = A000984(n), a(2*n+1) = A001700(n).

%F Recurrence relation: a(0) = 1, a(1) = 1, and for n >= 2, (n+1)*a(n) = 2*a(n-1) + 4*(n-1)*a(n-2). - _Peter Bala_, Feb 28 2011

%F G.f.: (1+x*c(x^2))/sqrt(1-4*x^2) = 1/(1-x-x^2*c(x^2)); where c(x) = g.f. for Catalan numbers A000108.

%F G.f.: (-1+2*x+sqrt(1-4*x^2))/(2*x-4*x^2). - _Lee A. Newberg_, Apr 26 2010

%F G.f.: 1/(1-x-x^2/(1-x^2/(1-x^2/(1-x^2/(1-... (continued fraction). - _Paul Barry_, Aug 12 2009

%F a(0) = 1; a(2*m+2) = 2*a(2*m+1); a(2*m+1) = Sum_{k = 0..2*m} (-1)^k*a(k)*a(2m-k). - _Len Smiley_, Dec 09 2001

%F G.f.: (sqrt((1+2*x)/(1-2*x))-1)/(2*x). - _Vladeta Jovovic_, Apr 28 2003

%F The o.g.f. A(x) satisfies A(x)+x*A^2(x) = 1/(1-2*x). - _Peter Bala_, Feb 28 2011

%F E.g.f.: BesselI(0, 2*x) + BesselI(1, 2*x). - _Vladeta Jovovic_, Apr 28 2003

%F a(0) = 1; a(2m+2) = 2a(2m+1); a(2m+1) = 2a(2m) - c(m), where c(m)=A000108(m) are the Catalan numbers. - Christopher Hanusa (chanusa(AT)washington.edu), Nov 25 2003

%F a(n) = Sum_{k=0..n} (-1)^k*2^(n-k)*binomial(n, k)*A000108(k). - _Paul Barry_, Jan 27 2005

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*binomial(1, n-2k). - _Paul Barry_, May 13 2005

%F From _Paul Barry_, Nov 02 2004: (Start)

%F a(n) = Sum_{k=0..floor((n+1)/2)} (binomial(n+1, k)(cos((n-2*k+1)*Pi/2) + sin((n-2*k+1)*Pi/2)));

%F a(n) = Sum_{k=0..n+1}, (binomial(n+1, (n-k+1)/2)*(1-(-1)^(n-k))*(cos(k*Pi/2) + sin(k*Pi))/2). (End)

%F a(n) = Sum_{k=floor(n/2)..n} (binomial(n,n-k) - binomial(n,n-k-1)). - _Paul Barry_, Sep 06 2007

%F Inverse binomial transform of A005773 starting (1, 2, 5, 13, 35, 96, ...) and double inverse binomial transform of A001700. Row sums of triangle A132815. - _Gary W. Adamson_, Aug 31 2007

%F a(n) = Sum_{k=0..n} A120730(n,k). - _Philippe Deléham_, Oct 16 2008

%F a(n) = Sum_{k=0..floor(n/2)} (binomial(n,n-k) - binomial(n,n-k-1)). - Nishant Doshi (doshinikki2004(AT)gmail.com), Apr 06 2009

%F Conjectured: a(n) = 2^n*2F1(1/2,-n;2;2), useful for number of paths in 1-d for which the coordinate is never negative. - _Benjamin Phillabaum_, Feb 20 2011

%F a(2*m+1) = (2*m+1)*a(2*m)/(m+1), e.g., a(7)=(7/4)*a(6) = (7/4)*20 = 35. - _Jon Perry_, Jan 20 2011

%F From _Peter Bala_, Feb 28 2011: (Start)

%F Let F(x) be the logarithmic derivative of the o.g.f. A(x). Then 1+x*F(x) is the o.g.f. for A027306.

%F Let G(x) be the logarithmic derivative of 1+x*A(x). Then x*G(x) is the o.g.f. for A058622. (End)

%F Let M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [1,0,0,0,...] in the main diagonal; and V = the vector [1,0,0,0,...]. a(n) = M^n*V, leftmost term. - _Gary W. Adamson_, Jun 13 2011

%F Let M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [1,0,0,0,...] in the main diagonal. a(n) = M^n_{1,1}. - Corrected by _Gary W. Adamson_, Jan 30 2012

%F a(n) = A007318(n, floor(n/2)). - _Reinhard Zumkeller_, Nov 09 2011

%F a(n+1) = Sum_{k=0..n} a(n-k)*A097331(k) = a(n) + Sum_{k=0..(n-1)/2} A000108(k)*a(n-2k-1). - _Philippe Deléham_, Nov 27 2011

%F a(n) = A214282(n) - A214283(n), for n > 0. - _Reinhard Zumkeller_, Jul 14 2012

%F a(n) = Sum_{k=0..n} A168511(n,k)*(-1)^(n-k). - _Philippe Deléham_, Mar 19 2013

%F a(n+2*p-2) = Sum_{k=0..floor(n/2)} A009766(n-k+p-1, k+p-1) + binomial(n+2*p-2, p-2), for p >= 1. - _Johannes W. Meijer_, Aug 02 2013

%F O.g.f.: (1-x*c(x^2))/(1-2*x), with the o.g.f. c(x) of Catalan numbers A000108. See the rewritten formula given by Lee A. Newberg above. This is the o.g.f. for the row sums the Riordan triangle A053121. - _Wolfdieter Lang_, Sep 22 2013

%F a(n) ~ 2^n / sqrt(Pi * n/2). - _Charles R Greathouse IV_, Oct 23 2015

%F a(n) = 2^n*hypergeom([1/2,-n], [2], 2). - _Vladimir Reshetnikov_, Nov 02 2015

%F a(2*k) = Sum_{i=0..k} binomial(k, i)*binomial(k, i), a(2*k+1) = Sum_{i=0..k} binomial(k+1, i)*binomial(k, i). - _Juan A. Olmos_, Dec 21 2017

%e For n = 4, the a(4) = 6 distinct strings of length 4, each of which is a prefix of a string of balanced parentheses, are ((((, (((), (()(, ()((, ()(), and (()). - _Lee A. Newberg_, Apr 26 2010

%e There are a(5)=10 symmetric balanced strings of 5 pairs of parentheses:

%e [ 1] ((((()))))

%e [ 2] (((()())))

%e [ 3] ((()()()))

%e [ 4] ((())(()))

%e [ 5] (()()()())

%e [ 6] (()(())())

%e [ 7] (())()(())

%e [ 8] ()()()()()

%e [ 9] ()((()))()

%e [10] ()(()())() - _Joerg Arndt_, Jul 25 2011

%e G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 35*x^7 + 70*x^8 + ...

%e The a(4)=6 binary 4-tuples such that the number of 1's in the even positions is the same as the number of 1's in the odd positions are 0000, 1100, 1001, 0110, 0011, 1111. - _Juan A. Olmos_, Dec 21 2017

%p A001405 := n->binomial(n, floor(n/2)): seq(A001405(n), n=0..33);

%t Table[Binomial[n, Floor[n/2]], {n, 0, 40}] (* _Stefan Steinerberger_, Apr 08 2006 *)

%t Table[DifferenceRoot[Function[{a,n},{-4 n a[n]-2 a[1+n]+(2+n) a[2+n] == 0,a[1] == 1,a[2] == 1}]][n], {n, 30}] (* _Luciano Ancora_, Jul 08 2015 *)

%t Array[Binomial[#,Floor[#/2]]&,40,0] (* _Harvey P. Dale_, Mar 05 2018 *)

%o (PARI) a(n) = binomial(n, n\2);

%o (PARI) first(n) = x='x+O('x^n); Vec((-1+2*x+sqrt(1-4*x^2))/(2*x-4*x^2)) \\ _Iain Fox_, Dec 20 2017 (edited by _Iain Fox_, May 07 2018)

%o (Haskell)

%o a001405 n = a007318_row n !! (n `div` 2) -- _Reinhard Zumkeller_, Nov 09 2011

%o (Maxima) A001405(n):=binomial(n,floor(n/2))$

%o makelist(A001405(n),n,0,30); /* _Martin Ettl_, Nov 01 2012 */

%o (MAGMA) [Binomial(n, Floor(n/2)): n in [0..40]]; // _Vincenzo Librandi_, Nov 16 2014

%o (GAP) List([0..40],n->Binomial(n,Int(n/2))); # _Muniru A Asiru_, Apr 08 2018

%Y Row sums of Catalan triangle A053121.

%Y Enumerates the structures encoded by A061854 and A061855.

%Y First differences are in A037952.

%Y Apparently a(n) = lim_{k->infinity} A094718(k, n).

%Y Partial sums are in A036256. Column k=2 of A182172.

%Y Cf. A000984 is the odd indexes of this sequence.

%Y Cf. A000712, A001006, A001700, A005773, A005817, A007578, A007579, A022916, A022917 (permutation patterns mod k), A049401, A051920, A063886, A130820, A132815, A153585, A239241, A265848.

%K nonn,easy,nice,core

%O 0,3

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 03:17 EST 2019. Contains 319184 sequences. (Running on oeis4.)