cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 38 results. Next

A001700 a(n) = binomial(2*n+1, n+1): number of ways to put n+1 indistinguishable balls into n+1 distinguishable boxes = number of (n+1)-st degree monomials in n+1 variables = number of monotone maps from 1..n+1 to 1..n+1.

Original entry on oeis.org

1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078, 5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650, 17672631900, 68923264410, 269128937220, 1052049481860, 4116715363800, 16123801841550, 63205303218876, 247959266474052
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

To show for example that C(2n+1, n+1) is the number of monotone maps from 1..n + 1 to 1..n + 1, notice that we can describe such a map by a nondecreasing sequence of length n + 1 with entries from 1 to n + 1. The number k of increases in this sequence is anywhere from 0 to n. We can specify these increases by throwing k balls into n+1 boxes, so the total is Sum_{k = 0..n} C((n+1) + k - 1, k) = C(2*n+1, n+1).
Also number of ordered partitions (or compositions) of n + 1 into n + 1 parts. E.g., a(2) = 10: 003, 030, 300, 012, 021, 102, 120, 210, 201, 111. - Mambetov Bektur (bektur1987(AT)mail.ru), Apr 17 2003
Also number of walks of length n on square lattice, starting at origin, staying in first and second quadrants. - David W. Wilson, May 05 2001. (E.g., for n = 2 there are 10 walks, all starting at 0, 0: 0, 1 -> 0, 0; 0, 1 -> 1, 1; 0, 1 -> 0, 2; 1, 0 -> 0, 0; 1, 0 -> 1, 1; 1, 0 -> 2, 0; 1, 0 -> 1, -1; -1, 0 -> 0, 0; -1, 0 -> -1, 1; -1, 0-> -2, 0.)
Also total number of leaves in all ordered trees with n + 1 edges.
Also number of digitally balanced numbers [A031443] from 2^(2*n+1) to 2^(2*n+2). - Naohiro Nomoto, Apr 07 2001
Also number of ordered trees with 2*n + 2 edges having root of even degree and nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002
Also number of paths of length 2*d(G) connecting two neighboring nodes in optimal chordal graph of degree 4, G(2*d(G)^2 + 2*d(G) + 1, 2d(G) + 1), where d(G) = diameter of graph G. - S. Bujnowski (slawb(AT)atr.bydgoszcz.pl), Feb 11 2002
Define an array by m(1, j) = 1, m(i, 1) = i, m(i, j) = m(i, j-1) + m(i-1, j); then a(n) = m(n, n), diagonal of A165257 - Benoit Cloitre, May 07 2002
Also the numerator of the constant term in the expansion of cos^(2*n)(x) or sin^(2*n)(x) when the denominator is 2^(2*n-1). - Robert G. Wilson v
Consider the expansion of cos^n(x) as a linear combination of cosines of multiple angles. If n is odd, then the expansion is a combination of a*cos((2*k-1)*x)/2^(n-1) for all 2*k - 1 <= n. If n is even, then the expansion is a combination of a*cos(2k*x)/2^(n-1) terms plus a constant. "The constant term, [a(n)/2^(2n-1)], is due to the fact that [cos^2n(x)] is never negative, i.e., electrical engineers would say the average or 'dc value' of [cos^(2*n)(x)] is [a(n)/2^(2*n-1)]. The dc value of [cos^(2*n-1)(x)] on the other hand, is zero because it is symmetrical about the horizontal axis, i.e., it is negative and positive equally." Nahin[62] - Robert G. Wilson v, Aug 01 2002
Also number of times a fixed Dyck word of length 2*k occurs in all Dyck words of length 2*n + 2*k. Example: if the fixed Dyck word is xyxy (k = 2), then it occurs a(1) = 3 times in the 5 Dyck words of length 6 (n = 1): (xy[xy)xy], xyxxyy, xxyyxy, x(xyxy)y, xxxyyy (placed between parentheses). - Emeric Deutsch, Jan 02 2003
a(n+1) is the determinant of the n X n matrix m(i, j) = binomial(2*n-i, j). - Benoit Cloitre, Aug 26 2003
a(n-1) = (2*n)!/(2*n!*n!), formula in [Davenport] used by Gauss for the special case prime p = 4*n + 1: x = a(n-1) mod p and y = x*(2n)! mod p are solutions of p = x^2 + y^2. - Frank Ellermann. Example: For prime 29 = 4*7 + 1 use a(7-1) = 1716 = (2*7)!/(2*7!*7!), 5 = 1716 mod 29 and 2 = 5*(2*7)! mod 29, then 29 = 5*5 + 2*2.
The number of compositions of 2*n, say c_1 + c_2 + ... + c_k = 2n, satisfy that Sum_{i = 1..j} c_i < 2*j for all j = 1..k, or equivalently, the number of subsets, say S, of [2*n-1] = {1, 2, ..., 2*n-1} with at least n elements such that if 2k is in S, then there must be at least k elements in S smaller than 2k. E.g., a(2) = 3 because we can write 4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1. - Ricky X. F. Chen (ricky_chen(AT)mail.nankai.edu.cn), Jul 30 2006
The number of walks of length 2*n + 1 on an infinite linear lattice that begin at the origin and end at node (1). Also the number of paths on a square lattice from the origin to (n+1, n) that use steps (1,0) and (0,1). Also number of binary numbers of length 2*n + 1 with n + 1 ones and n zeros. - Stefan Hollos (stefan(AT)exstrom.com), Dec 10 2007
If Y is a 3-subset of an 2*n-set X then, for n >= 3, a(n-1) is the number of n-subsets of X having at least two elements in common with Y. - Milan Janjic, Dec 16 2007
Also the number of rankings (preferential arrangements) of n unlabeled elements onto n levels when empty levels are allowed. - Thomas Wieder, May 24 2008
Also the Catalan transform of A000225 shifted one index, i.e., dropping A000225(0). - R. J. Mathar, Nov 11 2008
With offset 1. The number of solutions in nonnegative integers to X1 + X2 + ... + Xn = n. The number of terms in the expansion of (X1 + X2 + ... + Xn)^n. The coefficient of x^n in the expansion of (1 + x + x^2 + ...)^n. The number of distinct image sets of all functions taking [n] into [n]. - Geoffrey Critzer, Feb 22 2009
The Hankel transform of the aerated sequence 1, 0, 3, 0, 10, 0, ... is 1, 3, 3, 5, 5, 7, 7, ... (A109613(n+1)). - Paul Barry, Apr 21 2009
Also the number of distinct network topologies for a network of n items with 1 to n - 1 unidirectional connections to other objects in the network. - Anthony Bachler, May 05 2010
Equals INVERT transform of the Catalan numbers starting with offset 1. E.g.: a(3) = 35 = (1, 2, 5) dot (10, 3, 1) + 14 = 21 + 14 = 35. - Gary W. Adamson, May 15 2009
The integral of 1/(1+x^2)^(n+1) is given by a(n)/2^(2*n - 1) * (x/(1 + x^2)^n*P(x) + arctan(x)), where P(x) is a monic polynomial of degree 2*n - 2 with rational coefficients. - Christiaan van de Woestijne, Jan 25 2011
a(n) is the number of Schroder paths of semilength n in which the (2,0)-steps at level 0 come in 2 colors and there are no (2,0)-steps at a higher level. Example: a(2) = 10 because, denoting U = (1,1), H = (1,0), and D = (1,-1), we have 2^2 = 4 paths of shape HH, 2 paths of shape HUD, 2 paths of shape UDH, and 1 path of each of the shapes UDUD and UUDD. - Emeric Deutsch, May 02 2011
a(n) is the number of Motzkin paths of length n in which the (1,0)-steps at level 0 come in 3 colors and those at a higher level come in 2 colors. Example: a(3)=35 because, denoting U = (1,1), H = (1,0), and D = (1,-1), we have 3^3 = 27 paths of shape HHH, 3 paths of shape HUD, 3 paths of shape UDH, and 2 paths of shape UHD. - Emeric Deutsch, May 02 2011
Also number of digitally balanced numbers having length 2*(n + 1) in binary representation: a(n) = #{m: A070939(A031443(m)) = 2*(n + 1)}. - Reinhard Zumkeller, Jun 08 2011
a(n) equals 2^(2*n + 3) times the coefficient of Pi in 2F1([1/2, n+2]; [3/2]; -1). - John M. Campbell, Jul 17 2011
For positive n, a(n) equals 4^(n+2) times the coefficient of Pi^2 in Integral_{x = 0..Pi/2} x sin^(2*n + 2)x. - John M. Campbell, Jul 19 2011 [Apparently, the contributor means Integral_{x = 0..Pi/2} x * (sin(x))^(2*n + 2).]
a(n-1) = C(2*n, n)/2 is the number of ways to assign 2*n people into 2 (unlabeled) groups of size n. - Dennis P. Walsh, Nov 09 2011
Equals row sums of triangle A205945. - Gary W. Adamson, Feb 01 2012
a(n-1) gives the number of n-regular sequences defined by Erdős and Gallai in 1960 in connection with the degree sequences of simple graphs. - Matuszka Tamás, Mar 06 2013
a(n) is the sum of falling diagonals of squares in the comment in A085812 (equivalent to the Cloitre formula of Aug 2002). - John Molokach, Sep 26 2013
For n > 0: largest terms of Zigzag matrices as defined in A088961. - Reinhard Zumkeller, Oct 25 2013
Also the number of different possible win/loss round sequences (from the perspective of the eventual winner) in a "best of 2*n + 1" two-player game. For example, a(2) = 10 means there are 10 different win/loss sequences in a "best of 5" game (like a tennis match in which the first player to win 3 sets, out of a maximum of 5, wins the match); the 10 sequences are WWW, WWLW, WWLLW, WLWW, WLWLW, WLLWW, LWWW, LWWLW, LWLWW, LLWWW. See also A072600. - Philippe Beaudoin, May 14 2014; corrected by Jon E. Schoenfield, Nov 23 2014
When adding 1 to the beginning of the sequence: Convolving a(n)/2^n with itself equals 2^(n+1). For example, when n = 4: convolving {1, 1/1, 3/2, 10/4, 35/8, 126/16} with itself is 32 = 2^5. - Bob Selcoe, Jul 16 2014
From Tom Copeland, Nov 09 2014: (Start)
The shifted array belongs to a family of arrays associated to the Catalan A000108 (t = 1), and Riordan, or Motzkin sums A005043 (t = 0), with the o.g.f. [1 - sqrt(1 - 4x/(1 + (1 - t)x))]/2 and inverse x*(1 - x)/[1 + (t - 1)*x*(1 - x)]. See A091867 for more info on this family. Here is t = -3 (mod signs in the results).
Let C(x) = [1 - sqrt(1-4x)]/2, an o.g.f. for the Catalan numbers A000108, with inverse Cinv(x) = x*(1-x) and P(x,t) = x/(1 + t*x) with inverse P(x, -t).
O.g.f: G(x) = [-1 + sqrt(1 + 4*x/(1 - 4*x))]/2 = -C[P(-x, 4)].
Inverse o.g.f: Ginv(x) = x*(1 + x)/(1 + 4*x*(1 + x)) = -P(Cinv(-x), -4) (shifted signed A001792). A088218(x) = 1 + G(x).
Equals A001813/2 omitting the leading 1 there. (End)
Placing n distinguishable balls into n indistinguishable boxes gives A000110(n) (the number of set partitions). - N. J. A. Sloane, Jun 19 2015
The sequence is the INVERTi transform of A049027: (1, 4, 17, 74, 326, ...). - Gary W. Adamson, Jun 23 2015
a(n) is the number of compositions of 2*n + 2 such that the sum of the elements at odd positions is equal to the sum of the elements at even positions. a(2) = 10 because there are 10 such compositions of 6: (3, 3), (1, 3, 2), (2, 3, 1), (1, 1, 2, 2), (1, 2, 2, 1), (2, 2, 1, 1), (2, 1, 1, 2), (1, 2, 1, 1, 1), (1, 1, 1, 2, 1), (1, 1, 1, 1, 1, 1). - Ran Pan, Oct 08 2015
a(n-1) is also the Schur function of the partition (n) of n evaluated at x_1 = x_2 = ... = x_n = 1, i.e., the number of semistandard Young tableaux of shape (n) (weakly increasing rows with n boxes with numbers from {1, 2, ..., n}). - Wolfdieter Lang, Oct 11 2015
Also the number of ordered (rooted planar) forests with a total of n+1 edges and no trivial trees. - Nachum Dershowitz, Mar 30 2016
a(n) is the number of sets (i1,...in) of length n so that n >= i1 >= i2 >= ...>= in >= 1. For instance, n=3 as there are only 10 such sets (3,3,3) (3,3,2) (3,3,1) (3,2,2) (3,2,1) (3,1,1) (2,2,2) (2,2,1) (2,1,1) (1,1,1,) 3,2,1 is each used 10 times respectively. - Anton Zakharov, Jul 04 2016
The repeated middle term in the odd rows of Pascal's triangle, or half the central binomial coefficient in the even rows of Pascal's triangle, n >= 2. - Enrique Navarrete, Feb 12 2018
a(n) is the number of walks of length 2n+1 from the origin with steps (1,1) and (1,-1) that stay on or above the x-axis. Equivalently, a(n) is the number of walks of length 2n+1 from the origin with steps (1,0) and (0,1) that stay in the first octant. - Alexander Burstein, Dec 24 2019
Total number of nodes summed over all Dyck paths of semilength n. - Alois P. Heinz, Mar 08 2020
a(n-1) is the determinant of the n X n matrix m(i, j) = binomial(n+i-1, j). - Fabio Visonà, May 21 2022
Let X_i be iid standard Gaussian random variable N(0,1), and S_n be the partial sum S_n = X_1+...+X_n. Then P(S_1>0,S_2>0,...,S_n>0) = a(n+1)/2^(2n-1) = a(n+1) / A004171(n+1). For example, P(S_1>0) = 1/2, P(S_1>0,S_2>0) = 3/8, P(S_1>0,S_2>0,S_3>0) = 5/16, etc. This probability is also equal to the volume of the region x_1 > 0, x_2 > -x_1, x_3 > -(x_1+x_2), ..., x_n > -(x_1+x_2+...+x_(n-1)) in the hypercube [-1/2, 1/2]^n. This also holds for the Cauchy distribution and other stable distributions with mean 0, skew 0 and scale 1. - Xiaohan Zhang, Nov 01 2022
a(n) is the number of parking functions of size n+1 avoiding the patterns 132, 213, and 321. - Lara Pudwell, Apr 10 2023
Number of vectors in (Z_>=0)^(n+1) such that the sum of the components is n+1. binomial(2*n-1, n) provides this property for n. - Michael Richard, Jun 12 2023
Also number of discrete negations on the finite chain L_n={0,1,...,n-1,n}, i.e., monotone decreasing unary operators such that N(0)=n and N(n)=0. - Marc Munar, Oct 10 2023
a(n) is the number of Dyck paths of semilength n+1 having one of its peaks marked. - Juan B. Gil, Jan 03 2024
a(n) is the dimension of the (n+1)-st symmetric power of an (n+1)-dimensional vector space. - Mehmet A. Ates, Feb 15 2024
a(n) is the independence number of the twisted odd graph O^(sigma)(n+2). - _Miquel A. Fiol, Aug 26 2024
a(n) is the number of non-descending sequences with length n and the last number is less or equal to n. a(n) is also the number of integer partitions (of any positive integer) with length n and largest part is less or equal to n. - Zlatko Damijanic, Dec 06 2024
a(n) is the number of triangulations of a once-punctured (n+1)-gon [from Fontaine & Plamondon's Theorem 3.6]. - Esther Banaian, May 06 2025

Examples

			There are a(2)=10 ways to put 3 indistinguishable balls into 3 distinguishable boxes, namely, (OOO)()(), ()(OOO)(), ()()(OOO), (OO)(O)(), (OO)()(O), (O)(OO)(), ()(OO)(O), (O)()(OO), ()(O)(OO), and (O)(O)(O). - _Dennis P. Walsh_, Apr 11 2012
a(2) = 10: Semistandard Young tableaux for partition (3) of 3 (the indeterminates x_i, i = 1, 2, 3 are omitted and only their indices are given): 111, 112, 113, 122, 123, 133, 222, 223, 233, 333. - _Wolfdieter Lang_, Oct 11 2015

References

  • H. Davenport, The Higher Arithmetic. Cambridge Univ. Press, 7th ed., 1999, ch. V.3 (p. 122).
  • A. Frosini, R. Pinzani, and S. Rinaldi, About half the middle binomial coefficient, Pure Math. Appl., 11 (2000), 497-508.
  • Charles Jordan, Calculus of Finite Differences, Chelsea 1965, p. 449.
  • J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
  • Paul J. Nahin, "An Imaginary Tale, The Story of [Sqrt(-1)]," Princeton University Press, Princeton, NJ 1998, p. 62.
  • L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
  • 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).

