Does the following object have such property?

Let $S_n$ denote the set of bijections on the set $M = \{1, 2, ... , n\}$. Suppose that a set $\Omega \subset S_n$ satisfies the following condition: there is $k \leq n$ such that, for each nonempty subset $A \subset M$ with $|A| \leq k$ and each $a \in A$ there exist exactly $\frac{|\Omega|}{|A|}$ permutations $\pi \in \Omega$ for which $\min_{x \in A} \pi (x) = \pi (a)$. Is it true, that for every nonempty subset $A \subset M$ with $|A| \leq k$ and every $m \in \{1, 2, ... |A|\}$ there exist exactly $\frac{|\Omega|}{|A|}$ permutations $\pi \in \Omega$ such that $\pi (a)$ is the $m$-th largest element of $\pi (A)$?

For small $n$-s the statement seems to be true. However, I have no idea how to prove it in general.

Any help will be appreciated.

Solution 1:

The answer is affirmative. Use induction, say, on $m$. By assumption, the statement holds for $m=1$.

Denote for $\pi \in S_n$, $A\subset[n]$, $a\in A$ by $\nu_\pi(A,a)$ the rank of $\pi(a)$ among $\pi(x), x\in A$. Then $$ N(A,a,m) = \sum_{\pi\in\Omega}\mathbf{1}_{\nu_\pi(A,a)=m} $$ is the quantity we are interested in.

If $m = |A|$, then by induction hypothesis $$ N(A,a,m) = |\Omega| - \sum_{i=1}^{m-1} N(A,a,i) = |\Omega| - \sum_{i=1}^{m-1} \frac{|\Omega|}{|A|} = \frac{|\Omega|}{|A|}. $$

Otherwise, if $2\le m<|A|$, write by induction hypothesis $$ |\Omega| = (|A|-1)\cdot\frac{|\Omega|}{|A|-1} = \sum_{b\in A\setminus \{a\}} N(A\setminus \{b\},a,m-1)\\ = \sum_{b\in A\setminus \{a\}} \sum_{\pi\in\Omega}\mathbf{1}_{\nu_\pi(A\setminus\{b\},a)=m-1} = \sum_{\pi\in\Omega}\sum_{b\in A\setminus \{a\}}\mathbf{1}_{\nu_\pi(A\setminus\{b\},a)=m-1}. $$ Note that if $\nu_\pi(A\setminus\{b\},a)=m-1$, then either $\pi(b)>\pi (a)$ and $\nu_\pi(A,a)=m-1$ or $\pi(b)<\pi(a)$ and $\nu_\pi(A,a)=m$. Therefore, using the induction hypothesis, $$ |\Omega| = \sum_{\pi \in |\Omega|} \mathbf{1}_{\nu_\pi(A,a)=m-1} \sum_{b\in A:\pi(b)>\pi(a) }1 + \sum_{\pi \in |\Omega|} \mathbf{1}_{\nu_\pi(A,a)=m } \sum_{b\in A:\pi(b)<\pi(a) }1 \\ = \sum_{\pi \in |\Omega|} \mathbf{1}_{\nu_\pi(A,a)=m-1} (|A|-m + 1) + \sum_{\pi \in |\Omega|} \mathbf{1}_{\nu_\pi(A,a)=m }(m-1)\\ = (|A|-m + 1) N(A,a,m-1) + (m-1) N(A,a,m)\\ = (|A|-m + 1) \frac{|\Omega|}{|A|} + (m-1) N(A,a,m). $$ Hence, $$ N(A,a,m) = \frac{|\Omega|}{|A|}, $$ as required.