

A001405


a(n) = binomial(n, floor(n/2)).
(Formerly M0769 N0294)


354



1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, 77558760, 155117520, 300540195, 601080390, 1166803110
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

By symmetry, a(n) = binomial(n, ceiling(n/2)).  Labos Elemer, Mar 20 2003
Sperner's theorem says that this is the maximal number of subsets of an nset such that no one contains another.
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
Number of ordered trees with n+1 edges, having nonroot nodes of outdegree 0 or 2.  Emeric Deutsch, Aug 02 2002
Gives for n>=1 the maximum absolute column sum norm of the inverse of the Vandermonde matrix (a_ij) i=0..n1, j=0..n1 with a_00=1 and a_ij=i^j for (i,j)!=(0,0).  Torsten Muetze, Feb 06 2004
Image of Catalan numbers A000108 under the Riordan array (1/(12x),x/(12x)) or A065109.  Paul Barry, Jan 27 2005
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
Number of dispersed Dyck paths of length n; they are defined as concatenations of Dyck paths and (1,0)steps on the xaxis; 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
a(n) is odd iff n=2^k1.  Jon Perry, May 05 2005
An inverse Chebyshev transform of binomial(1,n)=(1,1,0,0,0,...) where g(x)>(1/sqrt(14*x^2))*g(x*c(x^2)), with c(x) the g.f. of A000108.  Paul Barry, May 13 2005
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
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
Also the number of standard tableaux of height <= 2.  Mike Zabrocki, Mar 24 2007
Hankel transform of this sequence forms A000012 = [1,1,1,1,1,1,1,...].  Philippe Deléham, Oct 24 2007
A001263 * [1, 2, 3, 4, 5, ...] = [1, 1, 2, 3, 6, 10, 20, 35, 70, 126, ...].  Gary W. Adamson, Jan 02 2008
Equals right border of triangle A153585.  Gary W. Adamson, Dec 28 2008
Second binomial transform of A168491.  Philippe Deléham, Nov 27 2009
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
Number of symmetric balanced strings of n pairs of parentheses; see example.  Joerg Arndt, Jul 25 2011
a(n) is the number of permutation patterns modulo 2.  Olivier Gérard, Feb 25 2011
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
For n >= 2, a(n1) is the number of incongruent twocolor bracelets of 2*n1 beads, n of which are black (A007123), having a diameter of symmetry.  Vladimir Shevelev, May 03 2011
The number of permutations of n elements where p(k2) < p(k) for all k.  Joerg Arndt, Jul 23 2011
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
a(n) is the number of symmetric Dyck paths of length 2n.  Matt Watson, Sep 26 2012
a(n) is divisible by A000108([n/2]) = abs(A129996(n2)).  Paul Curtz, Oct 23 2012
a(n) is the number of permutations of length n avoiding both 213 and 231 in the classical sense which are breadthfirst search reading words of increasing unarybinary trees. For more details, see the entry for permutations avoiding 231 at A245898.  Manda Riehl, Aug 05 2014
Number of symmetric standard Young tableaux of shape (n,n).  Ran Pan, Apr 10 2015
From Luciano Ancora, May 09 2015: (Start)
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:
[1], [1], 1, 1, 1, 1, 1, ... A000012
1, [2], [3], 4, 5, 6, 7, ...
1, 3, [6], [10], 15, 21, 28, ...
1, 4, 10, [20], [35], 56, 84, ...
1, 5, 15, 35, [70], [126], 210, ...
Sequences in second formula are the mixed diagonals shown in this array. (End)
a(n) = A265848(n,n).  Reinhard Zumkeller, Dec 24 2015
The constant Sum_{n >= 0} a(n)/n! is 1 + A130820.  Peter Bala, Jul 02 2016
Number of meanders (walks starting at the origin and ending at any altitude >= 0 that may touch but never go below the xaxis) with n steps from {1,1}.  David Nguyen, Dec 20 2016
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
Number of binary ntuples 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
Equivalently, a(n) is the number of subsets of {1,...,n} containing as many even numbers as odd numbers.  Gus Wiseman, Mar 17 2018
a(n) is the number of Dyck paths with semilength = n+1, returns to the xaxis = 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 xaxis: UududdUdUd, UdUuddUudd, UuddUuddUd, UdUdUududd, UuddUdUudd, UdUududdUd.  Roger Ford, Dec 29 2017
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^(n1)) denote the identity matrix of order 2^(n1), it has been conjectured that the dimension of the kernel of C_n(R, H)  I(2^(n1)) is always equal to a(n1).  John M. Campbell, Mar 30 2018
The number of Uequivalence classes of Łukasiewicz paths. Łukasiewicz paths are Uequivalent iff the positions of pattern U are identical in these paths.  Sergey Kirgizov, Apr 2018


REFERENCES

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.
M. Aigner and G. M. Ziegler, Proofs from The Book, SpringerVerlag, Berlin, 1999; see p. 135.
K. Engel, Sperner Theory, Camb. Univ. Press, 1997; Theorem 1.1.1.
P. Frankl, Extremal sets systems, Chap. 24 of R. L. Graham et al., eds, Handbook of Combinatorics, NorthHolland.
J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(b), p. 452.


LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000(terms 0 to 200 computed by T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math.Series 55, Tenth Printing, 1972.
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 25442563.
A. Asinowski, G. Rote, Point sets with many noncrossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics (2014).
Axel Bacher, Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths, arXiv:1802.06030 [cs.DS], 2018.
C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv preprint arXiv:1609.06473 [math.CO], 2016.
JeanLuc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
J.L. Baril, A. Petrossian, Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two, J. Int. Seq. 18 (2015) 15.7.1
P. Barry, A Note on a OneParameter Family of CatalanLike Numbers, JIS 12 (2009) 09.5.4
P. Barry and A. Hennessy, Fourterm Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2.  From N. J. A. Sloane, Sep 21 2012
F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math, vol. 139, no. 13 (1995), 463468.
Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Patternavoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003 [math.CO], 2013.
A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.
Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2009.
H. Bottomley, Illustration of initial terms
J. M. Campbell, The expansion of immaculate functions in the ribbon basis, Discrete Math., 340 (2017), 17161726.
F. Disanto, A. Frosini, S. Rinaldie, Square involuations, J. Int. Seq. 14 (2011) # 11.3.5
F. Disanto and S. Rinaldi, Symmetric convex permutominoes and involutions, PU. M. A., Vol. 22 (2011), No. 1, pp. 3960.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 77
J. R. Griggs, On the distribution of sums of residues, arXiv:math/9304211 [math.NT], 1993.
O. Guibert and T. Mansour, Restricted 132involutions, Séminaire Lotharingien de Combinatoire, B48a, 23 pp, 2002.
H. Gupta, Enumeration of incongruent cyclic kgons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964999.
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6.
Zachary Hamaker, Eric Marberg, Atoms for signed permutations, arXiv:1802.09805 [math.CO], 2018.
F. Harary & R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322335. (Annotated scanned copy)
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct 2011.
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
Christian Krattenthaler, Daniel Yaqubi, Some determinants of path generating functions, II, arXiv:1802.05990 [math.CO], 2018.
JeanPhilippe Labbé, Carsten Lange, Cambrian acyclic domains: counting csingletons, arXiv:1802.07978 [math.CO], 2018.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
P. Leroux and E. Rassart, Enumeration of Symmetry Classes of Parallelogram Polyominoes, arXiv:math/9901135 [math.CO], 1999.
Steven Linton, James Propp, Tom Roby, Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.
D. Lubell, A short proof of Sperner's lemma, J. Combin. Theory, 1 (1966), 299.
Piera Manara and Claudio Perelli Cippo, The fine structure of 4321 avoiding involutions and 321 avoiding involutions, PU. M. A. Vol. 22 (2011), 227238.
Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.
D. Merlini, Generating functions for the area below some lattice paths, Discrete Mathematics and Theoretical Computer Science AC, 2003, 217228.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167176. [Annotated, scanned copy]
M. A. Narcowich, Problem 736, SIAM Review, Vol. 16, No. 1, 1974, p. 97.
Ran Pan, Exercise P, Project P.
Alon Regev, Amitai Regev, Doron Zeilberger, Identities in character tables of S_n, arXiv preprint arXiv:1507.03499 [math.CO], 2015.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355361. (Annotated scanned copy)
V. Shevelev, Necklaces and convex kgons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629638.
V. Shevelev, A problem of enumeration of twocolor bracelets with several variations, arXiv:0710.1370 [math.CO], May 05 2011.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. SpringerVerlag, 1974.
C. G. Wagner, Letter to N. J. A. Sloane, Sep 30 1974
Eric Weisstein's World of Mathematics, Central Binomial Coefficient
Eric Weisstein's World of Mathematics, Quota System
Index entries for "core" sequences


FORMULA

a(n) = max C(n, k), 1 <= k <= n.
a(2*n) = A000984(n), a(2*n+1) = A001700(n).
Recurrence relation: a(0) = 1, a(1) = 1, and for n >= 2, (n+1)*a(n) = 2*a(n1) + 4*(n1)*a(n2).  Peter Bala, Feb 28 2011
G.f.: (1+x*c(x^2))/sqrt(14*x^2) = 1/(1xx^2*c(x^2)); where c(x) = g.f. for Catalan numbers A000108.
G.f.: (1+2*x+sqrt(14*x^2))/(2*x4*x^2).  Lee A. Newberg, Apr 26 2010
G.f.: 1/(1xx^2/(1x^2/(1x^2/(1x^2/(1... (continued fraction).  Paul Barry, Aug 12 2009
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(2mk).  Len Smiley, Dec 09 2001
G.f.: (sqrt((1+2*x)/(12*x))1)/(2*x).  Vladeta Jovovic, Apr 28 2003
The o.g.f. A(x) satisfies A(x)+x*A^2(x) = 1/(12*x).  Peter Bala, Feb 28 2011
E.g.f.: BesselI(0, 2*x) + BesselI(1, 2*x).  Vladeta Jovovic, Apr 28 2003
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
a(n) = Sum_{k=0..n} (1)^k*2^(nk)*binomial(n, k)*A000108(k).  Paul Barry, Jan 27 2005
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*binomial(1, n2k).  Paul Barry, May 13 2005
From Paul Barry, Nov 02 2004: (Start)
a(n) = Sum_{k=0..floor((n+1)/2)} (binomial(n+1, k)(cos((n2*k+1)*Pi/2) + sin((n2*k+1)*Pi/2)));
a(n) = Sum_{k=0..n+1}, (binomial(n+1, (nk+1)/2)*(1(1)^(nk))*(cos(k*Pi/2) + sin(k*Pi))/2). (End)
a(n) = Sum_{k=floor(n/2)..n} (binomial(n,nk)  binomial(n,nk1)).  Paul Barry, Sep 06 2007
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
a(n) = Sum_{k=0..n} A120730(n,k).  Philippe Deléham, Oct 16 2008
a(n) = Sum_{k=0..floor(n/2)} (binomial(n,nk)  binomial(n,nk1)).  Nishant Doshi (doshinikki2004(AT)gmail.com), Apr 06 2009
Conjectured: a(n) = 2^n*2F1(1/2,n;2;2), useful for number of paths in 1d for which the coordinate is never negative.  Benjamin Phillabaum, Feb 20 2011
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
From Peter Bala, Feb 28 2011: (Start)
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.
Let G(x) be the logarithmic derivative of 1+x*A(x). Then x*G(x) is the o.g.f. for A058622. (End)
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
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
a(n) = A007318(n, floor(n/2)).  Reinhard Zumkeller, Nov 09 2011
a(n+1) = Sum_{k=0..n} a(nk)*A097331(k) = a(n) + Sum_{k=0..(n1)/2} A000108(k)*a(n2k1).  Philippe Deléham, Nov 27 2011
a(n) = A214282(n)  A214283(n), for n > 0.  Reinhard Zumkeller, Jul 14 2012
a(n) = Sum_{k=0..n} A168511(n,k)*(1)^(nk).  Philippe Deléham, Mar 19 2013
a(n+2*p2) = Sum_{k=0..floor(n/2)} A009766(nk+p1, k+p1) + binomial(n+2*p2, p2), for p >= 1.  Johannes W. Meijer, Aug 02 2013
O.g.f.: (1x*c(x^2))/(12*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
a(n) ~ 2^n / sqrt(Pi * n/2).  Charles R Greathouse IV, Oct 23 2015
a(n) = 2^n*hypergeom([1/2,n], [2], 2).  Vladimir Reshetnikov, Nov 02 2015
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


EXAMPLE

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
There are a(5)=10 symmetric balanced strings of 5 pairs of parentheses:
[ 1] ((((()))))
[ 2] (((()())))
[ 3] ((()()()))
[ 4] ((())(()))
[ 5] (()()()())
[ 6] (()(())())
[ 7] (())()(())
[ 8] ()()()()()
[ 9] ()((()))()
[10] ()(()())()  Joerg Arndt, Jul 25 2011
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 + ...
The a(4)=6 binary 4tuples 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


MAPLE

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


MATHEMATICA

Table[Binomial[n, Floor[n/2]], {n, 0, 40}] (* Stefan Steinerberger, Apr 08 2006 *)
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 *)
Array[Binomial[#, Floor[#/2]]&, 40, 0] (* Harvey P. Dale, Mar 05 2018 *)


PROG

(PARI) a(n) = binomial(n, n\2);
(PARI) first(n) = x='x+O('x^n); Vec((1+2*x+sqrt(14*x^2))/(2*x4*x^2)) \\ Iain Fox, Dec 20 2017 (edited by Iain Fox, May 07 2018)
(Haskell)
a001405 n = a007318_row n !! (n `div` 2)  Reinhard Zumkeller, Nov 09 2011
(Maxima) A001405(n):=binomial(n, floor(n/2))$
makelist(A001405(n), n, 0, 30); /* Martin Ettl, Nov 01 2012 */
(MAGMA) [Binomial(n, Floor(n/2)): n in [0..40]]; // Vincenzo Librandi, Nov 16 2014
(GAP) List([0..40], n>Binomial(n, Int(n/2))); # Muniru A Asiru, Apr 08 2018


CROSSREFS

Row sums of Catalan triangle A053121.
Enumerates the structures encoded by A061854 and A061855.
First differences are in A037952.
Apparently a(n) = lim_{k>infinity} A094718(k, n).
Partial sums are in A036256. Column k=2 of A182172.
Cf. A000984 is the odd indexes of this sequence.
Cf. A000712, A001006, A001700, A005773, A005817, A007578, A007579, A022916, A022917 (permutation patterns mod k), A049401, A051920, A063886, A130820, A132815, A153585, A239241, A265848.
Sequence in context: A037031 A056202 * A126930 A210736 A036557 A173125
Adjacent sequences: A001402 A001403 A001404 * A001406 A001407 A001408


KEYWORD

nonn,easy,nice,core


AUTHOR

N. J. A. Sloane


STATUS

approved



