In how many distinct ways can flocks be formed?
A problem in sheep combinatorics

Let us augment the linear extension $w$ with two auxiliary fixed labels $w_{0}=0$ and $w_{p+1}=p+1$. Then any deletable label of $w$ is located between two fixed labels $w_{i}$ and $w_{j}$, which can be selected in such a way that all the labels $w_{i+1},\ldots,w_{j-1}$ in between are deletable. If there is any $k\in(i,j)$ such that $w_{k}>w_{k+1}$, $k$ would be a descent in $w$ and $w_{k}$ and $w_{k+1}$ would be fixed according to condition $1)$ of Def. 6, contradicting the choice of $w_{i}$ and $w_{j}$. Therefore, we have $w_{i}<w_{i+1}<\ldots<w_{j-1}<w_{j}$. Every deletable element belongs to such an interval containing monotonously increasing deletable labels flanked by two fixed labels, therefore constructing $v=w\setminus D$ by deleting any deletable elements from $w$ does not remove or introduce any descents. ∎

Consider an element $d\in D$. Let us now narrow down the family of subsets $D^{i}$ into which the element $d$ may be placed. Let $j_{d}=\text{max}\left\{j\in[\,q\,]\,|\,\omega^{-1}(v_{j})<_{P}\omega^{-1}(d)\right\}$, or $j_{d}=0$ if this set is empty. In order to not violate condition $b)$, $d$ must be in some $D^{i}$ with $j_{d}\leq i$. Denote by $I_{d}=\left\{i\,|\,i\geq j_{d},\,v_{i}<d<v_{i+1}\right\}$ the set of possible choices for $i$ limited by the so far derived conditions $i\geq j_{d}$ and $v_{i}<d<v_{i+1}$. The set $I_{d}$ is nonempty: It follows from the order-preserving nature of $\omega$ that $v_{j_{d}}<d<v_{q+1}$, so there must be at least one value of $i$ with $j_{d}\leq i\leq q$ such that $v_{i}<d<v_{i+1}$. Let $i_{d}=\text{min }I_{d}$.

We will now show by reductio ad absurdum that placing $d$ into a subset other than $D^{i_{d}}$ leads to a violation of condition $c)$. (Recollect that every deletable element appears in $w$ ,,as early as possible”.) Assume that $d\in D^{i}$ with $i\in I_{d}$ and $i>i_{d}$. Then, by definition of $I_{d}$, we know that $d<v_{i_{d}+1}$. In order for $d$ to be deletable from the sequence $w$, there must be an element $e\in[\,p\,]$ such that $\omega^{-1}(e)<_{P}\omega^{-1}(d)$ and which appears in $w$ between $v_{i_{d}+1}$ and $d$. Denote by $E$ the set of such elements: $E=\left\{e\in[\,p\,]\,|\,\omega^{-1}(e)<_{P}\omega^{-1}(d),\sigma(\omega^{-1}(v_{i_{d}+1}))<\sigma(\omega^{-1}(e))<\sigma(\omega^{-1}(d))\right\}$, where $\sigma$ denotes the map $\sigma:P\rightarrow\boldsymbol{p}$, $w_{i}\mapsto i$ implied by $w$. If there is an $e\in E$ with $e\notin D$, then $e$ must appear in $v$ at some position $k$, $e\equiv v_{k}$. Since $\omega^{-1}(e)<\omega^{-1}(d)$, according to the definitions of $j_{d}$ and $i_{d}$ we find that $k\leq j_{d}\leq i_{d}$, in contradiction with the requirement that $v_{i_{d}+1}$ precede $e=v_{k}$ in $v$. Therefore, $e\in D$ and thus $E\subset D$. Consider now the element $c=\text{min }E$. It follows from $\omega^{-1}(c)<_{P}\omega^{-1}(d)$ that $c<d<v_{i_{d}+1}$. In order for $c$ to be deletable from the finished sequence $w$, there must be an element $e^{\prime}\in[\,p\,]$ such that $\omega^{-1}(e^{\prime})<_{P}\omega^{-1}(c)$ and which appears in $w$ between $v_{i_{d}+1}$ and $c$. Because of $\omega^{-1}(c)<\omega^{-1}(d)$ and since $c$ must precede $d$ in $w$, the aforementioned element $e^{\prime}$ must be in $E$, and therefore $\text{min }E=c<e^{\prime}$. At the same time, since $\omega$ is a natural labeling, $\omega^{-1}(e^{\prime})<_{P}\omega^{-1}(c)$ implies $e^{\prime}<c$. This contradiction shows that $c$ cannot be deletable from $w$, $c\notin\text{Del}_{P}(w)$. However we have found before that $c\in D$, which means that the assumption $i>i_{d}$ leads to a violation of condition $c)$. Therefore, we must have $i\leq i_{d}$. Since $i_{d}$ is defined as the minimum allowed value of $i,$ we have $i=i_{d}$.

Next, let us verify that $w$ satisfies condition $b)$. Consider two arbitrary elements $s,t\in P$ such that $s<_{P}t$. Each of their labels $\omega(s)$ and $\omega(t)$ can be in $D$ or in $[\,p\,]\setminus D$. For each case, we have to show that $\omega(s)$ precedes $\omega(t)$ in $w$.

• •

  If $\omega(s),\omega(t)\in[\,p\,]\setminus D$, then $\omega(s)\equiv v_{i}$ and $\omega(t)\equiv v_{j}$ for some $i,j\in[\,q\,]$. Since $Q$ is an induced subposet of $P$, we have $s<_{Q}t$, and therefore we know that $i<j$, i.e., $v_{i}\equiv\omega(s)$ precedes $v_{j}\equiv\omega(t)$ in $v$. Then, by construction, $\omega(s)$ precedes $\omega(t)$ also in $w$.

• •

  If $\omega(s)\in[\,p\,]\setminus D$ and $\omega(t)\in D$, then $\omega(s)\equiv v_{k}$ for some $k\in[\,q\,]$. Step 1 defines two numbers $j_{\omega(t)}$ and $i_{\omega(t)}$. Since $s<_{P}t$, $k$ is in $\left\{j\in[q]\,|\,\omega^{-1}(v_{j})<_{P}t\right\}$, and thus by Eq. (5) $k\leq j_{\omega(t)}$. From Eq. (6) it is clear that $j_{\omega(t)}\leq i_{\omega(t)}$. Consequently, the label $\omega(t)$ is assigned to $D^{i_{\omega(t)}}$ with $k\leq i_{\omega(t)}$, which means that $\omega(t)$ appears in $w$ after $\omega(s)\equiv v_{k}$.

• •

  If $\omega(s)\in D$ and $\omega(t)\in[\,p\,]\setminus D$, then $\omega(t)\equiv v_{k}$ for some $k\in[\,q\,]$. Any $v_{l}\in[\,p\,]\setminus D$ with $\omega^{-1}(v_{l})<_{P}s$ also satisfies $\omega^{-1}(v_{l})<_{P}s<_{P}t=\omega^{-1}(v_{k})$, and therefore $l<k$. Therefore, application of Step $1$ to $\omega(s)$ results in $j_{\omega(s)}<k$ and, due to the fact that $\omega(s)<\omega(t)$, we have $i_{\omega(s)}<k$. Thus, $\omega(s)$ is assigned to a $D^{i_{\omega(s)}}$ with $i_{\omega(s)}<k$, and therefore it appears in $w$ before $\omega(t)$.

• •

  If $\omega(s),\omega(t)\in D$, then for any $v_{k}$ with $\omega^{-1}(v_{k})<_{P}s$, it follows directly that $\omega^{-1}(v_{k})<_{P}t$. Therefore, in Step $1$, we find $j_{\omega(s)}\leq j_{\omega(t)}$, and as a result, in addition to $j_{\omega(s)}\leq i_{\omega(s)}$ (due to Eq. (6)) we also know that $j_{\omega(s)}\leq i_{\omega(t)}$. By construction of $j_{\omega(s)}$ and $i_{\omega(t)}$ as well as the order-preserving nature of $\omega$, we find $v_{j_{\omega(s)}}<\omega(s)<\omega(t)<v_{i_{\omega(t)}+1}$. Therefore, there must be at least one value of $i$ in the interval $j_{\omega(s)},\ldots,i_{\omega(t)}$ such that $v_{i}<\omega(s)<v_{i+1}$. It follows that $i_{\omega(s)}\leq i_{\omega(t)}$. If $i_{\omega(s)}<i_{\omega(t)}$, then obviously $\omega(s)$ appears in $w$ before $v_{i_{\omega(t)}}$, which in turn appears before $\omega(t)$. Finally, even if $i_{\omega(s)}=i_{\omega(t)}$, in Step $2$ the elements of each $D^{i}$ are inserted into the sequence $w$ in increasing order, so in any case $\omega(s)$ will be inserted before $\omega(t)$.

We have shown that the constructed sequence $w$ satisfies the condition $b)$, $w\in\mathcal{L}(P)$.

Finally let us verify that $w$ satisfies condition $c)$. Consider an element $d\in D$ which is inserted into $w$ at some position $k$, thus $d\equiv w_{k}$. We have ensured during the construction process that $w_{k-1}<d\equiv w_{k}<w_{k+1}$, therefore condition $1)$ of Def. 6 is satisfied. If $w_{j}<w_{k}$ for all $j\in(0,k)$, then condition $2a)$ of Def. 6 is satisfied and $d$ is deletable in $w$. Otherwise, the set $L=\left\{i\,|\,i<k\text{ and }w_{i}>w_{k}\right\}$ is nonempty. Let $l=\text{max }L$. It is clear that $w_{i}<w_{k}$ for all $i\in(l,k)$. Thus, if we can find a value of $j\in(l,k)$ such that $\omega^{-1}(w_{j})<_{P}\omega^{-1}(w_{k})$, then condition $2b)$ of Def. 6 is satisfied. We show below that indeed this is the case.

It follows directly from the definition of $l$ that $w_{l}>w_{k}$ and simultaneously $w_{k}>w_{l+1}$ (since $l+1\in\left(l,k\right)$); therefore $w_{l}>w_{l+1}$, and $l$ is a descent. We already have seen that condition $1)$ of Def. 6 is satisfied for all the elements of $D$; therefore $w_{l}$ and $w_{l+1}$ are not in $D$, but appear somewhere in the original sequence $v$, in the form $w_{l}\equiv v_{\tilde{l}}$ and $w_{l+1}\equiv v_{\tilde{l}+1}$ for some $\tilde{l}\in[\,q\,]$. Since $l+1<k$, during Step 1 $d$ must have been assigned to some $D^{i_{d}}$ with $\tilde{l}<i_{d}$.

Let us assume that $j_{d}<\tilde{l}$; we will see that this assumption leads to a contradiction. From $\omega^{-1}(v_{j_{d}})<_{P}\omega^{-1}(d)$ it follows that $v_{j_{d}}<d$. By construction of $\tilde{l}$, we have $d<v_{\tilde{l}}$. Therefore, if $j_{d}<\tilde{l}$, then there must be a $i\in(j_{d}-1,\tilde{l})$ such that $v_{i}<d<v_{i+1}$. Then, by definition of $i_{d}$, we would have $i_{d}\leq i<\tilde{l}$, in contradiction with $\tilde{l}<i_{d}$. Therefore, the assumption $j_{d}<\tilde{l}$ made at the beginning of this paragraph must be wrong and we have $\tilde{l}\leq j_{d}$. Since $v_{\tilde{l}}>d$, we find $\omega^{-1}(v_{\tilde{l}})\nless_{P}\omega^{-1}(d)$, and therefore (by Eq. (5)) $j_{d}\neq\tilde{l}$. This reasoning shows that $\tilde{l}<j_{d}$.