How do you call a partition of a totally ordered set that….

combinatoricsorder-theoryset-partition

A partition of a set S is a collection P={B1,B2,…,Bk} of subset of S such that for each i, j, ∈ {1,2,…,k}:

  1. Bi ≠ ∅
  2. Bi ⋂ Bj ≠ ∅
  3. B1 ⋃ B2 ⋃…⋃ Bk = S

now if S is a totally ordered set and P is also equipped with a partial order ≼ how do you call a partition that meets the following additional condition?

for x ∈ Bi, y x ∈ Bj, if x<y then i≤j (or B i ≼ Bj)

For example if S= {1, 2, 3, 4} we can have the following partitions of S into two subsets:

1/234, 12/34 and 123/4 (but not 13/24 nor 14/23)

I've come accross the following definitions: monotone partition, consecutive partition…but I don't seem to find a commonly accepted terminology nor any body of litterature that would study these … (I know it is subset of partitions and non-crossing partitions)

Any directions, hints for me?

Many thanks

P.S: to give a bit of context, I wanted to study this type of partitions in details (their lattice structure, total number given binomials as suggested by Donald S. etc…)

Best Answer

By your p.s I think you would appreciate the following discussion.

Notice that your partitions, because there is an order inherit from the line, are completely characterize by the size of the sets. So, a partition of your interest say $\pi =\{B_1,B_2,\cdots ,B_k\}$ is such that $B_i=[x_1+\cdots +x_{i-1}+1,x_1+\cdots +x_{i-1}+x_i]\cap \mathbb{Z}$ where $x_0=0$ so the size of $|B_i|=x_i.$ in this way, the number of these partitions is $$|\{(x_1,\cdots ,x_k):\sum _{i=1}^kx_i=n,x_i>0\}|=\binom{n-1}{k-1},$$ which adds up to $2^{n-1}$ if you add over the number of parts. That is why is not very interesting to compute them and also the motivation to call them compositions.

In terms of the order structure that they inherit from the partitions you can check that the refinement looks like the Boolean lattice for $[n-1].$

Notice that a very similar concept that is very well studied is the concept of flag. The partitions that you describe are what happens to basis elements in flags of $\mathbb{R}^n.$

Related Question