Why are the numbers of two different permutations the same?

Question

Define $a(k,m,n)$ as the number of ordered sets $\sigma$ which are permutations of $\{m, m+1, \dots, m+n-1\}$, such that

$$\text{for all integers }j\text{ where }1 \leq j \leq n-1, \quad \frac{\sigma(m+j-1)}{k+j} \color{red}{>} \frac{\sigma(m+j)}{k+j+1},$$

where $\sigma(j)$ denotes the $j\text{'th}$ element of the ordered set $\sigma$.

Similalrly, define $b(k,m,n)$ as the number of $\sigma$ of $\{m, m+1,\dots, m+n-1\}$ such that

$$\text{for all integers }j\text{ where }1 \leq j \leq n-1, \quad \frac{\sigma(m+j-1)}{k+j} \color{red}{\geq} \frac{\sigma(m+j)}{k+j+1}.$$

Is the following statement true?

$$\text{For all integers }m\text{ where }0 \leq m \leq k+1,\quad a(k,m,n+1) = b(k,m,n).$$

Also, is the following true?

$$\text{For all integers }m'\text{ and }m\text{ where }0 \leq m' \leq m \leq k+1, \quad b(k,m,n) = b(k, m-m', n+m').$$

Example 1

We have $a(0,1,4) = 3$, since

$$ \frac{2}{1} > \frac{3}{2} > \frac{4}{3} > \frac{1}{4}, \\ \frac{3}{1} > \frac{4}{2} > \frac{2}{3} > \frac{1}{4}, \\ \frac{4}{1} > \frac{3}{2} > \frac{2}{3} > \frac{1}{4}. $$

We have $b(0,1,3) = 3$, since

$$ \frac{1}{1} \geq \frac{2}{2} \geq \frac{3}{3}, \\ \frac{2}{1} \geq \frac{3}{2} \geq \frac{1}{3}, \\ \frac{3}{1} \geq \frac{2}{2} \geq \frac{1}{3}. $$

So $a(0,1,4) = b(0,1,3)$.

Example 2

We have $a(1,1,4) = 2$, since

$$ \frac{3}{2} > \frac{4}{3} > \frac{2}{4} > \frac{1}{5}, \\ \frac{4}{2} > \frac{3}{3} > \frac{2}{4} > \frac{1}{5}. $$

We have $b(1,1,3) = 2$, since

$$ \frac{2}{2} \geq \frac{3}{3} \geq \frac{1}{4}, \\ \frac{3}{2} \geq \frac{2}{3} \geq \frac{1}{4}. $$

So $a(1,1,4) = b(1,1,3)$.

Example 3

We have $a(1,1,6) = 5$, since

$$ \frac{3}{2} > \frac{4}{3} > \frac{5}{4} > \frac{6}{5} > \frac{2}{6} > \frac{1}{7}, \\ \frac{4}{2} > \frac{5}{3} > \frac{6}{4} > \frac{3}{5} > \frac{2}{6} > \frac{1}{7}, \\ \frac{5}{2} > \frac{6}{3} > \frac{4}{4} > \frac{3}{5} > \frac{2}{6} > \frac{1}{7}, \\ \frac{6}{2} > \frac{4}{3} > \frac{5}{4} > \frac{3}{5} > \frac{2}{6} > \frac{1}{7}, \\ \frac{6}{2} > \frac{5}{3} > \frac{4}{4} > \frac{3}{5} > \frac{2}{6} > \frac{1}{7}. $$

We have $b(1,1,5) = 5$, since

$$ \frac{2}{2} \geq \frac{3}{3} \geq \frac{4}{4} \geq \frac{5}{5} \geq \frac{1}{6}, \\ \frac{3}{2} \geq \frac{4}{3} \geq \frac{5}{4} \geq \frac{2}{5} \geq \frac{1}{6}, \\ \frac{4}{2} \geq \frac{5}{3} \geq \frac{3}{4} \geq \frac{2}{5} \geq \frac{1}{6}, \\ \frac{5}{2} \geq \frac{3}{3} \geq \frac{4}{4} \geq \frac{2}{5} \geq \frac{1}{6}, \\ \frac{5}{2} \geq \frac{4}{3} \geq \frac{3}{4} \geq \frac{2}{5} \geq \frac{1}{6}. $$

So $a(1,1,6) = b(1,1,5)$.

Other calculation results are written here.

P.S.

Define $a(j,k,m,n)$ as the number of ordered sets $\sigma$ which are permutations of $\{m, m+1, \dots, m+n-1\}$, such that

$$\sigma(m) = j$$

$and$

$$\text{for all integers }j\text{ where }1 \leq j \leq n-1, \quad \frac{\sigma(m+j-1)}{k+j} \color{red}{>} \frac{\sigma(m+j)}{k+j+1},$$

where $\sigma(j)$ denotes the $j\text{'th}$ element of the ordered set $\sigma$.

Similalrly, define $b(j,k,m,n)$ as the number of $\sigma$ of $\{m, m+1,\dots, m+n-1\}$ such that

$$\sigma(m) = j$$

$and$

$$\text{for all integers }j\text{ where }1 \leq j \leq n-1, \quad \frac{\sigma(m+j-1)}{k+j} \color{red}{\geq} \frac{\sigma(m+j)}{k+j+1}.$$

Is the following statement true?

$$\text{For all integers }m\text{ where }0 \leq m \leq k+1,\quad a(j+1,k,m,n+1) = b(j,k,m,n).$$

Example 4

$a(2,0,1,4) = 1, a(3,0,1,4) = 1, a(4,0,1,4) = 1.$

$b(1,0,1,4) = 1, b(2,0,1,4) = 1, b(3,0,1,4) = 1.$

Example 5

$a(3,1,1,4) = 1, a(4,1,1,4) = 1.$

$b(2,1,1,4) = 1, b(3,1,1,4) = 1.$

Example 6

$a(3,1,1,6) = 1, a(4,1,1,6) = 1, a(5,1,1,6) = 1, a(6,1,1,6) = 2.$

$b(2,1,1,5) = 1, b(3,1,1,5) = 1, b(4,1,1,5) = 1, b(5,1,1,5) = 2.$

Other calculation results are written here.

Answer 1

Let $A(k,m,n), B(k,m,n)$ be the sets of permutations counted by $a(k,m,n), b(k,m,n)$ respectively.

To answer your first question, here is a bijection between $B(k,m,n)$ and $A(k,m,n+1)$. (I assume $n \ge 2$, avoiding some trivial cases.) Given $\sigma \in B(k,m,n)$, add $1$ to every element, then put $m$ last.

Let's check that this works. First, let's check that this preserves the first $n-1$ inequalities, going both ways. On one hand, if $\frac{x}{k+j} \ge \frac{y}{k+j+1}$, then we definitely have $\frac{x+1}{k+j} > \frac{y+1}{k+j+1}$, since we've increased the LHS by $\frac1{k+j}$ but the RHS by $\frac1{k+j+1}$. On the other hand, if $\frac{x+1}{k+j} > \frac{y+1}{k+j+1}$, then the slack in the inequality has to be at least $\frac1{(k+j)(k+j+1)} = \frac1{k+j} - \frac1{k+j+1}$, and therefore $\frac{x}{k+j} \ge \frac{y}{k+j+1}$.

Second, putting $m$ last in the image of $\sigma$ always satisfies the $n^{\text{th}}$ inequality. Even if the previous element is $m+1$, we still have $\frac{m+1}{k+n-1} > \frac{m}{k+n}$ if and only if $m+k+n>0$.

Lastly, every element of $A(k,m,n)$ puts $m$ last, so we don't miss any ordered sets this way. If $m$ were not last, then even if the next element of the ordered set were just $m+1$, and even if these are the two last elements of the ordered set (where the inequality is easiest to satisfy), we still can't have $\frac{m}{k+n-1} > \frac{m+1}{k+n}$. This would require $1 - k + m - n > 0$, and since $m \le k+1$ it would require $n<2$.

---

Regarding your other questions:

• The same map as above is a bijection between $B(j,k,m,n)$ and $A(j+1,k,m,n+1)$.
• The bijection between $B(k,m,n)$ and $B(k,m-1,n+1)$ is similar: we merely add $m-1$ to the end of the ordered set. We verify that this is the only place where $m-1$ can go, and that $m-1$ can always go there. From $b(k,m,n) = b(k,m-1,n+1)$ it follows that $b(k,m,n) = b(k,m-m',n+m')$.