# Orderly permutations with sets

If $$A_1, ..., A_m$$ are $$k$$ element subsets of $$\{1,2,3,...n\}$$ and $$B_1, ..., B_m$$ are $$l$$ element subsets of $$\{1,2,3,...n\}$$ with the following properties:

For all $$i \in [m]$$ there are subsets such that $$A_i \cap B_i = \emptyset$$ and if $$i, j \in [m]$$ and $$i \neq j$$, $$A_i \cap B_j \neq \emptyset$$

For all $$i \in [m]$$, a permutation in $$\mathbb{S}_n$$ is considered i-orderly is permutation($$a$$) < permutation($$b$$) for all $$a\in A_i$$ and $$b \in B_i$$.

With these constraints, prove that

|{$$i \in [m] : \text{permutation is i -orderly}$$}| $$\leq 1$$

and

for every $$i \in [m]$$ find

|{$$\text{permutation in} \mathbb{S}_n : \text{permutation is i -orderly}$$}|

Going through an example with $$n= 3$$: if $$k = 2$$ and $$l=1$$, then $$A_1, ..., A_m = \{1, 2\}, \{1, 3\}, \{2, 3\}$$ and $$B_1, ..., B_m = \{3\}, \{2\}, \{1\}$$

If we take a permutation $$\alpha$$ of {1, 2, 3} to be {2, 3, 1} And $$i$$ to be 1. Meaning: $$A_1 = \{1, 2\}$$ and $$B_1 = \{3\}$$

$$\alpha(1) = 2, \alpha(2) = 3, \alpha(3) = 1$$ In this iteration, $$\alpha$$ is not i-orderly where i = 1.

How can I prove this in a more general case? And how can I use this to compute for every $$i \in [m]$$ find

|{$$\text{permutation in} \mathbb{S}_n : \text{permutation is i -orderly}$$}|

Let $$\sigma\in\Bbb S_n$$, and suppose that $$\sigma$$ is $$i$$-orderly and $$j$$-orderly for some $$i,j\in[m]$$ such that $$i\ne j$$. By hypothesis there are $$x\in A_i\cap B_j$$ and $$y\in A_j\cap B_i$$. Then on the one hand $$\sigma(x)<\sigma(y)$$, since $$\sigma$$ is $$i$$-orderly, but on the other hand $$\sigma(y)<\sigma(x)$$, since $$\sigma$$ is $$j$$-orderly. This is clearly impossible, so $$|\{i\in [m]:\sigma\text{ is }i\text{-orderly}\}|\le 1$$.

Now let $$i\in[m]$$; $$\sigma\in\Bbb S_n$$ is $$i$$-orderly if and only if $$\max\sigma[A_i]<\min\sigma[B_i]$$. We can construct such a permutation of $$[n]$$ as follows. First, $$\sigma[A_i]\cup\sigma[B_i]$$ is a $$(k+\ell)$$-element subset of $$[n]$$, and there are $$\binom{n}{k+\ell}$$ of those. Once we’ve chosen one of those subsets to be $$\sigma[A_i]\cup\sigma[B_i]$$, the smallest $$k$$ members must be $$\sigma[A_i]$$, and the remaining $$\ell$$ members must be $$\sigma[B_i]$$. The members of $$\sigma[A_i]$$ can be permuted in any of $$k!$$ ways, and those of $$\sigma[B_i]$$ can independently be permuted in any of $$\ell!$$ ways. Thus, there are $$k!\ell!\binom{n}{k+\ell}$$ ways to choose $$\sigma\upharpoonright(A_i\cup B_i)$$

Finally, $$\sigma$$ must send $$[n]\setminus(A_i\cup B_i)$$ bijectively to $$[n]\setminus\sigma[A_i\cup B_i]$$, and it can do so in $$\big(n-(k+\ell)\big)!$$ different ways, so there are altogether

$$k!\ell!(n-k-\ell)!\binom{n}{k+\ell}=\frac{n!k!\ell!}{(k+\ell)!}$$

possibilities for $$\sigma$$. That is,

$$|\{\sigma\in\Bbb S_n:\sigma\text{ is }i\text{-orderly}\}|=\frac{n!k!\ell!}{(k+\ell)!}$$

for each $$i\in[m]$$.

You illustrate one case where the permutation is not $$i$$-orderly, but there is another where it is, if you take $$m=1$$ and $$A_1=\{1,2\}$$ and $$B_1=\{3\}$$. What about $$\pi([1,2,3]=[2,1,3]$$? That permutation is also $$i$$-orderly $$-$$ isn't it? $$-$$ because every element of $$\{2,1\}$$ is less than every element of $$\{3\}$$.

Stepping back: There are $${n\choose k}$$ subsets from which to choose $$m$$ values for the set of subsets $$A$$. There are $${n \choose l}$$ subsets from which to choose another wholly-unrelated $$m$$ values for the list $$B$$. Clearly $${n\choose k} \ne {n \choose l}$$ if $$l\ne k$$, so there is no natural definition of $$m$$. So we can take $$m$$ to be any number $$\le \min\{ {n\choose k} , {n\choose l}\}$$, right? So, $$m=1$$ is an arbitrary and valid choice by your rules, isn't it? And then we can take any $$m=1$$ element of either set of sets to compare. Furthermore, when we permute $$[n]$$, we need only take two $$i$$ orderly permutations to invalidate the conjecture that at most 1 permutation is $$i$$-orderly. OK, the table is set.

Let $$n=[6], ~k=3, ~l=2, ~m=[1], A_1=\{1,2,3\}, B_1\{4,5\}. A_1 \cap B_1 = \phi.$$ Since $$m=[1]$$ there are no other cases to consider. Clearly, $$a The initial permutation $$\pi_0[n]= 1,2,3,4,5,6$$ is $$i=1$$-orderly according to your definition of $$i$$ for $$i=1$$. But so is $$S_n=[1,2,3,\pi[4,5,6]].$$ The cardinality of the set of i-orderly permutations is easily greater than 1.

If we try to prove a theorem and end up disproving it by finding a counter example (this time very easily) then perhaps the meanings of words aren't clear. I take

For all $$i \in [m]$$, a permutation in $$S_n$$ is considered $$i$$-orderly is permutation($$a$$) < permutation($$b$$) for all $$a \in A_i$$ and $$b \in B_i.$$

to mean that the sets $$A_1=\{1,2,3\}$$ corresponds to the first three elements of the null/default permutation and $$B_1=\{4,5\}$$ corresponds to the 4th and 5th elements of the null/default permutation of $$\pi[n]$$. $$\pi_0[1,2,3,4,5,6] [4,5]=\{4,5\}$$, but under another permutation of [1,2,3,4,5,6], viz.[1,2,3,4,6,5], $$B_1 [4,5] = \pi_x[1,2,3,4,6,5][4,5]=\{4,6\}$$. So this is another, valid 1-orderly permutation for the values given, and the conjecture fails.

Am I understanding you correctly?