1
$\begingroup$

Let $[M]:=\{1,2,\dots, M\}$. (Part of the twelvefold way) as we all know, there is a bijection between surjective functions $[N] \to [B]$ and ordered set partitions of $[N]$ into $[B]$ blocks (of course $B \le N$).

There also seems to be a bijection between monotone surjective functions $[N] \to [B]$ and compositions (ordered integer partitions) of $N$ into $B$ blocks (since there is a bijection between these and contiguous set paritions of $[N]$ into $B$ blocks, e.g. $\{1\},\{2,3,4\}$ or $\{1,2\}, \{3,4\}$ for $N=4, B=2$).

Question: Are there standard terms for the operations on ordered integer partitions and/or ordered set partitions corresponding to (i) composition of functions and (ii) "function division" or "extension"?

To clarify what I mean, specifically for:

(i) given (monotone and) surjective functions $[N] \xrightarrow{P_1} [B_1]$ and $[B_1] \xrightarrow{Q} [B_2]$ (here $B_2 \le B_1 \le N$ of course), what is the term for the (ordered integer partition) ordered set partition corresponding to the (monotone and) surjective function $[N] \xrightarrow{P_2} [B_2] := [N] \xrightarrow{Q \circ P_1} [B_2]$?

(ii) given (monotone and) surjective functions $[N] \xrightarrow{P_1} [B_1]$ and $[N] \xrightarrow{P_2} [B_2]$, what is the term for the (ordered integer partition) ordered set partition corresponding to the (monotone and) surjective function $[B_1] \xrightarrow{Q} [B_2]$ such that $Q \circ P_1 = P_2$, if one exists?

For (ii), such a $Q$ exists if and only if $P_1$ is a (strong) refinement of $P_2$, in which case it is guaranteed to be unique since $P_1$ is surjective and thus an epimorphism i.e. right-cancellative. In (i) $P_1$ also refines $P_2$.

These seem like really basic operations, so I was surprised when I couldn't find them in any textbook like Stanley or Cameron. I've tried searching for papers referencing them but was not able to find anything, probably due to not using the correct terms. The only answer I got to a previous question on Math.SE was that SageMath has functions which implement both of these operations for compositions and one of them, (i), for ordered set partitions, and that (i) is a "fattening of $P_1$ using the grouping $Q$" and that (ii) are the "refinement splitting lengths" of $P_2$ with respect to $P_1$ (this being defined only when $P_1$ is finer than $P_2$ of course). However the documentation in SageMath does not give any references to sources using those terms, and searching for them on the internet I was not able to find them elsewhere, which makes me think SageMath invented them.

Are there really no more formal terms defined anywhere else besides SageMath?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy