cp's OEIS Frontend

Devadoss refers to these numbers as type B Catalan numbers (cf. A000108).

Equal to the binomial coefficient sum Sum_{k=0..n} binomial(n,k)^2.

Number of possible interleavings of a program with n atomic instructions when executed by two processes. - Manuel Carro (mcarro(AT)fi.upm.es), Sep 22 2001

Convolving a(n) with itself yields A000302, the powers of 4. - T. D. Noe, Jun 11 2002

Number of ordered trees with 2n+1 edges, having root of odd degree and nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002

Also number of directed, convex polyominoes having semiperimeter n+2.

Also number of diagonally symmetric, directed, convex polyominoes having semiperimeter 2n+2. - Emeric Deutsch, Aug 03 2002

The second inverse binomial transform of this sequence is this sequence with interpolated zeros. Its g.f. is (1 - 4*x^2)^(-1/2), with n-th term C(n,n/2)(1+(-1)^n)/2. - Paul Barry, Jul 01 2003

Number of possible values of a 2n-bit binary number for which half the bits are on and half are off. - Gavin Scott (gavin(AT)allegro.com), Aug 09 2003

Ordered partitions of n with zeros to n+1, e.g., for n=4 we consider the ordered partitions of 11110 (5), 11200 (30), 13000 (20), 40000 (5) and 22000 (10), total 70 and a(4)=70. See A001700 (esp. Mambetov Bektur's comment). - Jon Perry, Aug 10 2003

Number of nondecreasing sequences of n integers from 0 to n: a(n) = Sum_{i_1=0..n} Sum_{i_2=i_1..n}...Sum_{i_n=i_{n-1}..n}(1). - J. N. Bearden (jnb(AT)eller.arizona.edu), Sep 16 2003

Number of peaks at odd level in all Dyck paths of semilength n+1. Example: a(2)=6 because we have U*DU*DU*D, U*DUUDD, UUDDU*D, UUDUDD, UUU*DDD, where U=(1,1), D=(1,-1) and * indicates a peak at odd level. Number of ascents of length 1 in all Dyck paths of semilength n+1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(2)=6 because we have uDuDuD, uDUUDD, UUDDuD, UUDuDD, UUUDDD, where an ascent of length 1 is indicated by a lower case letter. - Emeric Deutsch, Dec 05 2003

a(n-1) = number of subsets of 2n-1 distinct elements taken n at a time that contain a given element. E.g., n=4 -> a(3)=20 and if we consider the subsets of 7 taken 4 at a time with a 1 we get (1234, 1235, 1236, 1237, 1245, 1246, 1247, 1256, 1257, 1267, 1345, 1346, 1347, 1356, 1357, 1367, 1456, 1457, 1467, 1567) and there are 20 of them. - Jon Perry, Jan 20 2004

The dimension of a particular (necessarily existent) absolutely universal embedding of the unitary dual polar space DSU(2n,q^2) where q>2. - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004.

Number of standard tableaux of shape (n+1, 1^n). - Emeric Deutsch, May 13 2004

Erdős, Graham et al. conjectured that a(n) is never squarefree for sufficiently large n (cf. Graham, Knuth, Patashnik, Concrete Math., 2nd ed., Exercise 112). Sárközy showed that if s(n) is the square part of a(n), then s(n) is asymptotically (sqrt(2)-2) * (sqrt(n)) * zeta(1/2). Granville and Ramare proved that the only squarefree values are a(1)=2, a(2)=6 and a(4)=70. - Jonathan Vos Post, Dec 04 2004 [For more about this conjecture, see A261009. - N. J. A. Sloane, Oct 25 2015]

The MathOverflow link contains the following comment (slightly edited): The Erdős squarefree conjecture (that a(n) is never squarefree for n>4) was proved in 1980 by Sárközy, A. (On divisors of binomial coefficients. I. J. Number Theory 20 (1985), no. 1, 70-80.) who showed that the conjecture holds for all sufficiently large values of n, and by A. Granville and O. Ramaré (Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. Mathematika 43 (1996), no. 1, 73-107) who showed that it holds for all n>4. - Fedor Petrov, Nov 13 2010. [From N. J. A. Sloane, Oct 29 2015]

p divides a((p-1)/2)-1=A030662(n) for prime p=5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, ... = A002144(n) Pythagorean primes: primes of form 4n+1. - Alexander Adamchuk, Jul 04 2006

The number of direct routes from my home to Granny's when Granny lives n blocks south and n blocks east of my home in Grid City. To obtain a direct route, from the 2n blocks, choose n blocks on which one travels south. For example, a(2)=6 because there are 6 direct routes: SSEE, SESE, SEES, EESS, ESES and ESSE. - Dennis P. Walsh, Oct 27 2006

Inverse: With q = -log(log(16)/(pi a(n)^2)), ceiling((q + log(q))/log(16)) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 26 2007

Number of partitions with Ferrers diagrams that fit in an n X n box (including the empty partition of 0). Example: a(2) = 6 because we have: empty, 1, 2, 11, 21 and 22. - Emeric Deutsch, Oct 02 2007

So this is the 2-dimensional analog of A008793. - William Entriken, Aug 06 2013

The number of walks of length 2n on an infinite linear lattice that begins and ends at the origin. - Stefan Hollos (stefan(AT)exstrom.com), Dec 10 2007

The number of lattice paths from (0,0) to (n,n) using steps (1,0) and (0,1). - Joerg Arndt, Jul 01 2011

Integral representation: C(2n,n)=1/Pi Integral [(2x)^(2n)/sqrt(1 - x^2),{x,-1, 1}], i.e., C(2n,n)/4^n is the moment of order 2n of the arcsin distribution on the interval (-1,1). - N-E. Fahssi, Jan 02 2008

Also the Catalan transform of A000079. - R. J. Mathar, Nov 06 2008

Straub, Amdeberhan and Moll: "... it is conjectured that there are only finitely many indices n such that C_n is not divisible by any of 3, 5, 7 and 11." - Jonathan Vos Post, Nov 14 2008

Equals INVERT transform of A081696: (1, 1, 3, 9, 29, 97, 333, ...). - Gary W. Adamson, May 15 2009

Also, in sports, the number of ordered ways for a "Best of 2n-1 Series" to progress. For example, a(2) = 6 means there are six ordered ways for a "best of 3" series to progress. If we write A for a win by "team A" and B for a win by "team B" and if we list the played games chronologically from left to right then the six ways are AA, ABA, BAA, BB, BAB, and ABB. (Proof: To generate the a(n) ordered ways: Write down all a(n) ways to designate n of 2n games as won by team A. Remove the maximal suffix of identical letters from each of these.) - Lee A. Newberg, Jun 02 2009

Number of n X n binary arrays with rows, considered as binary numbers, in nondecreasing order, and columns, considered as binary numbers, in nonincreasing order. - R. H. Hardin, Jun 27 2009

Hankel transform is 2^n. - Paul Barry, Aug 05 2009

It appears that a(n) is also the number of quivers in the mutation class of twisted type BC_n for n>=2.

Central terms of Pascal's triangle: a(n) = A007318(2*n,n). - Reinhard Zumkeller, Nov 09 2011

Number of words on {a,b} of length 2n such that no prefix of the word contains more b's than a's. - Jonathan Nilsson, Apr 18 2012

From Pascal's triangle take row(n) with terms in order a1,a2,..a(n) and row(n+1) with terms b1,b2,..b(n), then 2*(a1*b1 + a2*b2 + ... + a(n)*b(n)) to get the terms in this sequence. - J. M. Bergot, Oct 07 2012. For example using rows 4 and 5: 2*(1*(1) + 4*(5) + 6*(10) + 4*(10) + 1*(5)) = 252, the sixth term in this sequence.

Take from Pascal's triangle row(n) with terms b1, b2, ..., b(n+1) and row(n+2) with terms c1, c2, ..., c(n+3) and find the sum b1*c2 + b2*c3 + ... + b(n+1)*c(n+2) to get A000984(n+1). Example using row(3) and row(5) gives sum 1*(5)+3*(10)+3*(10)+1*(5) = 70 = A000984(4). - J. M. Bergot, Oct 31 2012

a(n) == 2 mod n^3 iff n is a prime > 3. (See Mestrovic link, p. 4.) - Gary Detlefs, Feb 16 2013

Conjecture: For any positive integer n, the polynomial sum_{k=0}^n a(k)x^k is irreducible over the field of rational numbers. In general, for any integer m>1 and n>0, the polynomial f_{m,n}(x) = Sum_{k=0..n} (m*k)!/(k!)^m*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013

This comment generalizes the comment dated Oct 31 2012 and the second of the sequence's original comments. For j = 1 to n, a(n) = Sum_{k=0..j} C(j,k)* C(2n-j, n-k) = 2*Sum_{k=0..j-1} C(j-1,k)*C(2n-j, n-k). - Charlie Marion, Jun 07 2013

The differences between consecutive terms of the sequence of the quotients between consecutive terms of this sequence form a sequence containing the reciprocals of the triangular numbers. In other words, a(n+1)/a(n)-a(n)/a(n-1) = 2/(n*(n+1)). - Christian Schulz, Jun 08 2013

Number of distinct strings of length 2n using n letters A and n letters B. - Hans Havermann, May 07 2014

From Fung Lam, May 19 2014: (Start)

Expansion of G.f. A(x) = 1/(1+q*x*c(x)), where parameter q is positive or negative (except q=-1), and c(x) is the g.f. of A000108 for Catalan numbers. The case of q=-1 recovers the g.f. of A000108 as xA^2-A+1=0. The present sequence A000984 refers to q=-2. Recurrence: (1+q)*(n+2)*a(n+2) + ((q*q-4*q-4)*n + 2*(q*q-q-1))*a(n+1) - 2*q*q*(2*n+1)*a(n) = 0, a(0)=1, a(1)=-q. Asymptotics: a(n) ~ ((q+2)/(q+1))*(q^2/(-q-1))^n, q<=-3, a(n) ~ (-1)^n*((q+2)/(q+1))*(q^2/(q+1))^n, q>=5, and a(n) ~ -Kq*2^(2*n)/sqrt(Pi*n^3), where the multiplicative constant Kq is given by K1=1/9 (q=1), K2=1/8 (q=2), K3=3/25 (q=3), K4=1/9 (q=4). These formulas apply to existing sequences A126983 (q=1), A126984 (q=2), A126982 (q=3), A126986 (q=4), A126987 (q=5), A127017 (q=6), A127016 (q=7), A126985 (q=8), A127053 (q=9), and to A007854 (q=-3), A076035 (q=-4), A076036 (q=-5), A127628 (q=-6), A126694 (q=-7), A115970 (q=-8). (End)

a(n)*(2^n)^(j-2) equals S(n), where S(n) is the n-th number in the self-convolved sequence which yields the powers of 2^j for all integers j, n>=0. For example, when n=5 and j=4, a(5)=252; 252*(2^5)^(4-2) = 252*1024 = 258048. The self-convolved sequence which yields powers of 16 is {1, 8, 96, 1280, 17920, 258048, ...}; i.e., S(5) = 258048. Note that the convolved sequences will be composed of numbers decreasing from 1 to 0, when j<2 (exception being j=1, where the first two numbers in the sequence are 1 and all others decreasing). - Bob Selcoe, Jul 16 2014

The variance of the n-th difference of a sequence of pairwise uncorrelated random variables each with variance 1. - Liam Patrick Roche, Jun 04 2015

Number of ordered trees with n edges where vertices at level 1 can be of 2 colors. Indeed, the standard decomposition of ordered trees leading to the equation C = 1 + zC^2 (C is the Catalan function), yields this time G = 1 + 2zCG, from where G = 1/sqrt(1-4z). - Emeric Deutsch, Jun 17 2015

Number of monomials of degree at most n in n variables. - Ran Pan, Sep 26 2015

Let V(n, r) denote the volume of an n-dimensional sphere with radius r, then V(n, 2^n) / Pi = V(n-1, 2^n) * a(n/2) for all even n. - Peter Luschny, Oct 12 2015

a(n) is the number of sets {i1,...,in} of length n such that n >= i1 >= i2 >= ... >= in >= 0. For instance, a(2) = 6 as there are only 6 such sets: (2,2) (2,1) (2,0) (1,1) (1,0) (0,0). - Anton Zakharov, Jul 04 2016

From Ralf Steiner, Apr 07 2017: (Start)

By analytic continuation to the entire complex plane there exist regularized values for divergent sums such as:

Sum_{k>=0} a(k)/(-2)^k = 1/sqrt(3).

Sum_{k>=0} a(k)/(-1)^k = 1/sqrt(5).

Sum_{k>=0} a(k)/(-1/2)^k = 1/3.

Sum_{k>=0} a(k)/(1/2)^k = -1/sqrt(7)i.

Sum_{k>=0} a(k)/(1)^k = -1/sqrt(3)i.

Sum_{k>=0} a(k)/2^k = -i. (End)

Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j). [Martinez and Savage, 2.18] - Eric M. Schmidt, Jul 17 2017