Links

Crossrefs

Cf. A000110, A007318, A030662, A046097, A060897-A060900, A049027, A076025, A076026, A060150, A001263, A005773, A001405, A132813, A134285.
Equals A000984(n+1)/2.
a(n) = (2*n+1)*Catalan(n) [A000108] = A035324(n+1, 1) (first column of triangle).
Row sums of triangles A028364, A050166, A039598.
Bisections: a(2*k) = A002458(k), a(2*k+1) = A001448(k+1)/2, k >= 0.
Other versions of the same sequence: A088218, A110556, A138364.
Diagonals 1 and 2 of triangle A100257.
Second row of array A102539.
Column of array A073165.
Row sums of A103371. - Susanne Wienand, Oct 22 2011
Cf. A002054: C(2*n+1, n-1). - Bruno Berselli, Jan 20 2014
Cf. A005043, A091867, A001792, A001813, A166454.

Programs

  • GAP
    List([0..30],n->Binomial(2*n+1,n+1)); # Muniru A Asiru, Feb 26 2019
  • Haskell
    a001700 n = a007318 (2*n+1) (n+1)  -- Reinhard Zumkeller, Oct 25 2013
  • Magma
    [Binomial(2*n, n)/2: n in [1..40]]; // Vincenzo Librandi, Nov 10 2014
  • Maple
    A001700 := n -> binomial(2*n+1,n+1); seq(A001700(n), n=0..20);
A001700List := proc(m) local A, P, n; A := [1]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), 2*P[-1]]);
A := [op(A), P[-1]] od; A end: A001700List(27); # Peter Luschny, Mar 24 2022
  • Mathematica
    Table[ Binomial[2n + 1, n + 1], {n, 0, 23}]
CoefficientList[ Series[2/((Sqrt[1 - 4 x] + 1)*Sqrt[1 - 4 x]), {x, 0, 22}], x] (* Robert G. Wilson v, Aug 08 2011 *)
  • Maxima
    B(n,a,x):=coeff(taylor(exp(x*t)*(t/(exp(t)-1))^a,t,0,20),t,n)*n!;
makelist((-1)^(n)*B(n,n+1,-n-1)/n!,n,0,10); /* Vladimir Kruchinin, Apr 06 2016 */
  • PARI
    a(n)=binomial(2*n+1,n+1)
  • PARI
    z='z+O('z^50); Vec((1/sqrt(1-4*z)-1)/(2*z)) \\ Altug Alkan, Oct 11 2015
  • Python
    from _future_ import division
A001700_list, b = [], 1
for n in range(10**3):
    A001700_list.append(b)
    b = b*(4*n+6)//(n+2) # Chai Wah Wu, Jan 26 2016
  • Sage
    [rising_factorial(n+1,n+1)/factorial(n+1) for n in (0..22)] # Peter Luschny, Nov 07 2011

Formula

a(n-1) = binomial(2*n, n)/2 = A000984(n)/2 = (2*n)!/(2*n!*n!).
D-finite with recurrence: a(0) = 1, a(n) = 2*(2*n+1)*a(n-1)/(n+1) for n > 0.
G.f.: (1/sqrt(1 - 4*x) - 1)/(2*x).
L.g.f.: log((1 - sqrt(1 - 4*x))/(2*x)) = Sum_{n >= 0} a(n)*x^(n+1)/(n+1). - Vladimir Kruchinin, Aug 10 2010
G.f.: 2F1([1, 3/2]; [2]; 4*x). - Paul Barry, Jan 23 2009
G.f.: 1/(1 - 2*x - x/(1 - x/(1 - x/(1 - x/(1 - ... (continued fraction). - Paul Barry, May 06 2009
G.f.: c(x)^2/(1 - x*c(x)^2), c(x) the g.f. of A000108. - Paul Barry, Sep 07 2009
O.g.f.: c(x)/sqrt(1 - 4*x) = (2 - c(x))/(1 - 4*x), with c(x) the o.g.f. of A000108. Added second formula. - Wolfdieter Lang, Sep 02 2012
Convolution of A000108 (Catalan) and A000984 (central binomial): Sum_{k=0..n} C(k)*binomial(2*(n-k), n-k), C(k) Catalan. - Wolfdieter Lang, Dec 11 1999
a(n) = Sum_{k=0..n} C(n+k, k). - Benoit Cloitre, Aug 20 2002
a(n) = Sum_{k=0..n} C(n, k)*C(n+1, k+1). - Benoit Cloitre, Oct 19 2002
a(n) = Sum_{k = 0..n+1} binomial(2*n+2, k)*cos((n - k + 1)*Pi). - Paul Barry, Nov 02 2004
a(n) = 4^n*binomial(n+1/2, n)/(n+1). - Paul Barry, May 10 2005
E.g.f.: Sum_{n >= 0} a(n)*x^(2*n + 1)/(2*n + 1)! = BesselI(1, 2*x). - Michael Somos, Jun 22 2005
E.g.f. in Maple notation: exp(2*x)*(BesselI(0, 2*x) + BesselI(1, 2*x)). Integral representation as n-th moment of a positive function on [0, 4]: a(n) = Integral_{x = 0..4} x^n * (x/(4 - x))^(1/2)/(2*Pi) dx, n >= 0. This representation is unique. - Karol A. Penson, Oct 11 2001
Narayana transform of [1, 2, 3, ...]. Let M = the Narayana triangle of A001263 as an infinite lower triangular matrix and V = the Vector [1, 2, 3, ...]. Then A001700 = M * V. - Gary W. Adamson, Apr 25 2006
a(n) = A122366(n,n). - Reinhard Zumkeller, Aug 30 2006
a(n) = C(2*n, n) + C(2*n, n-1) = A000984(n) + A001791(n). - Zerinvary Lajos, Jan 23 2007
a(n-1) = (n+1)*(n+2)*...*(2*n-1)/(n-1)! (product of n-1 consecutive integers, divided by (n-1)!). - Jonathan Vos Post, Apr 09 2007; [Corrected and shortened by Giovanni Ciriani, Mar 26 2019]
a(n-1) = (2*n - 1)!/(n!*(n - 1)!). - William A. Tedeschi, Feb 27 2008
a(n) = (2*n + 1)*A000108(n). - Paul Barry, Aug 21 2007
Binomial transform of A005773 starting (1, 2, 5, 13, 35, 96, ...) and double binomial transform of A001405. - Gary W. Adamson, Sep 01 2007
Row sums of triangle A132813. - Gary W. Adamson, Sep 01 2007
Row sums of triangle A134285. - Gary W. Adamson, Nov 19 2007
a(n) = 2*A000984(n) - A000108(n), that is, a(n) = 2*C(2*n, n) - n-th Catalan number. - Joseph Abate, Jun 11 2010
Conjectured: 4^n GaussHypergeometric(1/2,-n; 2; 1) -- Solution for the path which stays in the first and second quadrant. - Benjamin Phillabaum, Feb 20 2011
a(n)= Sum_{k=0..n} A038231(n,k) * (-1)^k * A000108(k). - Philippe Deléham, Nov 27 2009
Let A be the Toeplitz matrix of order n defined by: A[i,i-1] = -1, A[i,j] = Catalan(j-i), (i <= j), and A[i,j] = 0, otherwise. Then, for n >= 1, a(n) = (-1)^n * charpoly(A,-2). - Milan Janjic, Jul 08 2010
a(n) is the upper left term of M^(n+1), where M is the infinite matrix in which a column of (1,2,3,...) is prepended to an infinite lower triangular matrix of all 1's and the rest zeros, as follows:
1, 1, 0, 0, 0, ...
2, 1, 1, 0, 0, ...
3, 1, 1, 1, 0, ...
4, 1, 1, 1, 1, ...
...
Alternatively, a(n) is the upper left term of M^n where M is the infinite matrix:
3, 1, 0, 0, 0, ...
1, 1, 1, 0, 0, ...
1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 14 2011
a(n) = (n + 1)*hypergeom([-n, -n], [2], 1). - Peter Luschny, Oct 24 2011
a(n) = Pochhammer(n+1, n+1)/(n+1)!. - Peter Luschny, Nov 07 2011
E.g.f.: 1 + 6*x/(U(0) - 6*x); U(k) = k^2 + (4*x + 3)*k + 6*x + 2 - 2*x*(k + 1)*(k + 2)*(2*k + 5)/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2011
a(n) = 2*A000984(n) - A000108(n). [Abate & Whitt]
a(n) = 2^(2*n+1)*binomial(n+1/2, -1/2). - Peter Luschny, May 06 2014
For n > 1: a(n-1) = A166454(2*n, n), central terms in A166454. - Reinhard Zumkeller, Mar 04 2015
a(n) = 2*4^n*Gamma(3/2 + n)/(sqrt(Pi)*Gamma(2+n)). - Peter Luschny, Dec 14 2015
a(n) ~ 2*4^n*(1 - (5/8)/n + (73/128)/n^2 - (575/1024)/n^3 + (18459/32768)/n^4)/sqrt(n*Pi). - Peter Luschny, Dec 16 2015
a(n) = (-1)^(n)*B(n, n+1, -n-1)/n!, where B(n,a,x) is a generalized Bernoulli polynomial. - Vladimir Kruchinin, Apr 06 2016
a(n) = Gamma(2 + 2*n)/(n!*Gamma(2 + n)). Andres Cicuttin, Apr 06 2016
a(n) = (n + (n + 1))!/(Gamma(n)*Gamma(1 + n)*A002378(n)), for n > 0. Andres Cicuttin, Apr 07 2016
From Ilya Gutkovskiy, Jul 04 2016: (Start)
Sum_{n >= 0} 1/a(n) = 2*(9 + 2*sqrt(3)*Pi)/27 = A248179.
Sum_{n >= 0} (-1)^n/a(n) = 2*(5 + 4*sqrt(5)*arcsinh(1/2))/25 = 2*(5*A145433 - 1).
Sum_{n >= 0} (-1)^n*a(n)/n! = BesselI(2,2)*exp(-2) = A229020*A092553. (End)
Conjecture: a(n) = Sum_{k=2^n..2^(n+1)-1} A178244(k). - Mikhail Kurkov, Feb 20 2021
a(n-1) = 1 + (1/n)*Sum_{t=1..n/2} (2*cos((2*t-1)*Pi/(2*n)))^(2*n). - Greg Dresden, Oct 11 2022
a(n) = Product_{1 <= i <= j <= n} (i + j + 1)/(i + j - 1). Cf. A006013. - Peter Bala, Feb 21 2023
Sum_{n >= 0} a(n)*x^(n+1)/(n+1) = x + 3*x^2/2 + 10*x^3/3 + 35*x^4/4 + ... = the series reversion of exp(-x)*(1 - exp(-x)). - Peter Bala, Sep 06 2023

Extensions

Name corrected by Paul S. Coombes, Jan 11 2012
Name corrected by Robert Tanniru, Feb 01 2014

A097805 Number of compositions of n with k parts, T(n, k) = binomial(n-1, k-1) for n, k >= 1 and T(n, 0) = 0^n, triangle read by rows for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 1, 0, 1, 5, 10, 10, 5, 1, 0, 1, 6, 15, 20, 15, 6, 1, 0, 1, 7, 21, 35, 35, 21, 7, 1, 0, 1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1
Offset: 0

Views

Author

Paul Barry, Aug 25 2004

Keywords

Comments

Previous name was: Riordan array (1, 1/(1-x)) read by rows.
Note this Riordan array would be denoted (1, x/(1-x)) by some authors.
Columns have g.f. (x/(1-x))^k. Reverse of A071919. Row sums are A011782. Antidiagonal sums are Fibonacci(n-1). Inverse as Riordan array is (1, 1/(1+x)). A097805=B*A059260*B^(-1), where B is the binomial matrix.
(0,1)-Pascal triangle. - Philippe Deléham, Nov 21 2006
(n+1) * each term of row n generates triangle A127952: (1; 0, 2; 0, 3, 3; 0, 4, 8, 4; ...). - Gary W. Adamson, Feb 09 2007
Triangle T(n,k), 0<=k<=n, read by rows, given by [0,1,0,0,0,0,0,...] DELTA [1,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2008
From Paul Weisenhorn, Feb 09 2011: (Start)
Triangle read by rows: T(r,c) is the number of unordered partitions of n=r*(r+1)/2+c into (r+1) parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2.
Triangle read by rows: T(r,c) is the number of unordered partitions of the number n=r*(r+1)/2+(c-1) into r parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2. (End)
Triangle read by rows: T(r,c) is the number of ordered partitions (compositions) of r into c parts. - Juergen Will, Jan 04 2016
From Tom Copeland, Oct 25 2012: (Start)
Given a basis composed of a sequence of polynomials p_n(x) characterized by ladder (creation / annihilation, or raising / lowering) operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x) with p_0(x)=1, giving the number operator # p_n(x) = RL p_n(x) = n p_n(x), the lower triangular padded Pascal matrix Pd (A097805) serves as a matrix representation of the operator exp(R^2*L) = exp(R#) =
1) exp(x^2D) for the set x^n and
2) D^(-1) exp(t*x)D for the set x^n/n! (see A218234).
(End)
From James East, Apr 11 2014: (Start)
Square array a(m,n) with m,n=0,1,2,... read by off-diagonals.
a(m,n) gives the number of order-preserving functions f:{1,...,m}->{1,...,n}. Order-preserving means that x
a(n,n)=A088218(n) is the size of the semigroup O_n of all order-preserving transformations of {1,...,n}.
Read as a triangle, this sequence may be obtained by augmenting Pascal's triangle by appending the column 1,0,0,0,... on the left.
(End)
A formula based on the partitions of n with largest part k is given as a Sage program below. The 'conjugate' formula leads to A048004. - Peter Luschny, Jul 13 2015
From Wolfdieter Lang, Feb 17 2017: (Start)
The transposed of this lower triangular Riordan matrix of the associated type T provides the transition matrix between the monomial basis {x^n}, n >= 0, and the basis {y^n}, n >= 0, with y = x/(1-x): x^0 = 1 = y^0, x^n = Sum_{m >= n} Ttrans(n,m) y^m, for n >= 1, with Ttrans(n,m) = binomial(m-1,n-1).
Therefore, if a transformation with this Riordan matrix from a sequence {a} to the sequence {b} is given by b(n) = Sum_{m=0..n} T(n, m)*a(m), with T(n, m) = binomial(n-1, m-1), for n >= 1, then Sum_{n >= 0} a(n)*x^n = Sum_{n >= 0} b(n)*y^n, with y = x/(1-x) and vice versa. This is a modified binomial transformation; the usual one belongs to the Pascal Riordan matrix A007318. (End)
From Gus Wiseman, Jan 23 2022: (Start)
Also the number of compositions of n with alternating sum k, with k ranging from -n to n in steps of 2. For example, row n = 6 counts the following compositions (empty column indicated by dot):
. (15) (24) (33) (42) (51) (6)
(141) (132) (123) (114)
(1113) (231) (222) (213)
(1212) (1122) (321) (312)
(1311) (1221) (1131) (411)
(2112) (2121)
(2211) (3111)
(11121) (11112)
(12111) (11211)
(111111) (21111)
The reverse-alternating version is the same. Counting compositions by all three parameters (sum, length, alternating sum) gives A345197. Compositions of 2n with alternating sum 2k with k ranging from -n + 1 to n are A034871. (End)
Also the convolution triangle of A000012. - Peter Luschny, Oct 07 2022
From Sergey Kitaev, Nov 18 2023: (Start)
Number of permutations of length n avoiding simultaneously the patterns 123 and 132 with k right-to-left maxima. A right-to-left maximum in a permutation a(1)a(2)...a(n) is position i such that a(j) < a(i) for all i < j.
Number of permutations of length n avoiding simultaneously the patterns 231 and 312 with k right-to-left minima (resp., left-to-right maxima). A right-to-left minimum (resp., left-to-right maximum) in a permutation a(1)a(2)...a(n) is position i such that a(j) > a(i) for all j > i (resp., a(j) < a(i) for all j < i).
Number of permutations of length n avoiding simultaneously the patterns 213 and 312 with k right-to-left maxima (resp., left-to-right maxima).
Number of permutations of length n avoiding simultaneously the patterns 213 and 231 with k right-to-left maxima (resp., right-to-left minima). (End)

Examples

			G.f. = 1 + x * (x + x^3 * (1 + x) + x^6 * (1 + x)^2 + x^10 * (1 + x)^3 + ...). - _Michael Somos_, Aug 20 2006
The triangle T(n, k) begins:
n\k  0 1 2  3  4   5   6  7  8 9 10 ...
0:   1
1:   0 1
2:   0 1 1
3:   0 1 2  1
4:   0 1 3  3  1
5:   0 1 4  6  4   1
6:   0 1 5 10 10   5   1
7:   0 1 6 15 20  15   6  1
8:   0 1 7 21 35  35  21  7  1
9:   0 1 8 28 56  70  56 28  8 1
10:  0 1 9 36 84 126 126 84 36 9  1
... reformatted _Wolfdieter Lang_, Jul 31 2017
From _Paul Weisenhorn_, Feb 09 2011: (Start)
T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+c = 18 with (r+1)=6 summands: (5+5+4+2+1+1), (5+5+3+3+1+1), (5+4+4+3+1+1), (5+5+3+2+2+1), (5+4+4+2+2+1), (5+4+3+3+2+1).
T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+(c-1) = 17 with r=5 summands: (5+5+4+2+1), (5+5+3+3+1), (5+5+3+2+2), (5+4+4+3+1), (5+4+4+2+2), (5+4+3+3+2).  (End)
From _James East_, Apr 11 2014: (Start)
a(0,0)=1 since there is a unique (order-preserving) function {}->{}.
a(m,0)=0 for m>0 since there is no function from a nonempty set to the empty set.
a(3,2)=4 because there are four order-preserving functions {1,2,3}->{1,2}: these are [1,1,1], [2,2,2], [1,1,2], [1,2,2]. Here f=[a,b,c] denotes the function defined by f(1)=a, f(2)=b, f(3)=c.
a(2,3)=6 because there are six order-preserving functions {1,2}->{1,2,3}: these are [1,1], [1,2], [1,3], [2,2], [2,3], [3,3].
(End)

References

  • D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Section 7.2.1.3, 2011.

Links

Crossrefs

Case m=0 of the polynomials defined in A278073.
Cf. A000012 (diagonal), A011782 (row sums), A088218 (central terms).
Cf. A007318, A048004, A127952, A118800, A200139, A130595, A167374.
The terms just left of center in odd-indexed rows are A001791, even A002054.
The odd-indexed rows are A034871.
Row sums without the center are A058622.
The unordered version is A072233, without zeros A008284.
Right half without center has row sums A027306(n-1).
Right half with center has row sums A116406(n).
Left half without center has row sums A294175(n-1).
Left half with center has row sums A058622(n-1).
A025047 counts alternating compositions.
A098124 counts balanced compositions, unordered A047993.
A106356 counts compositions by number of maximal anti-runs.
A344651 counts partitions by sum and alternating sum.
A345197 counts compositions by sum, length, and alternating sum.
Cf. A000346, A000984, A001700, A008549, A008965, A114121, A124754, A238279, A345907, A345908, A346632.

Programs

  • Maple
    b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
      expand(add(b(n-i*j, i-1, p+j)/j!*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, May 25 2014
# Alternatively:
T := proc(k,n) option remember;
if k=n then 1 elif k=0 then 0 else
add(T(k-1,n-i), i=1..n-k+1) fi end:
A097805 := (n,k) -> T(k,n):
for n from 0 to 12 do seq(A097805(n,k), k=0..n) od; # Peter Luschny, Mar 12 2016
# Uses function PMatrix from A357368.
PMatrix(10, n -> 1);  # Peter Luschny, Oct 07 2022
  • Mathematica
    T[0, 0] = 1; T[n_, k_] := Binomial[n-1, k-1]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 03 2014, after Paul Weisenhorn *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]==k&]],{n,0,10},{k,0,n}] (* Gus Wiseman, Jan 23 2022 *)
  • PARI
    {a(n) = my(m); if( n<2, n==0, n--; m = (sqrtint(8*n + 1) - 1)\2; binomial(m-1, n - m*(m + 1)/2))}; /* Michael Somos, Aug 20 2006 */
  • PARI
    T(n,k) = if (k==0, 0^n, binomial(n-1, k-1)); \\ Michel Marcus, May 06 2022
  • PARI
    row(n) = vector(n+1, k, k--; if (k==0, 0^n, binomial(n-1, k-1))); \\ Michel Marcus, May 06 2022
  • Python
    from math import comb
def T(n, k): return comb(n-1, k-1) if k != 0 else k**n  # Peter Luschny, May 06 2022
  • Sage
    # Illustrates a basic partition formula, is not efficient as a program for large n.
def A097805_row(n):
    r = []
    for k in (0..n):
        s = 0
        for q in Partitions(n, max_part=k, inner=[k]):
            s += mul(binomial(q[j],q[j+1]) for j in range(len(q)-1))
        r.append(s)
    return r
[A097805_row(n) for n in (0..9)] # Peter Luschny, Jul 13 2015

Formula

Number triangle T(n, k) defined by T(n,k) = Sum_{j=0..n} binomial(n, j)*if(k<=j, (-1)^(j-k), 0).
T(r,c) = binomial(r-1,c-1), 0 <= c <= r. - Paul Weisenhorn, Feb 09 2011
G.f.: (-1+x)/(-1+x+x*y). - R. J. Mathar, Aug 11 2015
a(0,0) = 1, a(n,k) = binomial(n-1,n-k) = binomial(n-1,k-1) Juergen Will, Jan 04 2016
G.f.: (x^1 + x^2 + x^3 + ...)^k = (x/(1-x))^k. - Juergen Will, Jan 04 2016
From Tom Copeland, Nov 15 2016: (Start)
E.g.f.: 1 + x*[e^((x+1)t)-1]/(x+1).
This padded Pascal matrix with the odd columns negated is NpdP = M*S = S^(-1)*M^(-1) = S^(-1)*M, where M(n,k) = (-1)^n A130595(n,k), the inverse Pascal matrix with the odd rows negated, S is the summation matrix A000012, the lower triangular matrix with all elements unity, and S^(-1) = A167374, a finite difference matrix. NpdP is self-inverse, i.e., (M*S)^2 = the identity matrix, and has the e.g.f. 1 - x*[e^((1-x)t)-1]/(1-x).
M = NpdP*S^(-1) follows from the well-known recursion property of the Pascal matrix, implying NpdP = M*S.
The self-inverse property of -NpdP is implied by the self-inverse relation of its embedded signed Pascal submatrix M (cf. A130595). Also see A118800 for another proof.
Let P^(-1) be A130595, the inverse Pascal matrix. Then T = A200139*P^(-1) and T^(-1) = padded P^(-1) = P*A097808*P^(-1). (End)
The center (n>0) is T(2n+1,n+1) = A000984(n) = 2*A001700(n-1) = 2*A088218(n) = A126869(2n) = 2*A138364(2n-1). - Gus Wiseman, Jan 25 2022

Extensions

Corrected by Philippe Deléham, Oct 05 2005
New name using classical terminology by Peter Luschny, Feb 05 2019

A002054 Binomial coefficient C(2n+1, n-1).

Original entry on oeis.org

1, 5, 21, 84, 330, 1287, 5005, 19448, 75582, 293930, 1144066, 4457400, 17383860, 67863915, 265182525, 1037158320, 4059928950, 15905368710, 62359143990, 244662670200, 960566918220, 3773655750150, 14833897694226, 58343356817424, 229591913401900
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) = number of permutations in S_{n+2} containing exactly one 312 pattern. E.g., S_3 has a_1 = 1 permutations containing exactly one 312 pattern, and S_4 has a_2 = 5 permutations containing exactly one 312 pattern, namely 1423, 2413, 3124, 3142, and 4231. This comment is also true if 312 is replaced by any of 132, 213, or 231 (but not 123 or 321, for which see A003517). [Comment revised by N. J. A. Sloane, Nov 26 2022]
Number of valleys in all Dyck paths of semilength n+1. Example: a(2)=5 because UD*UD*UD, UD*UUDD, UUDD*UD, UUD*UDD, UUUDDD, where U=(1,1), D=(1,-1) and the valleys are shown by *. - Emeric Deutsch, Dec 05 2003
Number of UU's (double rises) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDU*UDD, U*UDDUD, U*UDUDD, U*U*UDDD, the double rises being shown by *. - Emeric Deutsch, Dec 05 2003
Number of peaks at level higher than one (high peaks) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUU*DDD, the high peaks being shown by *. - Emeric Deutsch, Dec 05 2003
Number of diagonal dissections of a convex (n+3)-gon into n regions. Number of standard tableaux of shape (n,n,1) (see Stanley reference). - Emeric Deutsch, May 20 2004
Number of dissections of a convex (n+3)-gon by noncrossing diagonals into several regions, exactly n-1 of which are triangular. Example: a(2)=5 because the convex pentagon ABCDE is dissected by any of the diagonals AC, BD, CE, DA, EB into regions containing exactly 1 triangle. - Emeric Deutsch, May 31 2004
Number of jumps in all full binary trees with n+1 internal nodes. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007
a(n) is the total number of nonempty Dyck subpaths in all Dyck paths (A000108) of semilength n. For example, the Dyck path UUDUUDDD has Dyck subpaths stretching over positions 1-8 (the entire path), 2-3, 2-7, 4-7, 5-6 and so contributes 5 to a(4). - David Callan, Jul 25 2008
a(n+1) is the total number of ascents in the set of all n-permutations avoiding the pattern 132. For example, a(2) = 5 because there are 5 ascents in the set 123, 213, 231, 312, 321. - Cheyne Homberger, Oct 25 2013
Number of increasing tableaux of shape (n+1,n+1) with largest entry 2n+1. An increasing tableau is a semistandard tableau with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 5 counts the five tableaux (124)(235), (123)(245), (124)(345), (134)(245), (123)(245). - Oliver Pechenik, May 02 2014
a(n) is the number of noncrossing partitions of 2n+1 into n-1 blocks of size 2 and 1 block of size 3. - Oliver Pechenik, May 02 2014
Number of paths in the half-plane x>=0, from (0,0) to (2n+1,3), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 5 paths: UUUUD, UUUDU, UUDUU, UDUUU, DUUUU. - José Luis Ramírez Ramírez, Apr 19 2015
From Gus Wiseman, Aug 20 2021: (Start)
Also the number of binary numbers with 2n+2 digits and with two more 0's than 1's. For example, the a(2) = 5 binary numbers are: 100001, 100010, 100100, 101000, 110000, with decimal values 33, 34, 36, 40, 48. Allowing first digit 0 gives A001791, ranked by A345910/A345912.
Also the number of integer compositions of 2n+2 with alternating sum -2, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(3) = 21 compositions are:
(35) (152) (1124) (11141) (111113)
(251) (1223) (12131) (111212)
(1322) (13121) (111311)
(1421) (14111) (121112)
(2114) (121211)
(2213) (131111)
(2312)
(2411)
The following pertain to these compositions:
- The unordered version is A344741.
- Ranked by A345924 (reverse: A345923).
- A345197 counts compositions by length and alternating sum.
- A345925 ranks compositions with alternating sum 2 (reverse: A345922).
(End)

