cp's OEIS Frontend

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

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.

First differs from A326255 in lacking 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 nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x < z and t < y or z < x and y < t. This is a stronger condition than capturing, so for example {{1,3,5},{2,4}} is capturing but not nesting.

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

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.

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.

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 weakly nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x <= z and t <= y or z <= x and y <= t.

From Emeric Deutsch, Aug 21 2008: (Start)

Number of Dyck paths of height at least 4 and of semilength n. Example: a(5)=8 because we have UUUUUDDDDD, UUUUDUDDDD, UUUDUUDDDD, UUDUUUDDDD, UDUUUUDDDD and the reflection of the last three in a vertical axis.

Number of ordered trees of height at least 4 and having n edges. (End)

From Gus Wiseman, Jun 22 2019: (Start)

Also the number of non-crossing, capturing set partitions of {1..n}. 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 and y > t or x > z and y < t. Capturing is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting. The a(4) = 1 and a(5) = 8 non-crossing, capturing set partitions are:

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

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

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

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

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

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

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

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

(End)

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.