login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001405 a(n) = binomial(n, floor(n/2)).
(Formerly M0769 N0294)
331
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)=C(n,ceiling(n/2)). - Labos Elemer, Mar 20 2003

Sperner's theorem says that this is the maximal number of subsets of an n-set 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..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

Image of Catalan numbers A000108 under the Riordan array (1/(1-2x),-x/(1-2x)) 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 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

a(n) is odd iff n=2^k-1 - Jon Perry, May 05 2005

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

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(0<i<=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>ceil(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)). - M. Dols (markdols99(AT)yahoo.com), Jul 15 2010

For n>=2, a(n-1) is the number of incongruent two-color bracelets of 2*n-1 beads, n from them are black (A007123), having a diameter of symmetry. - Vladimir Shevelev, May 03 2011

The number of permutations of n elements where p(k-2) < 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(n-2)). - 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 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

Number of symmetric standard Young tableaux of shape (n,n). - Ran Pan, Apr 10 2015

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.

- Luciano Ancora, May 09 2015

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

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, Springer-Verlag, 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, North-Holland.

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.

P. K. Stockmeyer, The charm bracelet problem and its applications, 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.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..200

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.

A. Asinowski, G. Rote, Point sets with many non-crossing 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).

P. Barry, A Note on a One-Parameter Family of Catalan-Like Numbers, JIS 12 (2009) 09.5.4

P. Barry and A. Hennessy, Four-term 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. 1-3 (1995), 463-468.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding 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.

H. Bottomley, Illustration of initial terms

F. Disanto and S. Rinaldi,Symmetric convex permutominoes and involutions, PU. M. A., Vol. 22 (2011), No. 1, pp. 39-60.

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 132-involutions, Séminaire Lotharingien de Combinatoire, B48a, 23 pp, 2002.

H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964-999.

R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6.

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.

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), 227-238.

D. Merlini, Generating functions for the area below some lattice paths, Discrete Mathematics and Theoretical Computer Science AC, 2003, 217-228.

T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

M. A. Narcowich, Problem 73-6, 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, 2015

V. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.

V. Shevelev, A problem of enumeration of two-color 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).

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(n-1) + 4*(n-1)*a(n-2). - Peter Bala, Feb 28 2011

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.

G.f.: (-1+2*x+sqrt(1-4*x^2))/(2*x-4*x^2). - Lee A. Newberg, Apr 26 2010

G.f.: 1/(1-x-x^2/(1-x^2/(1-x^2/(1-x^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((-1)^k*a(k)*a(2m-k), k = 0..2*m). - Len Smiley, Dec 09 2001

G.f.: (sqrt((1+2*x)/(1-2*x))-1)/(2*x). - Vladeta Jovovic, Apr 28 2003

The o.g.f. A(x) satisfies A(x)+x*A^2(x) = 1/(1-2*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^(n-k)*binomial(n, k)*A000108(k)}. - Paul Barry, Jan 27 2005

a(n) = sum{k=0..floor(n/2), binomial(n, k)*binomial(1, n-2k)}. - Paul Barry, May 13 2005

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))};

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}. - Paul Barry, Nov 02 2004

a(n) = sum{k=floor(n/2)..n, C(n,n-k)-C(n,n-k-1)}. - 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_{0<=k<=n} A120730(n,k). - Philippe Deléham, Oct 16 2008

a(n) = sum{k=0..floor(n/2), C(n,n-k)-C(n,n-k-1)}. - 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 1-d 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<=k<=n} a(n-k)*A097331(k) = a(n)+ Sum_{k, 0<=k<=(n-1)/2} A000108(k)*a(n-2k-1). - 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<=k<=n} A168511(n,k)*(-1)^(n-k). - Philippe Deléham, Mar 19 2013

a(n+2*p-2) = sum(A009766(n-k+p-1, k+p-1), k=0..floor(n/2)) + binomial(n+2*p-2, p-2), for p >= 1. - Johannes W. Meijer, Aug 02 2013

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

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

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 + ...

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 *)

PROG

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

(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

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=1..inf, A094718(k, n)].

Cf. A051920, A001006, A005817, A049401, A007579, A007578, A005773, A001700, A132815, A022916, A153585, A022917 (permutation patterns mod k).

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

Cf. A000984 is the odd indexes of this sequence.

Cf. A265848, A130820.

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 28 01:03 EDT 2016. Contains 275914 sequences.