← Back to the home page

Nonnesting partitions

A set partition of an nn element set into blocks B1,B2,...,BkB_1, B_2, ..., B_k is nonnesting if for any 4 elements 1≤a<b<c<d≤n1 \leq a < b < c < d \leq n satisfying a,d∈Bi and b,c∈Bja, d \in B_i \text{ and }b, c \in B_j, we have i=ji = j.

They are counted by Catalan numbers.

A000108 on the OEIS

Source

Mamede: A bijection between noncrossing and nonnesting partitions of types A and B

Comments

Loading comments...