The o.g.f. for the sequence equals the diagonal of any of the following the rational functions: 1/(1 - (x + y)), 1/(1 - (x + y*z)), 1/(1 - (x + x*y + y*z)) or 1/(1 - (x + y + y*z)). - Peter Bala, Jan 30 2018

From Colin Defant, Sep 16 2018: (Start)

Let s denote West's stack-sorting map. a(n) is the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 231, and 321. a(n) is also the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 312, and 321.

a(n) is the number of permutations of [n+1] that avoid the patterns 1342, 3142, 3412, and 3421. (End)

All binary self-dual codes of length 4n, for n>0, must contain at least a(n) codewords of weight 2n. More to the point, there will always be at least one, perhaps unique, binary self-dual code of length 4n that will contain exactly a(n) codewords that have a hamming weight equal to half the length of the code (2n). This code can be constructed by direct summing the unique binary self-dual code of length 2 (up to permutation equivalence) to itself an even number of times. A permutation equivalent code can be constructed by augmenting two identity matrices of length 2n together. - Nathan J. Russell, Nov 25 2018

From Isaac Saffold, Dec 28 2018: (Start)

Let [b/p] denote the Legendre symbol and 1/b denote the inverse of b mod p. Then, for m and n, where n is not divisible by p,

[(m+n)/p] == [n/p]*Sum_{k=0..(p-1)/2} (-m/(4*n))^k * a(k) (mod p).

Evaluating this identity for m = -1 and n = 1 demonstrates that, for all odd primes p, Sum_{k=0..(p-1)/2} (1/4)^k * a(k) is divisible by p. (End)

Number of vertices of the subgraph of the (2n-1)-dimensional hypercube induced by all bitstrings with n-1 or n many 1s. The middle levels conjecture asserts that this graph has a Hamilton cycle. - Torsten Muetze, Feb 11 2019

a(n) is the number of walks of length 2n 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 from the origin with steps (1,0) and (0,1) that stay in the first octant. - Alexander Burstein, Dec 24 2019

Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {3>1, 1>2} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second element but smaller than the third elements. - Sergey Kitaev, Dec 08 2020

From Gus Wiseman, Jul 21 2021: (Start)

Also the number of integer compositions of 2n+1 with alternating sum 1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(0) = 1 through a(2) = 6 compositions are:

(1) (2,1) (3,2)

(1,1,1) (1,2,2)

(2,2,1)

(1,1,2,1)

(2,1,1,1)

(1,1,1,1,1)

The following relate to these compositions:

- The unordered version is A000070.

- The alternating sum -1 version is counted by A001791, ranked by A345910/A345912.

- The alternating sum 0 version is counted by A088218, ranked by A344619.

- Including even indices gives A126869.