Examples

			G.f. = x + 5*x^2 + 21*x^3 + 84*x^4 + 330*x^5 + 1287*x^6 + 5005*x^7 + ...

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.
  • George Grätzer, General Lattice Theory. Birkhauser, Basel, 1998, 2nd edition, p. 474, line -3.
  • A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
  • 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).

Links

Crossrefs

Diagonal 4 of triangle A100257. Also a diagonal of A033282.
Equals (1/2) A024483(n+2). Bisection of A037951 and A037955.
Cf. A001263.
Column k=1 of A263771.
Counts terms of A031445 with 2n+2 digits in binary.
Cf. A000097, A000346, A000984, A001622, A001700, A007318, A008549, A031444, A058622, A097805, A116406, A138364, A163493, A202736.
Cf. binomial(2*n+m, n): A000984 (m = 0), A001700 (m = 1), A001791 (m = 2), A002694 (m = 4), A003516 (m = 5), A002696 (m = 6), A030053 - A030056, A004310 - A004318.

Programs

  • GAP
    List([1..25],n->Binomial(2*n+1,n-1)); # Muniru A Asiru, Aug 09 2018
  • Magma
    [Binomial(2*n+1, n-1): n in [1..30]]; // Vincenzo Librandi, Apr 20 2015
  • Maple
    with(combstruct): seq((count(Composition(2*n+2), size=n)), n=1..24); # Zerinvary Lajos, May 03 2007
  • Mathematica
    CoefficientList[Series[8/(((Sqrt[1-4x] +1)^3)*Sqrt[1-4x]), {x,0,22}], x] (* Robert G. Wilson v, Aug 08 2011 *)
