Orderly permutations with sets

Question

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}$}|

Answer 1

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<b \text{ for every } a \in A_1, b \in B_1.$ 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?

Answer 2

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]$.