- The complement is counted by A202736.

- Ranked by A345909 (reverse: A345911).

Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 1 than 0's. For example, the a(2) = 6 binary numbers are: 10011, 10101, 10110, 11001, 11010, 11100.

(End)

From Michael Wallner, Jan 25 2022: (Start)

a(n) is the number of nx2 Young tableaux with a single horizontal wall between the first and second column. If there is a wall between two cells, the entries may be decreasing; see [Banderier, Wallner 2021].

Example for a(2)=6:

3 4 2 4 3 4 3|4 4|3 2|4

1|2, 1|3, 2|1, 1 2, 1 2, 1 3

a(n) is also the number of nx2 Young tableaux with n "walls" between the first and second column.

Example for a(2)=6:

3|4 2|4 4|3 3|4 4|3 4|2

1|2, 1|3, 1|2, 2|1, 2|1, 3|1 (End)

From Shel Kaphan, Jan 12 2023: (Start)

a(n)/4^n is the probability that a fair coin tossed 2n times will come up heads exactly n times and tails exactly n times, or that a random walk with steps of +-1 will return to the starting point after 2n steps (not necessarily for the first time). As n becomes large, this number asymptotically approaches 1/sqrt(n*Pi), using Stirling's approximation for n!.

a(n)/(4^n*(2n-1)) is the probability that a random walk with steps of +-1 will return to the starting point for the first time after 2n steps. The absolute value of the n-th term of A144704 is denominator of this fraction.

