cp's OEIS Frontend

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.

A multiset partition is normal if it covers an initial interval of positive integers. It is unsortable if no permutation has an ordered concatenation, or equivalently if the concatenation of its lexicographically-ordered parts is not weakly increasing. For example, the multiset partition {{1,2},{1,1,1},{2,2,2}} is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

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 nesting if a < c and b > d or a > c and b < d.

Also unsortable digraphs with vertices {1..n}, where a digraph is sortable if, when the edges are listed in lexicographic order, their targets are weakly increasing.

Also the number of semicrossing digraphs with vertices {1..n}, where two edges (a,b), (c,d) are semicrossing if a < c and b < d or a > c and b > d. For example, the a(2) = 4 semicrossing digraph edge-sets are:

{11,22}

{11,12,22}

{11,21,22}

{11,12,21,22}

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is obtained by taking the multiset of prime indices of each prime index of n.

A multiset partition is unsortable if no permutation has an ordered concatenation. For example, the multiset partition ((1,2),(1,1,1),(2,2,2)) is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

First differs from A326256 in having 2599.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is obtained by taking the multiset of prime indices of each prime index of n.

A multiset partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and t < y or z < x and y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

A set partition is crossing if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < y < t or z < x < t < y, and nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < t < y or z < x < y < t.

A multiset partition is normal if it covers an initial interval of positive integers. It is sortable if some permutation has an ordered concatenation. For example, the multiset partition {{1,2},{1,1,1},{2,2,2}} is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

These are digraphs with the property that, if the edges are listed in lexicographic order, the sequence of targets is weakly increasing. For example, the digraph with lexicographically ordered edge set {(1,2),(2,1),(3,1),(3,2)} is nesting because the targets are (2,1,1,2), a sequence that is not weakly increasing.

Also the number of non-semicrossing digraphs with vertices {1..n}, where two edges (a,b), (c,d) are semicrossing if a < c and b < d or a > c and b > d. For example, the a(2) = 4 non-semicrossing digraph edge-sets are:

{}

{11}

{12}

{21}

{22}

{11,12}

{11,21}

{12,21}

{12,22}

{21,22}

{11,12,21}

{12,21,22}

Apparently a duplicate of A152254. - R. J. Mathar, Jul 12 2019