|
%I M0769 N0294 #637 Apr 20 2024 07:24:53
%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 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, gives A037952 apart from the initial term. - _Antti Karttunen_, Jun 05 2001 [This is correct because the g.f.'s satisfy (1+x*g001405(x))*g126120(x) = g001405(x) and g001405(x)*g126120(x) = g037952(x)/x. - _R. J. Mathar_, Sep 23 2021]
%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 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(floor(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
%C Closed under addition. - _Torlach Rush_, Apr 18 2019
%C The sequence starting (1, 2, 3, 6, ...) is the invert transform of A097331: (1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, ...). - _Gary W. Adamson_, Feb 22 2020
%C From _Gary W. Adamson_, Feb 24 2020: (Start)
%C The sequence is the culminating limit of an infinite set of sequences with convergents of 2*cos(Pi/N), N = (3, 5, 7, 9, ...).
%C The first few such sequences are:
%C N = 3: (1, 1, 1, 1, 1, 1, 1, 1, ...)
%C N = 5: (1, 1, 2, 3, 5, 8, 13, 21, ...) = A000045
%C N = 7: (1, 1, 2, 3, 6, 10, 19, 33, ...) = A028495, a(n)/a(n-1) tends to 1.801937...
%C N = 9 (1, 1, 2, 3, 6, 10, 20, 35, ...) = A061551, a(n)/a(n_1) tends to 1.879385...
%C ...
%C In the limit one gets the current sequence with ratio 2. (End)
%C a(n) is also the number of monotone lattice paths from (0,0) to (floor(n/2),ceiling(n/2)). These are the number of Grand Dyck paths when n is even. - _Nachum Dershowitz_, Aug 12 2020
%C The maximum number of preimages that a permutation of length n+1 can have under the consecutive-132-avoiding stack-sorting map. - _Colin Defant_, Aug 28 2020
%C Counts faro permutations of length n. Faro permutations are permutations avoiding the three consecutive patterns 231, 321 and 312. They are obtained by a perfect faro shuffle of two nondecreasing words of lengths differing by at most one. - _Sergey Kirgizov_, Jan 12 2021
%C Per "Sperner's Theorem", the largest possible familes of finite sets none of which contain any other sets in the family. - _Renzo Benedetti_, May 26 2021
%C a(n-1) are the incomplete, primitive Dyck paths of n steps without a first return: paths of U and D steps starting at the origin, never touching the horizontal axis later on, and ending above the horizontal axis. n=1: {U}, n=2: {UU}, n=3: {UUU, UUD}, n=4: {UUUU, UUUD, UUDU}, n=5: {UUUUU, UUUUD, UUUDD, UUDUU, UUUDU, UUDUD}. For comparison: A037952 counts incomplete Dyck paths with n steps with any number of intermediate returns to the horizontal axis, ending above the horizontal axis. - _R. J. Mathar_, Sep 24 2021
%C a(n) is the number of noncrossing partitions of [n] whose nontrivial blocks are of type {a,b}, with a <= n/2, b > n/2. - _Francesca Aicardi_, May 29 2022
%C Maximal coefficient of (1+x)^n. - _Vaclav Kotesovec_, Dec 30 2022
%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., Vol. 308 (2008), pp. 2544-2563.
%H A. Asinowski and 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, Volume 332 (October 2014), Pages 45-54.
%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 and 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, Vol. 67 (2018), pp. 71-77.
%H Taylor Ball, David Galvin, Katie Hyry, and Kyle Weingartner, <a href="https://arxiv.org/abs/1901.06579">Independent set and matching permutations</a>, arXiv:1901.06579 [math.CO], 2019.
%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, 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, 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 Jean-Luc Baril and 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., Vol. 18 (2015), Article 15.7.1.
%H Jean-Luc Baril, Alexander Burstein, and Sergey Kirgizov, <a href="https://arxiv.org/abs/2010.06270">Pattern statistics in faro words and permutations</a>, arXiv:2010.06270 [math.CO], 2020. See Table 1.
%H Paul 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, Vol. 12 (2009), Article 09.5.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., Vol. 22 (2019), Article 19.1.3.
%H Paul 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, Vol. 15 (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), pp. 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 Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.
%H Henry 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., Vol. 340 (2017), pp. 1716-1726.
%H Colin Defant and Kai Zheng, <a href="https://arxiv.org/abs/2008.12297">Stack-Sorting with Consecutive-Pattern-Avoiding Stacks</a>, arXiv:2008.12297 [math.CO], 2020.
%H Isaac DeJager, Madeleine Naquin, and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.
%H F. Disanto, A. Frosini, and 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, No. 1 (2011), pp. 39-60.
%H Justine Falque, Jean-Christophe Novelli, and Jean-Yves Thibon, <a href="https://arxiv.org/abs/2106.05248">Pinnacle sets revisited</a>, arXiv:2106.05248 [math.CO], 2021.
%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="https://web.archive.org/web/20200806162943/http://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005a66_964.pdf">Enumeration of incongruent cyclic k-gons</a>, Indian J. Pure and Appl. Math., Vol. 10, No. 8 (1979), pp. 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 Seq., Vol. 3 (2000), Article 00.1.6.
%H Zachary Hamaker and Eric Marberg, <a href="https://arxiv.org/abs/1802.09805">Atoms for signed permutations</a>, arXiv:1802.09805 [math.CO], 2018.
%H F. Harary and R. W. Robinson, <a href="/A000108/a000108_18.pdf">The number of achiral trees</a>, Jnl. Reine Angewandte Mathematik, Vol. 278 (1975), pp. 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 Zoe M. Himwich and Noah A. Rosenberg, <a href="https://arxiv.org/abs/1901.04465">Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees</a>, arXiv:1901.04465 [q-bio.pE] (2019); Adv. Appl. Math. 113 (2020), 101939.
%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 and Daniel Yaqubi, <a href="https://arxiv.org/abs/1802.05990">Some determinants of path generating functions, II</a>, Adv. Appl. Math., Vol. 101 (2018), pp. 232-265.
%H Jean-Philippe Labbé and 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, and 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), Article 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, Vol. 1 (1966), p. 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), pp. 227-238.
%H Eric Marberg and 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="https://doi.org/10.46298/dmtcs.3323">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 Saulo Queiroz, João Vilela, and Edmundo Monteiro, <a href="https://doi.org/10.1109/WD.2019.8734233">What is the Cost of the Index Selector Task for OFDM with Index Modulation?</a>, 2019 Wireless Days (WD).
%H Saulo Queiroz, João P. Vilela, and Edmundo Monteiro, <a href="https://arxiv.org/abs/2002.09382">Optimal Mapper for OFDM with Index Modulation: A Spectro-Computational Analysis</a>, arXiv:2002.09382 [eess.SP], 2020. See also <a href="https://doi.org/10.1109/ACCESS.2020.2986131">IEEE Access</a> (2020) Vol. 8, 68365-68378.
%H Alon Regev, Amitai Regev, and 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, Vol. 32, No. 3 (1976), pp. 355-361. (Annotated scanned copy)
%H Arnold Saunders, <a href="https://arxiv.org/abs/1906.02720">A Class of Random Recursive Tree Algorithms with Deletion</a>, arXiv:1906.02720 [math.PR], 2019.
%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., Vol. 35, No. 5 (2004), pp. 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 Emanuel Sperner, <a href="https://doi.org/10.1007/BF01171114">Ein Satz über Untermengen einer endlichen Menge</a>, Mathematische Zeitschrift (in German), Vol. 27, No. 1 (1928), pp. 544-548.
%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 P. J. Stockmeyer, <a href="/A006078/a006078.pdf">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. [Scanned annotated and corrected copy]
%H I. Tasoulas, K. Manes, A. Sapounakis, and P. Tsikouras, <a href="https://arxiv.org/abs/1911.10883">Chains with Small Intervals in the Lattice of Binary Paths</a>, arXiv:1911.10883 [math.CO], 2019.
%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 W. H. W. Wong and E. G. Tay, <a href="https://arxiv.org/abs/2001.01910">On Cross-intersecting Sperner Families</a>, arXiv:2001.01910 [math.CO], 2020.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>.
%F a(n) = max_{k=0..n} binomial(n, k).
%F a(2*n) = A000984(n), a(2*n+1) = A001700(n).
%F By symmetry, a(n) = binomial(n, ceiling(n/2)). - _Labos Elemer_, Mar 20 2003
%F P-recursive with recurrence: 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(2*m-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(2*m+2) = 2*a(2*m+1); a(2*m+1) = 2*a(2*m) - 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-2*k). - _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,k) - binomial(n,k-1)). - Nishant Doshi (doshinikki2004(AT)gmail.com), Apr 06 2009
%F 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
%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-2*k-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
%F a(0) = 1, a(n) = 2 * a(n-1) for even n, a(n) = (2*n/(n+1)) * a(n-1) for odd n. - _James East_, Sep 25 2019
%F a(n) = A037952(n) + A000108(n/2) where A(.)=0 for non-integer argument. - _R. J. Mathar_, Sep 23 2021
%F From _Amiram Eldar_, Mar 10 2022: (Start)
%F Sum_{n>=0} 1/a(n) = 2*Pi/(3*sqrt(3)) + 2.
%F Sum_{n>=0} (-1)^n/a(n) = 2/3 - 2*Pi/(9*sqrt(3)). (End)
%F For k>2, Sum_{n>=0} a(n)/k^n = (sqrt((k+2)/(k-2)) - 1)*k/2. - _Vaclav Kotesovec_, May 13 2022
%F From _Peter Bala_, Mar 24 2023: (Start)
%F a(n) = Sum_{k = 0..n+1} (-1)^(k+binomial(n+2,2)) * k/(n+1) * binomial(n+1,k)^2.
%F (n + 1)*(2*n - 1)*a(n) = (-1)^(n+1)*2*a(n-1) + 4*(n - 1)*(2*n + 1)*a(n-2) with a(0) = a(1) = 1. (End)
%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
%o (Python)
%o from math import comb
%o def A001405(n): return comb(n,n//2) # _Chai Wah Wu_, Jun 07 2022
%Y Row sums of Catalan triangle A053121 and of symmetric Dyck paths A088855.
%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. Column k=1 of A335570.
%Y Bisections give A000984 (even part), A001700 (odd part). - _Nachum Dershowitz_, Aug 12 2020
%Y Cf. A000984 gives the odd-indexed terms 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.
%Y Cf. A097331.
%Y Cf. A000045, A028495, A061551
%Y Cf. A107373, A340567, A340568, A340569 (popularity of certain patterns in faro permutations). - _Sergey Kirgizov_, Jan 12 2021
%K nonn,easy,nice,core,walk
%O 0,3
%A _N. J. A. Sloane_
|