Considering all possible random walks of exactly 2n steps with steps of +-1, a(n)/(2n-1) is the number of such walks that return to the starting point for the first time after 2n steps. See the absolute values of A002420 or A284016 for these numbers. For comparison, as mentioned by Stefan Hollos, Dec 10 2007, a(n) is the number of such walks that return to the starting point after 2n steps, but not necessarily for the first time. (End)

p divides a((p-1)/2) + 1 for primes p of the form 4*k+3 (A002145). - Jules Beauchamp, Feb 11 2023

Also the size of the shuffle product of two words of length n, such that the union of the two words consist of 2n distinct elements. - Robert C. Lyons, Mar 15 2023

a(n) is the number of vertices of the n-dimensional cyclohedron W_{n+1}. - Jose Bastidas, Mar 25 2025

Consider a stack of pancakes of height n, where the only allowed operation is reversing the top portion of the stack. First, perform a series of reversals of increasing sizes, followed by a series of reversals of decreasing sizes. The number of distinct permutations of the initial stack that can be reached through these operations is a(n). - Thomas Baruchel, May 12 2025

Essentially the same as A001700, which has more information.

Note that the unique rooted tree with no edges has no leaves, so a(0)=1 is by convention. - Michael Somos, Jul 30 2011

Number of ordered partitions of n into n parts, allowing zeros (cf. A097070) is binomial(2*n-1,n) = a(n) = essentially A001700. - Vladeta Jovovic, Sep 15 2004

Hankel transform is A000027; example: Det([1,1,3,10;1,3,10,35;3,10,35,126; 10,35,126,462]) = 4. - Philippe Deléham, Apr 13 2007

a(n) is the number of functions f:[n]->[n] such that for all x,y in [n] if xA045992(n). - Geoffrey Critzer, Apr 02 2009

Hankel transform of the aeration of this sequence is A000027 doubled: 1,1,2,2,3,3,... - Paul Barry, Sep 26 2009

