# Why are the numbers of two different permutations the same?

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.

• Neat. Have you checked it for many $k,m,n$? Mar 9 '20 at 15:59
• @Jair Taylor :Yes. manchanr6.blogspot.com/2020/03/200307.html
– TOM
Mar 9 '20 at 16:01
• Nice. My only thought is perhaps "Ehrhart-McDonald reciprocity", or some other combinatorial reciprocity theorem, could be useful somehow. Mar 9 '20 at 16:14

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

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