a[ n_]:= Binomial[2 n + 1, n - 1]; (* Michael Somos, Apr 25 2014 *)
  • PARI
    {a(n) = binomial( 2*n+1, n-1)};
  • Python
    from _future_ import division
A002054_list, b = [], 1
for n in range(1,10**3):
    A002054_list.append(b)
    b = b*(2*n+2)*(2*n+3)//(n*(n+3)) # Chai Wah Wu, Jan 26 2016
  • Sage
    [binomial(2*n+1, n-1) for n in (1..25)] # G. C. Greubel, Mar 22 2019

Formula

a(n) = Sum_{j=0..n-1} binomial(2*j, j) * binomial(2*n - 2*j, n-j-1)/(j+1). - Yong Kong (ykong(AT)curagen.com), Dec 26 2000
G.f.: z*C^4/(2-C), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function. - Emeric Deutsch, Jul 05 2003
From Wolfdieter Lang, Jan 09 2004: (Start)
a(n) = binomial(2*n+1, n-1) = n*C(n+1)/2, C(n)=A000108(n) (Catalan).
G.f.: (1 - 2*x - (1-3*x)*c(x))/(x*(1-4*x)) with g.f. c(x) of A000108. (End)
G.f.: z*C(z)^3/(1-2*z*C(z)), where C(z) is the g.f. of Catalan numbers. - José Luis Ramírez Ramírez, Apr 19 2015
G.f.: 2F1(5/2, 2; 4; 4*x). - R. J. Mathar, Aug 09 2015
D-finite with recurrence: a(n+1) = a(n)*(2*n+3)*(2*n+2)/(n*(n+3)). - Chai Wah Wu, Jan 26 2016
From Ilya Gutkovskiy, Aug 30 2016: (Start)
E.g.f.: (BesselI(0,2*x) + (1 - 1/x)*BesselI(1,2*x))*exp(2*x).
a(n) ~ 2^(2*n+1)/sqrt(Pi*n). (End)
a(n) = (1/(n+1))*Sum_{i=0..n-1} (n+1-i)*binomial(2n+2,i), n >= 1. - Taras Goy, Aug 09 2018
G.f.: (x - 1 + (1 - 3*x)/sqrt(1 - 4*x))/(2*x^2). - Michael Somos, Jul 28 2021
From Amiram Eldar, Jan 24 2022: (Start)
Sum_{n>=1} 1/a(n) = 5/3 - 2*Pi/(9*sqrt(3)).
Sum_{n>=1} (-1)^(n+1)/a(n) = 52*log(phi)/(5*sqrt(5)) - 7/5, where phi is the golden ratio (A001622). (End)
a(n) = A001405(2*n+1) - A000108(n+1), n >= 1 (from Eremin link, page 7). - Gennady Eremin, Sep 05 2023
G.f.: x/(1 - 4*x)^2 * c(-x/(1 - 4*x))^3, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, Feb 03 2024
From Peter Bala, Oct 13 2024: (Start)
a(n) = Integral_{x = 0..4} x^n * w(x) dx, where the weight function w(x) = 1/(2*Pi) * sqrt(x)*(x - 3)/sqrt(4 - x) (see Penson).
G.f. x*/sqrt(1 - 4*x) * c(x)^3. (End)

A058622 a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).

Original entry on oeis.org

0, 1, 1, 4, 5, 16, 22, 64, 93, 256, 386, 1024, 1586, 4096, 6476, 16384, 26333, 65536, 106762, 262144, 431910, 1048576, 1744436, 4194304, 7036530, 16777216, 28354132, 67108864, 114159428, 268435456, 459312152, 1073741824, 1846943453
Offset: 0

Views

Author

Yong Kong (ykong(AT)curagen.com), Dec 29 2000

Keywords

Comments

a(n) is the number of n-digit binary sequences that have more 1's than 0's. - Geoffrey Critzer, Jul 16 2009
Maps to the number of walks that end above 0 on the number line with steps being 1 or -1. - Benjamin Phillabaum, Mar 06 2011
Chris Godsil observes that a(n) is the independence number of the (n+1)-folded cube graph; proof is by a Cvetkovic's eigenvalue bound to establish an upper bound and a direct construction of the independent set by looking at vertices at an odd (resp., even) distance from a fixed vertex when n is odd (resp., even). - Stan Wagon, Jan 29 2013
Also the number of subsets of {1,2,...,n} that contain more odd than even numbers. For example, for n=4, a(4)=5 and the 5 subsets are {1}, {3}, {1,3}, {1,2,3}, {1,3,4}. See A014495 when same number of even and odd numbers. - Enrique Navarrete, Feb 10 2018
Also half the number of length-n binary sequences with a different number of zeros than ones. This is also the number of integer compositions of n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. Also the number of integer compositions of n+1 with alternating sum <= 0, ranked by A345915 (reverse: A345916). - Gus Wiseman, Jul 19 2021

Examples

			G.f. = x + x^2 + 4*x^3 + 5*x^4 + 16*x^5 + 22*x^6 + 64*x^7 + 93*x^8 + ...
From _Gus Wiseman_, Jul 19 2021: (Start)
The a(1) = 1 through a(5) = 16 compositions with nonzero alternating sum:
  (1)  (2)  (3)      (4)      (5)
            (1,2)    (1,3)    (1,4)
            (2,1)    (3,1)    (2,3)
            (1,1,1)  (1,1,2)  (3,2)
                     (2,1,1)  (4,1)
                              (1,1,3)
                              (1,2,2)
                              (1,3,1)
                              (2,1,2)
                              (2,2,1)
                              (3,1,1)
                              (1,1,1,2)
                              (1,1,2,1)
                              (1,2,1,1)
                              (2,1,1,1)
                              (1,1,1,1,1)
(End)

References

  • A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.1.7)

Links

Crossrefs

The odd bisection is A000302.
The even bisection is A000346.
The following relate to compositions with nonzero alternating sum:
- The complement is counted by A001700 or A138364.
- The version for alternating sum > 0 is A027306.
- The unordered version is A086543 (even bisection: A182616).
- The version for alternating sum < 0 is A294175.
- These compositions are ranked by A345921.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0: counted by A088218, ranked by A344619/A344619.
- k = 1: counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2: counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k > 0: counted by A027306, ranked by A345917/A345918.
- k < 0: counted by A294175, ranked by A345919/A345920.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd: counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000097, A007318, A008549, A034871, A114121, A120452, A163493, A210736, A239830, A344611.

Programs

  • Magma
    [(2^n -(1+(-1)^n)*Binomial(n, Floor(n/2))/2)/2: n in [0..40]]; // G. C. Greubel, Aug 08 2022
  • Mathematica
    Table[Sum[Binomial[n, Floor[n/2 + i]], {i, 1, n}], {n, 0, 32}] (* Geoffrey Critzer, Jul 16 2009 *)
a[n_] := If[n < 0, 0, (2^n - Boole[EvenQ @ n] Binomial[n, Quotient[n, 2]])/2]; (* Michael Somos, Nov 22 2014 *)
a[n_] := If[n < 0, 0, n! SeriesCoefficient[(Exp[2 x] - BesselI[0, 2 x])/2, {x, 0, n}]]; (* Michael Somos, Nov 22 2014 *)
Table[2^(n - 1) - (1 + (-1)^n) Binomial[n, n/2]/4, {n, 0, 40}] (* Eric W. Weisstein, Mar 21 2018 *)
CoefficientList[Series[2 x/((1-2x)(1 + 2x + Sqrt[(1+2x)(1-2x)])), {x, 0, 40}], x] (* Eric W. Weisstein, Mar 21 2018 *)
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],ats[#]!=0&]],{n,0,15}] (* Gus Wiseman, Jul 19 2021 *)
  • PARI
    a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n\2); \\ Michel Marcus, Dec 30 2015
  • PARI
    my(x='x+O('x^100)); concat(0, Vec(2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))))) \\ Altug Alkan, Dec 30 2015
  • Python
    from math import comb