The Fi1 and Fi2 triangle sums of A039599 are given by the terms of this sequence. For the definitions of these triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011

Alternating row sums of Riordan triangle A094527. See the Philippe Deléham formula. - Wolfdieter Lang, Nov 22 2012

(-2)*a(n) is the Z-sequence for the Riordan triangle A110162. For the notion of Z- and A-sequences for Riordan arrays see the W. Lang link under A006232 with details and references. - Wolfdieter Lang, Nov 22 2012

From Gus Wiseman, Jun 27 2021: (Start)

Also the number of integer compositions of 2n with alternating (or reverse-alternating) sum 0 (ranked by A344619). This is equivalent to Ran Pan's comment at A001700. For example, the a(0) = 1 through a(3) = 10 compositions are:

() (11) (22) (33)

(121) (132)

(1111) (231)

(1122)

(1221)

(2112)

(2211)

(11121)

(12111)

(111111)

For n > 0, a(n) is also the number of integer compositions of 2n with alternating sum 2.

(End)

Number of terms in the expansion of (x_1+x_2+...+x_n)^n. - César Eliud Lozada, Jan 08 2022

Number of peaks at even level in all Dyck paths of semilength n+1. Example: a(2)=4 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUUDDD, where U=(1,1), D=(1,-1) and the peaks at even level are shown by *. - Emeric Deutsch, Dec 05 2003

Also number of long ascents (i.e., ascents of length at least two) in all Dyck paths of semilength n+1. Example: a(2)=4 because in the five Dyck paths of semilength 3, namely UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and (UUU)DDD, we have four long ascents (shown between parentheses). Here U=(1,1) and D=(1,-1). Also number of branch nodes (i.e., vertices of outdegree at least two) in all ordered trees with n+1 edges. - Emeric Deutsch, Feb 22 2004

Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) which touch or cross the line x-y=1. Example: For n=2 these are the paths EENN, ENEN, ENNE and NEEN. - Herbert Kociemba, May 23 2004

Narayana transform (A001263) of [1, 3, 5, 7, 9, ...] = (1, 4, 15, 56, 210, ...). Row sums of triangles A136534 and A136536. - Gary W. Adamson, Jan 04 2008

Starting with offset 1 = the Catalan sequence starting (1, 2, 5, 14, ...) convolved with A000984: (1, 2, 6, 20, ...). - Gary W. Adamson, May 17 2009

Also number of peaks plus number of valleys in all Dyck n-paths. - David Scambler, Oct 08 2012

Apparently counts UDDUD in all Dyck paths of semilength n+2. - David Scambler, Apr 22 2013

Apparently the number of peaks strictly left of the midpoint in all Dyck paths of semilength n+1. - David Scambler, Apr 30 2013

For n>0, a(n) is the number of compositions of n into at most n parts if zeros are allowed as parts (so-called "weak" compositions). - L. Edson Jeffery, Jul 24 2014

Number of paths in the half-plane x >= 0, from (0,0) to (2n,2), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 4 paths: UUUD, UUDU, UDUU, DUUU. - José Luis Ramírez Ramírez, Apr 19 2015

For n>1, 1/a(n) is the probability that when a stick is broken up at n points independently and uniformly chosen at random along its length any triple of pieces of the n+1 pieces can form a triangle. The corresponding probability for the existence of at least one triple is A339392(n)/A339393(n). - Amiram Eldar, Dec 04 2020

a(n) is the number of lattice paths of 2n steps taken from the step set {U=(1,1), D=(1,-1)} that start at the origin, never go below the x-axis, and end strictly above the x-axis; more succinctly, proper left factors of Dyck paths. For example, a(2)=4 counts UUUU, UUUD, UUDU, UDUU. - David Callan and Emeric Deutsch, Jan 25 2021

From Gus Wiseman, Jul 21 2021: (Start)

