Why are the numbers of two different permutations the same?

Solution 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')$.