def A058622(n): return (1<>1)>>1) if n else 0 # Chai Wah Wu, Aug 25 2025
  • SageMath
    [(2^n - binomial(n, n//2)*((n+1)%2))/2 for n in (0..40)] # G. C. Greubel, Aug 08 2022

Formula

a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).
a(n) = Sum_{i=0..floor((n-1)/2)} binomial(n, i).
G.f.: 2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))). - Vladeta Jovovic, Apr 27 2003
E.g.f: (e^(2x)-I_0(2x))/2 where I_n is the Modified Bessel Function. - Benjamin Phillabaum, Mar 06 2011
Logarithmic derivative of the g.f. of A210736 is a(n+1). - Michael Somos, Nov 22 2014
Even index: a(2n) = 2^(n-1) - A088218(n). Odd index: a(2n+1) = 2^(2n). - Gus Wiseman, Jul 19 2021
D-finite with recurrence n*a(n) +2*(-n+1)*a(n-1) +4*(-n+1)*a(n-2) +8*(n-2)*a(n-3)=0. - R. J. Mathar, Sep 23 2021
a(n) = 2^n-A027306(n). - R. J. Mathar, Sep 23 2021
A027306(n) - a(n) = A126869(n). - R. J. Mathar, Sep 23 2021

A063886 Number of n-step walks on a line starting from the origin but not returning to it.

Original entry on oeis.org

1, 2, 2, 4, 6, 12, 20, 40, 70, 140, 252, 504, 924, 1848, 3432, 6864, 12870, 25740, 48620, 97240, 184756, 369512, 705432, 1410864, 2704156, 5408312, 10400600, 20801200, 40116600, 80233200, 155117520, 310235040, 601080390, 1202160780, 2333606220, 4667212440
Offset: 0

Views

Author

Henry Bottomley, Aug 28 2001

Keywords

Comments

A Chebyshev transform of A007877(n+1). The g.f. is transformed to (1+x)/((1-x)(1+x^2)) under the mapping G(x)->(1/(1+x^2))G(1/(1+x^2)). - Paul Barry, Oct 12 2004
a(n-1) = 2*C(n-2, floor((n-2)/2)) is also the number of bit strings of length n in which the number of 00 substrings is equal to the number of 11 substrings. For example, when n = 4 we have 4 such bit strings: 0011, 0101, 1010, and 1100. - Angel Plaza, Apr 23 2009
Hankel transform is A120617. - Paul Barry, Aug 10 2009
The Hankel transform of a(n) is (-2)^C(n+1,2). The Hankel transform of (-1)^C(n+1,2)*a(n) is (-1)^C(n+1,2)*A164584(n). - Paul Barry, Aug 17 2009
For n > 1, a(n) is also the number of n-step walks starting from the origin and returning to it exactly once. - Geoffrey Critzer, Jan 24 2010
-a(n) is the Z-sequence for the Riordan array A130777. (See the W. Lang link under A006232 for A- and Z-sequences for Riordan matrices). - Wolfdieter Lang, Jul 12 2011
Number of subsets of {1,...,n} in which the even elements appear as often at even positions as at odd positions. - Gus Wiseman, Mar 17 2018

Examples

			a(4) = 6 because there are six length four walks that do not return to the origin: {-1, -2, -3, -4}, {-1, -2, -3, -2}, {-1, -2, -1, -2}, {1, 2, 1, 2}, {1, 2, 3, 2}, {1, 2, 3, 4}. There are also six such walks that return exactly one time: {-1, -2, -1, 0}, {-1, 0, -1, -2}, {-1, 0, 1, 2}, {1, 0, -1, -2}, {1, 0, 1, 2}, {1, 2, 1, 0}. - _Geoffrey Critzer_, Jan 24 2010
The a(5) = 12 subsets in which the even elements appear as often at even positions as at odd positions: {}, {1}, {3}, {5}, {1,3}, {1,5}, {2,4}, {3,5}, {1,2,4}, {1,3,5}, {2,4,5}, {1,2,4,5}. - _Gus Wiseman_, Mar 17 2018

Links

Crossrefs

Apart from initial terms, same as A182027.
Cf. A000108, A000246, A000712, A000984, A001405, A001700, A002420, A006232, A007877, A026010, A028329, A045931, A047073, A089849, A097613, A106180, A120617, A130777, A130780, A138364, A164584, A171966, A239241, A300787, A300788, A300789.
Cf. A307768 (complementary event).

Programs

  • Magma
    [1] cat [2*Binomial(n-1, Floor((n-1)/2)): n in [1..40]]; // G. C. Greubel, Jun 07 2023
  • Maple
    seq(seq(binomial(2*j,j)*i, i=1..2),j=0..16); # Zerinvary Lajos, Apr 28 2007
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n+1,
       4*a(n-2) +2*(a(n-1) -4*a(n-2))/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 10 2014