Also the number of integer compositions of 2n+1 with alternating sum -1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(1) = 1 through a(3) = 15 compositions are:

(1,2) (2,3) (3,4)

(1,3,1) (1,4,2)

(1,1,1,2) (2,4,1)

(1,2,1,1) (1,1,2,3)

(1,2,2,2)

(1,3,2,1)

(2,1,1,3)

(2,2,1,2)

(2,3,1,1)

(1,1,1,3,1)

(1,2,1,2,1)

(1,3,1,1,1)

(1,1,1,1,1,2)

(1,1,1,2,1,1)

(1,2,1,1,1,1)

The following relate to these compositions.

- The unordered version is A000070.

- Allowing any negative alternating sum gives A000346.

- The opposite (positive 1) version is A000984.

- The version for reverse-alternating sum is also A001791 (this sequence).

- Taking alternating sum -2 instead of -1 gives A002054.

- The shifted version for alternating sum 0 is counted by A088218 and ranked by A344619.

- Ranked by A345910 (reverse: A345912).

Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 0 than 1's. For example, the a(2) = 4 binary numbers are: 10001, 10010, 10100, 11000.

(End)

The diagonal of a square n X n matrix where cells of the first row are the nonnegative integers and cells of subsequent rows are sums of cells of the previous row up to and including n. - Torlach Rush, Apr 24 2024

For n>=1, a(n) is the independence number of the odd graph O_{n+1}. - Miquel A. Fiol, Jul 07 2024

The alternating sum of a partition (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i, which is equal to the number of odd parts in the conjugate partition.

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.

Also the reverse-alternating sum of the prime indices of n.

Also number of partitions of 2*n with exactly 2 odd parts (offset 1). - Vladeta Jovovic, Jan 12 2005

Also number of transitions from one partition of n+2 to another, where a transition consists of replacing any two parts with their sum. Remove all 1' and 2' from the partition, replacing them with ((number of 2') + 1) and ((number of 1') + (number of 2') + 1); these are the two parts being summed. Number of partitions of n into parts of 2 kinds with at most 2 parts of the second kind, or of n+2 into parts of 2 kinds with exactly 2 parts of the second kind. - Franklin T. Adams-Watters, Mar 20 2006

From Christian Gutschwager (gutschwager(AT)math.uni-hannover.de), Feb 10 2010: (Start)

a(n) is also the number of pairs of partitions of n+2 which differ by only one box (for bijection see the first Gutschwager link).

a(n) is also the number of partitions of n with two parts marked.

a(n) is also the number of partitions of n+1 with two different parts marked. (End)

Convolution of A000041 and A008619. - Vaclav Kotesovec, Aug 18 2015

a(n) = P(/2,n), a particular case of P(/k,n) defined as follows: P(/0,n) = A000041(n) and P(/k,n) = P(/k-1, n) + P(/k-1,n-k) + P(/k-1, n-2k) + ... Also, P(/k,n) = the convolution of A000041 and the partitions of n with exactly k parts, and g.f. P(/k,n) = (g.f. for P(n)) * 1/(1-x)...(1-x^k). - Gregory L. Simay, Mar 22 2018

a(n) is also the sum of binomial(D(p),2) in partitions p of (n+3), where D(p)= number of different sizes of parts in p. - Emily Anible, Apr 03 2018

Also partitions of 2*(n+1) with alternating sum 2. Also partitions of 2*(n+1) with reverse-alternating sum -2 or 2. - Gus Wiseman, Jun 21 2021

Define the distance graph of the partitions of n using the distance function in A366156 as follows: two vertices (partitions) share an edge if and only if the distance between the vertices is 2. Then a(n) is the number of edges in the distance graph of the partitions of n. - Clark Kimberling, Oct 12 2023

Up to sign, same as A124754.

The reverse-alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(k-i) y_i.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

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

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

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

These compositions avoid the weak consecutive pattern (1,2,3), the strict version being A128761.