cp's OEIS Frontend

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.

For the definition of a purely crossing partition refer to Dykema link (see PC(n) Definition 1.2 and Table 2).

From Gus Wiseman, Feb 23 2019: (Start)

For n >= 1, a set partition of {1,...,n} is purely crossing if it is topologically connected (A099947), has no successive elements in the same block (A000110(n - 1)), and the first and last vertices belong to different blocks (A005493(n - 2)). For example, the a(4) = 1, a(6) = 5, and a(7) = 14 purely crossing set partitions are:

{{13}{24}} {{135}{246}} {{13}{246}{57}}

{{13}{25}{46}} {{13}{257}{46}}

{{14}{25}{36}} {{135}{26}{47}}

{{14}{26}{35}} {{135}{27}{46}}

{{15}{24}{36}} {{136}{24}{57}}

{{136}{25}{47}}

{{14}{257}{36}}

{{14}{26}{357}}

{{146}{25}{37}}

{{146}{27}{35}}

{{15}{246}{37}}

{{15}{247}{36}}

{{16}{24}{357}}

{{16}{247}{35}}

(End)

If all subsets are allowed instead of just pairs (chords), we get A324173. The rightmost column is A000108 (see Riordan). - Gus Wiseman, Feb 27 2019

A set partition of {1,...,n} is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...},{...z...t...}} for some x < z < y < t or z < x < t < y.

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 capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. Capturing is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

Two blocks are nesting if they are of the form {...x,y...}, {...z,t...} where x < z < t < y or z < x < y < t. A set partition has its nesting blocks connected if the graph whose vertices are the blocks and whose edges are nesting pairs of blocks is connected.

Two blocks are capturing if they are of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. A set partition has its capturing blocks connected if the graph whose vertices are the blocks and whose edges are capturing pairs of blocks is connected.

For the definition of these special purely crossing partitions refer to Dykema link (see PC+(n) Definition 2.1 and Table 2).

From Gus Wiseman, Feb 23 2019: (Start)

a(n) is the number of topologically connected (A099947) set partitions of {1,...,n} with no successive elements in the same block. For example, the a(4) = 1 through a(7) = 19 set partitions are:

{{13}{24}} {{135}{24}} {{135}{246}} {{1357}{246}}

{{13}{25}{46}} {{13}{246}{57}}

{{14}{25}{36}} {{13}{257}{46}}

{{14}{26}{35}} {{135}{26}{47}}

{{15}{24}{36}} {{135}{27}{46}}

{{136}{24}{57}}

{{136}{25}{47}}

{{137}{25}{46}}

{{14}{257}{36}}

{{14}{26}{357}}

{{146}{25}{37}}

{{146}{27}{35}}

{{147}{25}{36}}

{{147}{26}{35}}

{{15}{246}{37}}

{{15}{247}{36}}

{{157}{24}{36}}

{{16}{24}{357}}

{{16}{247}{35}}

(End)

This multiset (row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

A multiset partition is crossing if it contains two blocks of the form {{...x...y...},{...z...t...}} with x < z < y < t or z < x < t < y.

Apparently the number of Dyck n-paths with more than half of the path lying between the first and last peaks. - David Scambler, Sep 14 2012

From Peter Luschny, Nov 28 2024: (Start)

A Touchard walk T(n) of length n is, as defined by Dershowitz, "a sequence of n steps, each of which is one of N/S/E/W, such that at each point along the way the number of N-steps that have been taken is never less than the number of S-steps, and are in the end equal."

There are Sum_{k=0..n} binomial(n, k) Touchard walks that have no N/S-steps at all and since by Touchard's identity T(n) = Catalan(n+1), it follows that a(n) = T(n-1) - Sum_{k=0..n-1} binomial(n-1, k) = Catalan(n) - 2^(n-1) for n >= 1. Thus a(n+1) is the number of Touchard walks of length n that have at least one N-step. (End)