# third program:
A063886 := series(BesselI(0, 2*x)*(1 + x*2 + x*Pi*StruveL(1, 2*x)) - Pi*x*BesselI(1, 2*x)*StruveL(0, 2*x), x = 0, 34): seq(n!*coeff(A063886, x, n), n = 0 .. 33); # Mélika Tebni, Jun 17 2024
  • Mathematica
    Table[Length[Select[Map[Accumulate, Strings[{-1, 1}, n]], Count[ #, 0] == 0 &]], {n, 0, 20}] (* Geoffrey Critzer, Jan 24 2010 *)
CoefficientList[Series[Sqrt[(1+2x)/(1-2x)],{x,0,40}],x] (* Harvey P. Dale, Apr 28 2016 *)
  • PARI
    a(n)=(n==0)+2*binomial(n-1,(n-1)\2)
  • PARI
    a(n) = 2^n*prod(k=0,n-1,(k/n+1/n)^((-1)^k)); \\ Michel Marcus, Dec 03 2013
  • Python
    from math import ceil
from sympy import binomial
def a(n):
    if n==0: return 1
    return 2*binomial(n-1,(n-1)//2)
print([a(n) for n in range(18)])
# David Nacin, Feb 29 2012
  • SageMath
    [2*binomial(n-1, (n-1)//2) + int(n==0) for n in range(41)] # G. C. Greubel, Jun 07 2023

Formula

G.f.: sqrt((1+2*x)/(1-2*x)).
a(n+1) = 2*C(n, floor(n/2)) = 2*A001405(n); a(2n) = C(2n, n) = A000984(n) = 4*a(2n-2)-|A002420(n)| = 4*a(2n-2)-2*A000108(n-1) = 2*A001700(n-1); a(2n+1) = 2*a(2n) = A028329(n).
2*a(n) = A047073(n+1).
a(n) = Sum_{k=0..n} abs(A106180(n,k)). - Philippe Deléham, Oct 06 2006
a(n) = Sum_{k=0..n} (k+1)binomial(n, (n-k)/2) ( 1-cos((k+1)*Pi/2) (1+(-1)^(n-k))/(n+k+2) ). - Paul Barry, Oct 12 2004
G.f.: 1/(1-2*x/(1+x/(1+x/(1-x/(1-x/(1+x/(1+x/(1-x/(1-x/(1+ ... (continued fraction). - Paul Barry, Aug 10 2009
G.f.: 1 + 2*x/(G(0)-x+x^2) where G(k)= 1 - 2*x^2 - x^4/G(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Aug 10 2012
D-finite with recurrence: n*a(n) = 2*a(n-1) + 4*(n-2)*a(n-2). - R. J. Mathar, Dec 03 2012
From Sergei N. Gladkovskii, Jul 26 2013: (Start)
G.f.: 1/G(0), where G(k) = 1 - 2*x/(1 + 2*x/(1 + 1/G(k+1) )); (continued fraction).
G.f.: G(0), where G(k) = 1 + 2*x/(1 - 2*x/(1 + 1/G(k+1) )); (continued fraction).
G.f.: W(0)/2*(1+2*x), where W(k) = 1 + 1/(1 - 2*x/(2*x + (k+1)/(x*(2*k+1))/W(k+1) )), abs(x) < 1/2; (continued fraction). (End)
a(n) = 2^n*Product_{k=0..n-1} (k/n + 1/n)^((-1)^k). - Peter Luschny, Dec 02 2013
G.f.: G(0), where G(k) = 1 + 2*x*(4*k+1)/((2*k+1)*(1+2*x) - (2*k+1)*(4*k+3)*x*(1+2*x)/((4*k+3)*x + (k+1)*(1+2*x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 19 2014
From Peter Bala, Mar 29 2024: (Start)
a(n) = 2^n * Sum_{k = 0..n} (-1)^(n+k)*binomial(1/2, k)*binomial(- 1/2, n-k) = 2^n * A000246(n)/n!.
a(n) = (1/2^n) * binomial(2*n, n) * hypergeom([-1/2, -n], [1/2 - n], -1). (End)
E.g.f.: BesselI(0, 2*x)*(1 + x*(2 + Pi)*StruveL(1, 2*x)) - Pi*x*BesselI(1, 2*x)*StruveL(0, 2*x). - Stefano Spezia, May 11 2024
a(n) = A089849(n) + A138364(n). - Mélika Tebni, Jun 17 2024
From Amiram Eldar, Aug 15 2025: (Start)
Sum_{n>=0} 1/a(n) = Pi/(3*sqrt(3)) + 2.
Sum_{n>=0} (-1)^n/a(n) = 2/3 + Pi/(9*sqrt(3)). (End)

A294175 a(n) = 2^(n-1) + ((1+(-1)^n)/4)*binomial(n, n/2) - binomial(n, floor(n/2)).

Original entry on oeis.org

0, 0, 1, 1, 5, 6, 22, 29, 93, 130, 386, 562, 1586, 2380, 6476, 9949, 26333, 41226, 106762, 169766, 431910, 695860, 1744436, 2842226, 7036530, 11576916, 28354132, 47050564, 114159428, 190876696, 459312152, 773201629, 1846943453, 3128164186, 7423131482
Offset: 0

Views

Author

Enrique Navarrete, Feb 10 2018

Keywords

Comments

Number of subsets of {1,2,...,n} that contain more even than odd numbers.
Note that A058622 counts the nonempty subsets of {1,2,...,n} that contain more odd than even numbers.
From Gus Wiseman, Jul 22 2021: (Start)
Also the number of integer compositions of n + 1 with alternating sum < 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(0) = 0 through a(6) = 6 compositions (empty columns indicated by dots) are:
. . (12) (13) (14) (15)
(23) (24)
(131) (141)
(1112) (1113)
(1211) (1212)
(1311)
Also the number of integer compositions of n + 1 with reverse-alternating sum < 0. For a bijection, keep the odd-length compositions and reverse the even-length ones.
Also the number of (n+1)-digit binary numbers with more 0's than 1's. For example, the a(0) = 0 through a(5) = 6 binary numbers are:
. . 100 1000 10000 100000
10001 100001
10010 100010
10100 100100
11000 101000
110000
(End)
2*a(n) is the number of all-positive pinnacle sets that are admissible in the group S_{n+1}^B of signed permutations, but not admissible in S_{n+1}. - Bridget Tenner, Jan 06 2023

Examples

			For example, for n=5, a(5)=6 and the 6 subsets are {2}, {4}, {2,4}, {1,2,4}, {2,3,4}, {2,4,5}.

Links

  • Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO] (2023).

Crossrefs

The even bisection is A000346.
The odd bisection is A008549.
The following relate to compositions of n + 1 with alternating sum k < 0.
- The k = 1 version is A000984, ranked by A345909/A345911.
- The opposite (k > 0) version is A027306, ranked by A345917/A345918.
- The weak (k <= 0) version A058622, ranked by A345915/A345916.
- The k != 0 version is also A058622, ranked by A345921.
- The complement (k >= 0) is counted by A116406, ranked by A345913/A345914.
- The k = 0 version is A138364, ranked by A344619.
- The unordered version is A344608, ranked by A119899.
- Ranked by A345919 (reverse: A345920).
A097805 counts compositions by alternating (or reverse-alternating) sum.
A101211 lists run-lengths in binary expansion (reverse: A227736).
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001700, A007318, A025047, A032443, A034871, A106356, A114121, A126869, A163493, A344743, A345908, A289871, A359066, A359067.

Programs

  • Maple
    f:= gfun:-rectoproc({(8+8*n)*a(n)+(4*n+16)*a(1+n)+(-20-6*n)*a(n+2)+(-5-n)*a(n+3)+(5+n)*a(n+4), a(0) = 0, a(1) = 0, a(2) = 1, a(3) = 1}, a(n), remember):
map(f, [$0..40]); # Robert Israel, Feb 12 2018
  • Mathematica
    f[n_] := 2^(n - 1) + ((1 + (-1)^n)/4) Binomial[n, n/2] - Binomial[n, Floor[n/2]]; Array[f, 38, 0] (* Robert G. Wilson v, Feb 10 2018 *)
Table[Length[Select[Tuples[{0,1},{n+1}],First[#]==1&&Count[#,0]>Count[#,1]&]],{n,0,10}] (* Gus Wiseman, Jul 22 2021 *)

Formula

From Robert Israel, Feb 12 2018: (Start)
G.f.: (x+1)*sqrt(1-4*x^2)/(2*x*(4*x^2-1))+(x-1)/(2*(2*x-1)*x).
D-finite with recurrence: (8+8*n)*a(n)+(4*n+16)*a(1+n)+(-20-6*n)*a(n+2)+(-5-n)*a(n+3)+(5+n)*a(n+4) = 0. (End)

A057977 GCD of consecutive central binomial coefficients: a(n) = gcd(A001405(n+1), A001405(n)).

Original entry on oeis.org

1, 1, 1, 3, 2, 10, 5, 35, 14, 126, 42, 462, 132, 1716, 429, 6435, 1430, 24310, 4862, 92378, 16796, 352716, 58786, 1352078, 208012, 5200300, 742900, 20058300, 2674440, 77558760, 9694845, 300540195, 35357670, 1166803110, 129644790, 4537567650
Offset: 0

Views

Author

Labos Elemer, Nov 13 2000

Keywords

Comments

The numbers can be seen as a generalization of the Catalan numbers, extending A000984(n)/(n+1) to A056040(n)/(floor(n/2)+1). They can also be seen as composing the aerated Catalan numbers A126120 with the aerated complementary Catalan numbers A138364. (Thus the name 'extended Catalan numbers' might be apt for this sequence.) - Peter Luschny, May 03 2011
a(n) is the number of lattice paths from (0,0) to (n,0) that do not go below the x-axis and consist of steps U=(1,1), D=(1,-1) and maximally one step H=(1,0). - Alois P. Heinz, Apr 17 2013
Equal to A063549 (see comments in that sequence). - Nathaniel Johnston, Nov 17 2014
a(n) can be computed with ballot numbers without multiplications or divisions, see Maple program. - Peter Luschny, Feb 23 2019

Examples

			This GCD equals A001405(n) for the smaller odd number gcd(C(12,6), C(11,5)) = gcd(924,462) = 462 = C(11,5).

Links

Crossrefs

Cf. A001405, A063549.
Bisections are A000108 and A001700.

Programs

  • Maple
    A057977_ogf := proc(z) b := z -> (z-1)/(2*z^2);
(2 + b(z))/sqrt(1-4*z^2) - b(z) end:
seq(coeff(series(A057977_ogf(z),z,n+3),z,n), n = 0..35);
A057977_rec := n -> `if`(n=0, 1, A057977_rec(n-1)*n^modp(n,2)
*(4/(n+2))^modp(n+1,2));
A057977_int := proc(n) int((x^(2*n-1)*((4-x)^2/x)^cos(Pi*n))^(1/4),x=0..4)/(2*Pi); round(evalf(%)) end:
A057977 := n -> (n!/iquo(n,2)!^2) / (iquo(n,2)+1):
seq(A057977(n), n=0..35); # Peter Luschny, Apr 30 2011
b := proc(p, q) option remember; local S;
   if p = 0 and q = 0 then return 1 fi;
   if p < 0 or  p > q then return 0 fi;
   S := b(p-2, q) + b(p, q-2);
   if type(q, odd) then S := S + b(p-1, q-1) fi;
   S end:
seq(b(n, n), n=0..35); # Peter Luschny, Feb 23 2019
  • Mathematica
    a[n_] := n! / (Quotient[n, 2]!^2 * (Quotient[n, 2]+1)); Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Feb 03 2012, after Peter Luschny *)
  • PARI
    a(n)=if(n<0,0,(n+n%2)!/(n\2+1)!/(n\2+n%2)!/(1+n%2))
a(n)=n!/(n\2)!^2/(n\2+1) \\ Charles R Greathouse IV, May 02 2011
  • Sage
    def A057977():
    x, n = 1, 1
    while True:
        yield x
        m = n if is_odd(n) else 4/(n+2)
        x *= m
        n += 1
a = A057977(); [next(a) for i in range(36)]   # Peter Luschny, Oct 21 2013

Formula

G.f.: (4*x^2+x-1+(1-x)*sqrt(1-4*x^2))/(2*sqrt(1-4*x^2)*x^2). E.g.f.: (1+1/x)*BesselI(1, 2*x). - Vladeta Jovovic, Jan 19 2004
From Peter Luschny, Apr 30 2011: (Start)
Recurrence: a(0) = 1 and a(n) = a(n-1)*n^[n odd]*(4/(n+2))^[n even] for n > 0.
Asymptotic formula: Let [n even] = 1 if n is even, 0 otherwise. Let N := n+1+[n even]. Then a(n) ~ 2^N /((n+1)^[n even]*sqrt(Pi*(2*N+1))).
Integral representation: a(n) = (1/(2*Pi))*Int_{x=0..4}(x^(2*n-1)* ((4-x)^2/x)^cos(Pi*n))^(1/4) (End)
E.g.f.: U(0) where U(k)= 1 + x/(1 - x/(x + (k+1)*(k+2)//U(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Oct 19 2012
From R. J. Mathar, Sep 16 2016: (Start)
D-finite with recurrence: (n+2)*a(n) - n*a(n-1) + 4*(-2*n+1)*a(n-2) + 4*(n-1)*a(n-3) + 16*(n-3)*a(n-4) = 0.
D-finite with recurrence: -(n+2)*(n^2-5)*a(n) + 4*(-2*n-1)*a(n-1) + 4*(n-1)*(n^2+2*n-4)*a(n-2) = 0. (End)
Sum_{n>=0} 1/a(n) = 8/3 + 8*Pi/(9*sqrt(3)). - Amiram Eldar, Aug 20 2022

A347463 Number of ordered factorizations of n with integer alternating product.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 4, 1, 1, 1, 7, 1, 4, 1, 4, 1, 1, 1, 6, 2, 1, 3, 4, 1, 1, 1, 11, 1, 1, 1, 18, 1, 1, 1, 6, 1, 1, 1, 4, 4, 1, 1, 20, 2, 4, 1, 4, 1, 6, 1, 6, 1, 1, 1, 8, 1, 1, 4, 26, 1, 1, 1, 4, 1, 1, 1, 35, 1, 1, 4, 4, 1, 1, 1, 20, 7, 1, 1, 8, 1, 1, 1, 6, 1, 8, 1, 4, 1, 1, 1, 32, 1, 4, 4, 18
Offset: 1

Views

Author

Gus Wiseman, Oct 07 2021

Keywords

Comments

An ordered factorization of n is a sequence of positive integers > 1 with product n.
We define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)).

Examples

			The ordered factorizations for n = 4, 8, 12, 16, 24, 32, 36:
  4     8       12      16        24      32          36
  2*2   4*2     6*2     4*4       12*2    8*4         6*6
        2*2*2   2*2*3   8*2       2*2*6   16*2        12*3
                3*2*2   2*2*4     3*2*4   2*2*8       18*2
                        2*4*2     4*2*3   2*4*4       2*2*9
                        4*2*2     6*2*2   4*2*4       2*3*6
                        2*2*2*2           4*4*2       2*6*3
                                          8*2*2       3*2*6
                                          2*2*4*2     3*3*4
                                          4*2*2*2     3*6*2
                                          2*2*2*2*2   4*3*3
                                                      6*2*3
                                                      6*3*2
                                                      9*2*2
                                                      2*2*3*3
                                                      2*3*3*2
                                                      3*2*2*3
                                                      3*3*2*2

Links

Crossrefs

Positions of 2's are A001248.
Positions of 1's are A005117.
The restriction to powers of 2 is A116406.
The even-length case is A347048
The odd-length case is A347049.
The unordered version is A347437, reciprocal A347439, reverse A347442.
The case of partitions is A347446, reverse A347445, ranked by A347457.
A001055 counts factorizations (strict A045778, ordered A074206).
A046099 counts factorizations with no alternating permutations.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A119620 counts partitions with alternating product 1, ranked by A028982.
A273013 counts ordered factorizations of n^2 with alternating product 1.
A339846 counts even-length factorizations, ordered A174725.
A339890 counts odd-length factorizations, ordered A174726.
A347438 counts factorizations with alternating product 1.
A347460 counts possible alternating products of factorizations.
Cf. A025047, A038548, A138364, A347440, A347441, A347453, A347454, A347456, A347458, A347459, A347464, A347705, A347708.

Programs

  • Mathematica
    facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
altprod[q_]:=Product[q[[i]]^(-1)^(i-1),{i,Length[q]}];
Table[Length[Select[Join@@Permutations/@facs[n],IntegerQ[altprod[#]]&]],{n,100}]
  • PARI
    A347463(n, m=n, ap=1, e=0) = if(1==n, if(e%2, 1==denominator(ap), 1==numerator(ap)), sumdiv(n, d, if(d>1, A347463(n/d, d, ap * d^((-1)^e), 1-e)))); \\ Antti Karttunen, Jul 28 2024

Formula

a(n) = A347048(n) + A347049(n).

Extensions

Data section extended up to a(100) by Antti Karttunen, Jul 28 2024

A039004 Numbers whose base-4 representation has the same number of 1's and 2's.

Original entry on oeis.org

0, 3, 6, 9, 12, 15, 18, 24, 27, 30, 33, 36, 39, 45, 48, 51, 54, 57, 60, 63, 66, 72, 75, 78, 90, 96, 99, 102, 105, 108, 111, 114, 120, 123, 126, 129, 132, 135, 141, 144, 147, 150, 153, 156, 159, 165, 177, 180, 183, 189, 192, 195, 198, 201, 204, 207, 210, 216, 219
Offset: 1

Views

Author

Olivier Gérard

Keywords

Comments

Numbers such that sum (-1)^k*b(k) = 0 where b(k)=k-th binary digit of n (see A065359). - Benoit Cloitre, Nov 18 2003
Conjecture: a(C(2n,n)-1) = 4^n - 1. (A000984 is C(2n,n)). - Gerald McGarvey, Nov 18 2007
From Russell Jay Hendel, Jun 23 2015: (Start)
We prove the McGarvey conjecture (A) a(e(n,n)-1) = 4^n-1, with e(n,m) = A034870(n,m) = binomial(2n,m), the even rows of Pascal's triangle. By the comment from Hendel in A034870, we have the function s(n,k) = #{n-digit, base-4 numbers with n-k more 1-digits than 2-digits}. As shown in A034870, (B) #s(n,k)= e(n,k) with # indicating cardinality, that is, e(n,k) = binomial(2n,k) gives the number of n-digit, base-4 numbers with n-k more 1-digits than 2-digits.
We now show that (B) implies (A). By definition, s(n,n) contains the e(n,n) = binomial(2n,n) numbers with an equal number of 1-digits and 2-digits. The biggest n-digit, base-4 number is 333...3 (n copies of 3). Since 333...33 has zero 1-digits and zero 2-digits it follows that 333...333 is a member of s(n,n) and hence it is the biggest member of s(n,n). But 333...333 (n copies of 3) in base 4 has value 4^n-1. Since A039004 starts with index 0 (that is, 0 is the 0th member of A039004), it immediately follows that 4^n-1 is the (e(n,n)-1)st member of A039004, proving the McGarvey conjecture. (End)
Also numbers whose alternating sum of binary expansion is 0, i.e., positions of zeros in A345927. These are numbers whose binary expansion has the same number of 1's at even positions as at odd positions. - Gus Wiseman, Jul 28 2021

Links

Crossrefs

Cf. A139370, A139371, A139372, A139373.
Cf. A139351, A139352, A139353, A139354, A139355.
A subset of A001969 (evil numbers).
A base-2 version is A031443 (digitally balanced numbers).
Positions of 0's in A065359 and A345927.
Positions of first appearances are A086893.
The version for standard compositions is A344619.
A000120 and A080791 count binary digits, with difference A145037.
A003714 lists numbers with no successive binary indices.
A011782 counts compositions.
A030190 gives the binary expansion of each nonnegative integer.
A070939 gives the length of an integer's binary expansion.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A101211 lists run-lengths in binary expansion:
- row-lengths: A069010
- reverse: A227736
- ones only: A245563
A138364 counts compositions with alternating sum 0:
- bisection: A001700/A088218
- complement: A058622
A328594 lists numbers whose binary expansion is aperiodic.
A345197 counts compositions by length and alternating sum.
Cf. A000302, A000346, A003242, A029837, A053738, A053754, A071321, A103919, A191232, A328596.

Programs

  • Fortran
    c See link in A139351.
  • Maple
    N:= 1000: # to get all terms up to N, which should be divisible by 4
B:= Array(0..N-1):
d:= ceil(log[4](N));
S:= Array(0..N-1,[seq(op([0,1,-1,0]),i=1..N/4)]):
for i from 1 to d do
  B:= B + S;
  S:= Array(0..N-1,i-> S[floor(i/4)]);
od:
select(t -> B[t]=0, [$0..N-1]); # Robert Israel, Jun 24 2015
  • Mathematica
    ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Select[Range[0,100],ats[IntegerDigits[#,2]]==0&] (* Gus Wiseman, Jul 28 2021 *)
  • PARI
    for(n=0,219,if(sum(i=1,length(binary(n)),(-1)^i*component(binary(n),i))==0,print1(n,",")))

Formula

Conjecture: there is a constant c around 5 such that a(n) is asymptotic to c*n. - Benoit Cloitre, Nov 24 2002
That conjecture is false. The number of members of the sequence from 0 to 4^d-1 is binomial(2d,d) which by Stirling's formula is asymptotic to 4^d/sqrt(Pi*d). If Cloitre's conjecture were true we would have 4^d-1 asymptotic to c*4^d/sqrt(Pi*d), a contradiction. - Robert Israel, Jun 24 2015

A274230 Number of holes in a sheet of paper when you fold it n times and cut off the four corners.

Original entry on oeis.org

0, 0, 1, 3, 9, 21, 49, 105, 225, 465, 961, 1953, 3969, 8001, 16129, 32385, 65025, 130305, 261121, 522753, 1046529, 2094081, 4190209, 8382465, 16769025, 33542145, 67092481, 134193153, 268402689, 536821761, 1073676289, 2147385345
Offset: 0

Views

Author

Philippe Gibone, Jun 15 2016

Keywords

Comments

The folds are always made so the longer side becomes the shorter side.
We could have counted not only the holes but also all the notches: 4, 6, 9, 15, 25, 45, 81, 153, 289, ... which has the formula a(n) = (2^ceiling(n/2) + 1) * (2^floor(n/2) + 1) and appears to match the sequence A183978. - Philippe Gibone, Jul 06 2016
The same sequence (0,0,1,3,9,21,49,...) turns up when you start with an isosceles right triangular piece of paper and repeatedly fold it in half, snipping corners as you go. Is there an easy way to see why the two questions have the same answer? - James Propp, Jul 05 2016
Reply from Tom Karzes, Jul 05 2016: (Start)
This case seems a little more complicated than the rectangular case, since with the triangle you alternate between horizontal/vertical folds vs. diagonal folds, and the resulting fold pattern is more complex, but I think the basic argument is essentially the same.
Note that with the triangle, the first hole doesn't appear until after you've made 3 folds, so if you start counting at zero folds, you have three leading zeros in the sequence: 0,0,0,1,3,9,21,... (End)
Also the number of subsets of {1,2,...,n} that contain both even and odd numbers. For example, a(3)=3 and the 3 subsets are {1,2}, {2,3}, {1,2,3}; a(4)=9 and the 9 subsets are {1,2}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}. (See comments in A052551 for the number of subsets of {1,2,...,n} that contain only odd and even numbers.) - Enrique Navarrete, Mar 26 2018
Also the number of integer compositions of n + 1 with an odd part other than the first or last. The complementary compositions are counted by A052955(n>0) = A027383(n) + 1. - Gus Wiseman, Feb 05 2022
Also the number of unit squares in the (n+1)-st iteration in the version of the dragon curve where the rotation directions alternate, so that any clockwise rotation is followed by a counterclockwise rotation, and vice versa (see image link below). - Talmon Silver, May 09 2023

Links

Crossrefs

Cf. A000225, A079667, A183978.
See A274626, A274627 for the three- and higher-dimensional analogs.
This is the main diagonal of A274635.
Counting fold lines instead of holes gives A027383.
Bisections are A060867 (even) and A134057 (odd).
Cf. A000712, A001405, A008549, A011782, A026010, A052955, A097613, A126869, A138364, A232580, A351003.

Programs

Formula

u(0) = 0; v(0) = 0; u(n+1) = v(n); v(n+1) = 2u(n) + 1; a(n) = u(n)*v(n).
a(n) = (2^ceiling(n/2) - 1)*(2^floor(n/2) - 1).
Proof from Tom Karzes, Jul 05 2016: (Start)
Let r be the number of times you fold along one axis and s be the number of times you fold along the other axis. So r is ceiling(n/2) and s is floor(n/2), where n is the total number of folds.
When unfolded, the resulting paper has been divided into a grid of (2^r) by (2^s) rectangles. The interior grid lines will have diamond-shaped holes where they intersect (assuming diagonal cuts).
There are (2^r-1) internal grid lines along one axis and (2^s-1) along the other. The total number of internal grid line intersections is therefore (2^r-1)*(2^s-1), or (2^ceiling(n/2)-1)*(2^floor(n/2)-1) as claimed. (End)
From Colin Barker, Jun 22 2016, revised by N. J. A. Sloane, Jul 05 2016: (Start)
It follows that:
a(n) = (2^(n/2)-1)^2 for n even, a(n) = 2^n+1-3*2^((n-1)/2) for n odd.
a(n) = 3*a(n-1)-6*a(n-3)+4*a(n-4) for n>3.
G.f.: x^2 / ((1-x)*(1-2*x)*(1-2*x^2)).
a(n) = (1+2^n-2^((n-3)/2)*(3-3*(-1)^n+2*sqrt(2)+2*(-1)^n*sqrt(2))). (End)
a(n) = A000225(n) - 2*A052955(n-2) for n > 1. - Yuchun Ji, Nov 19 2018
a(n) = A079667(2^(n-1)) for n >= 1. - J. M. Bergot, Jan 18 2021
a(n) = 2^(n-1) - A052955(n) = 2^(n-1) - A027383(n) - 1. - Gus Wiseman, Jan 29 2022
E.g.f.: cosh(x) + cosh(2*x) - 2*cosh(sqrt(2)*x) + sinh(x) + sinh(2*x) - 3*sinh(sqrt(2)*x)/sqrt(2). - Stefano Spezia, Apr 06 2022
Showing 1-10 of 38 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.