cp's OEIS Frontend

a(n) is the number of Dyck paths of semilength n with no UUDD. See A025242 for a bijection between paths avoiding DDUU versus UUDD.

Also number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=1. - Alois P. Heinz, Oct 07 2015

a(n) is the number of bargraphs of semiperimeter n (n>=2). Example: a(4) = 5; the 5 bargraphs correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3]. - Emeric Deutsch, May 20 2016 [a(n) are the row sums of A271942 for n >= 2. Peter Luschny, Oct 18 2020]

a(n) is the number of skew Motzkin paths of length n. A skew Motzkin path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1) (up), D=(1,-1) (down), F=(1,0) (flat) and A=(-1,1) (anti-down) so that down and anti-down steps do not overlap. - Sergey Kirgizov, Oct 03 2018

From Gus Wiseman, Jul 04 2019: (Start)

Conjecture: Also the number of maximal simple graphs with vertices {1..n} and no weakly nesting edges. Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d. For example, the a(1) = 1 through a(5) = 13 edge-sets are:

{} {12} {13} {14} {15}

{12,23} {12,24} {12,25}

{13,24} {13,25}

{13,34} {14,25}

{12,23,34} {14,35}

{14,45}

{12,23,35}

{12,24,35}

{12,24,45}

{13,24,35}

{13,24,45}

{13,34,45}

{12,23,34,45}

Cf. A006125, A054726, A117662, A326244, A326257, A326289, A326293, A326329, A326337, A326338, A326340.

(End)

a(n) is the number of Dyck n-paths in which no nonterminal descent has the same length as the preceding ascent. Example: a(3) = 2 counts UUDUDD and UUUDDD where the latter path qualifies because DDD is the terminal descent. - David Callan, Dec 14 2021

Related to Schröder's second problem.

A001006 gives number of ways of drawing any number of nonintersecting chords between n points on a circle, while this sequence gives number of ways of drawing noncrossing chords between n points on a circle. The difference is that nonintersection chords have no point in common, while noncrossing chords may share an endpoint. - David W. Wilson, Jan 30 2003

For n>0, a(n) = number of lattice paths from (0,0) to (n-1,n-1) that consist of steps (i,j), i,j nonnegative integers not both 0 and that stay strictly below the line y=x except at their endpoints. For example, a(3)=8 counts the paths with following step sequences: {(2, 2)}, {(2, 1), (0, 1)}, {(2, 0), (0, 2)}, {(2, 0), (0, 1), (0, 1)}, {(1, 0), (1, 2)}, {(1, 0), (1, 1), (0, 1)}, {(1, 0), (1, 0), (0, 2)}, {(1, 0), (1, 0), (0, 1), (0, 1)}. If the word "strictly" is replaced by "weakly", the counting sequence becomes A059435. - David Callan, Jun 07 2006

The nodes on the circle are distinguished by their positions but are otherwise unlabeled. - Lee A. Newberg, Aug 09 2011

From Gus Wiseman, Jun 22 2019: (Start)

Conjecture: Also the number of simple graphs with vertices {1..n} not containing any pair of nesting edges. Two edges {a,b}, {c,d} where a < b and c < d are nesting if a < c and b > d or a > c and b < d. For example, the a(0) = 1 through a(3) = 8 non-nesting edge-sets are:

{} {} {} {}

{12} {12}

{13}

{23}

{12,13}

{12,23}

{13,23}

{12,13,23}

Cf. A001519, A117662, A326244, A326256, A326257, A326279.

(End)

Also simple graphs containing a crossing pair of edges, where two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b.

Also simple graphs such that, if the edges are listed in lexicographic order, their maxima (seconds) are not weakly increasing.

Hankel transform is [1,1,1,...] = A000012. - Paul Barry, Jan 19 2009

The inverse Motzkin transform apparently yields 1 followed by A000930, which implies a generating function g(x)=1+z/(1-z-z^3) where z=x*A001006(x). - R. J. Mathar, Jul 07 2009

It appears that the infinite set of interpolated sequences between the Motzkin and the Catalan can be generated with a succession of INVERT transforms, given each sequence has two leading 1's. Also, the N-th sequence in the set starting with (N=1, A001006) can be generated from a production matrix of the form "M" in the formula section, such that the main diagonal is (N leading 1's, 0, 0, 0, ...). M with a diagonal of (1, 0, 0, 0, ...) generates A001006, while M with a main diagonal of all 1's is the production matrix for A000108. - Gary W. Adamson, Jul 29 2011

From Gus Wiseman, Jun 22 2019: (Start)

Conjecture: Also the number of non-capturing set partitions of {1..n}. A set partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and y > t or x > z and y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting. The a(0) = 1 through a(4) = 14 non-capturing set partitions are:

{} {{1}} {{1,2}} {{1,2,3}} {{1,2,3,4}}

{{1},{2}} {{1},{2,3}} {{1},{2,3,4}}

{{1,2},{3}} {{1,2},{3,4}}

{{1,3},{2}} {{1,2,3},{4}}

{{1},{2},{3}} {{1,2,4},{3}}

{{1,3},{2,4}}

{{1,3,4},{2}}

{{1},{2},{3,4}}

{{1},{2,3},{4}}

{{1,2},{3},{4}}

{{1},{2,4},{3}}

{{1,3},{2},{4}}

{{1,4},{2},{3}}

{{1},{2},{3},{4}}

Cf. A000108, A000110, A058681, A326212, A326237, A326243, A326244, A326249, A326255.

(End)

The above conjecture is true: A partition is non-capturing iff its representation in canonical sequential form avoids the patterns 1221 and 2112. In the context of these partition representations, the pattern 2112 is equivalent to the pattern 12112. Partitions whose canonical sequence form avoid 1221 and 12112 are one of the classes that are handled in the Mansour/Shattuck "Pattern Avoiding Partitions,..." paper. It shows that they are counted by this sequence. - Christian Sievers, Oct 29 2024

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d. A graph with positive integer vertices is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d.

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Is this (apart from offsets) the same as A073717? - R. J. Mathar, Jul 04 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Appears to be essentially the same as A003946.

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.