cp's OEIS Frontend

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

Also a(n) = 2nd elementary symmetric function of binomial(n,0), binomial(n,1), ..., binomial(n,n).

Also a(n) = one half the sum of the heights, over all Dyck (n+2)-paths, of the vertices that are at even height and terminate an upstep. For example with n=1, these vertices are indicated by asterisks in the 5 Dyck 3-paths: UU*UDDD, UU*DU*DD, UDUU*DD, UDUDUD, UU*DDUD, yielding a(1)=(2+4+2+0+2)/2=5. - David Callan, Jul 14 2006

Hankel transform is (-1)^n*(2n+1); the Hankel transform of sum(k=0..n, C(2*n,k) ) - C(2n,n) is (-1)^n*n. - Paul Barry, Jan 21 2007

Row sums of the Riordan matrix (1/(1-4x),(1-sqrt(1-4x))/2) (A187926). - Emanuele Munarini, Mar 16 2011

From Gus Wiseman, Jul 19 2021: (Start)

For n > 0, a(n-1) is also the number of integer compositions of 2n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A053754 /\ A345921. For example, the a(3-1) = 22 compositions of 6 are:

(6) (1,5) (1,1,4) (1,1,1,3) (1,1,1,1,2)

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

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

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

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

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

(3,2,1)

(4,1,1)

(End)

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)

Inverse binomial transform of A027914. Hankel transform (see A001906 for definition) is {1, 2, 3, 4, ..., n, ...}. - Philippe Deléham, Jul 21 2005

Number of walks of length n on a line that starts at the origin and ends at or above 0. - Benjamin Phillabaum, Mar 05 2011

Number of binary integers (i.e., with a leading 1 bit) of length n+1 which have a majority of 1-bits. E.g., for n+1=4: (1011, 1101, 1110, 1111) a(3)=4. - Toby Gottfried, Dec 11 2011

Number of distinct symmetric staircase walks connecting opposite corners of a square grid of side n > 1. - Christian Barrientos, Nov 25 2018

From Gus Wiseman, Aug 20 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. These compositions are ranked by A345917. For example, the a(0) = 1 through a(4) = 11 compositions are:

(1) (2) (3) (4) (5)

(21) (31) (32)

(111) (112) (41)

(211) (113)

(122)

(212)

(221)

(311)

(1121)

(2111)

(11111)

The following relate to these compositions:

- The unordered version is A027193.

- The complement is counted by A058622.

- The reverse unordered version is A086543.

- The version for alternating sum >= 0 is A116406.

- The version for alternating sum < 0 is A294175.

- Ranked by A345917. (End)

The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. - Peter Bala, Jan 07 2022

Area under Dyck excursions (paths ending in 0): a(n) is the sum of the areas under all Dyck excursions of length 2*n (nonnegative walks beginning and ending in 0 with jumps -1,+1).

Number of inversions in all 321-avoiding permutations of [n+1]. Example: a(2)=6 because the 321-avoiding permutations of [3], namely 123,132,312,213,231, have 0, 1, 2, 1, 2 inversions, respectively. - Emeric Deutsch, Jul 28 2003

Convolution of A001791 and A000984. - Paul Barry, Feb 16 2005

a(n) = total semilength of "longest Dyck subpath" starting at an upstep U taken over all upsteps in all Dyck paths of semilength n. - David Callan, Jul 25 2008

[1,6,29,130,562,2380,...] is convolution of A001700 with itself. - Philippe Deléham, May 19 2009

From Ran Pan, Feb 04 2016: (Start)

a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) bounce off the diagonal y = x to the right. This is related to paired pattern P_2 in Pan and Remmel's link and more details can be found in Section 3.2 in the link.

a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) horizontally cross the diagonal y = x. This is related to paired pattern P_3 in Pan and Remmel's link and more details can be found in Section 3.3 in the link.

2*a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) bounce off the diagonal y = x. This is related to paired pattern P_2 and P_4 in Pan and Remmel's link and more details can be found in Section 4.2 in the link.

2*a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) cross the diagonal y = x. This is related to paired pattern P_3 and P_4 in Pan and Remmel's link and more details can be found in Section 4.3 in the link. (End)

From Gus Wiseman, Jul 17 2021: (Start)

Also the number of integer compositions of 2*(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(3) = 29 compositions of 8 are:

(1,7) (1,5,2) (1,1,1,5) (1,1,1,4,1) (1,1,1,1,1,3)

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

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

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

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

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

(1,4,1,2)

(1,4,2,1)

(1,5,1,1)

(2,1,1,4)

(2,2,1,3)

(2,3,1,2)

(2,4,1,1)

Also the number of integer compositions of 2*(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 2*(n+1)-digit binary numbers with more 0's than 1's. For example, the a(2) = 6 binary numbers are: 100000, 100001, 100010, 100100, 101000, 110000; or in decimal: 32, 33, 34, 36, 40, 48.

(End)

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

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) 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.

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) 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.