13
$\begingroup$

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.

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

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')$.
$\endgroup$
1
  • $\begingroup$ Nice bijection you found! $\endgroup$
    – TOM
    Mar 15 '20 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.