|
| |
|
|
A001405
|
|
Central binomial coefficients: C(n,floor(n/2)).
(Formerly M0769 N0294)
|
|
302
|
|
|
|
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 E. (labos(AT)ana.sote.hu), 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 Catalans [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 Catalans, 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 (torstenmuetze(AT)gmx.de), 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 4 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 (zabrocki(AT)mathstat.yorku.ca), Mar 24 2007
Hankel transform of this sequence forms A000012 = [1,1,1,1,1,1,1,...] . - Philippe DELEHAM, 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 [From Gary W. Adamson, Dec 28 2008]
Second binomial transform of A168491. [From Philippe DELEHAM, 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. [From 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 Gerard, 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)) [From 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 [From 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]
a(n) = A007318(n, floor(n/2)). [Reinhard Zumkeller, Nov 09 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, 15 May 2012]
For n > 0: a(n) = A214282(n) - A214283(n). - Reinhard Zumkeller, Jul 14 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.
|
|
|
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, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 135.
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.
F. Disanto and S. Rinaldi, Symmetric convex permutominoes and involutions, PU. M. A., Vol. 22 (2011), No. 1, pp. 39-60; http://www.mat.unisi.it/newsito/puma/public_html/22_1/2-disanto_rinaldi.pdf
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.
H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964-999.
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; http://repository.wit.ie/1693/1/AoifeThesis.pdf
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; http://www.mat.unisi.it/newsito/puma/public_html/22_2/manara_perelli-cippo.pdf. - From N. J. A. Sloane, Oct 13 2012
J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
M. A. Narcowich, Problem 73-6, SIAM Review, Vol. 16, No. 1, 1974, p. 97.
V. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
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].
H. Bottomley, Illustration of initial terms
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 77
J. R. Griggs, On the distribution of sums of residues
O. Guibert and T. Mansour, Restricted 132-involutions
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
P. Leroux and E. Rassart, [math/9901135] Enumeration of Symmetry Classes of Parallelogram Polyominoes
D. Merlini, Generating functions for the area below some lattice paths
V. Shevelev, A problem of enumeration of two-color bracelets with several variations
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
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.
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, 28 Feb 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). [From 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). [From 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 (smiley(AT)math.uaa.alaska.edu), 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, 28 Feb 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). [From Philippe DELEHAM, 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
Contribution from Peter Bala, 28 Feb 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. [From Gary W. Adamson, Jun 013 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+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). From Philippe Deléham, Nov 27 2011
E.g.f.: G(0) where G(k)= 1 + x/(k+1 - (k+1)*x/(x + (k+1)/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 25 2012
a(n) = Sum_{k, 0<=k<=n} A168511(n,k)*(-1)^(n-k). - Philippe Deléham, Mar 19 2013
|
|
|
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 (()). [From 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]
|
|
|
MAPLE
|
A001405 := n->binomial(n, floor(n/2));
|
|
|
MATHEMATICA
|
Table[Binomial[n, Floor[n/2]], {n, 0, 40}] (* Stefan Steinerberger, Apr 08 2006 *)
|
|
|
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 */
|
|
|
CROSSREFS
|
Cf. A051920. a(2*n)= A000984(n), a(2*n+1)= A001700(n).
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. A001006, A005817, A049401, A007579, A007578.
Cf. A005773, A001700, A132815.
Cf. A022916, A022917 (permutation patterns mod k).
Partial sums are in A036256.
A153585 [From Gary W. Adamson, Dec 28 2008]
Column k=2 of A182172. - Alois P. Heinz, May 30 2012
Sequence in context: A037031 A056202 * A126930 A210736 A036557 A173125
Adjacent sequences: A001402 A001403 A001404 * A001406 A001407 A001408
|
|
|
KEYWORD
|
nonn,easy,nice,core,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
