About Warm-ups Problems News

Problem 36

Posted 04/08/2017
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

This problem is proposed by Dun Qiu. If you want to submit your problem, please click here.

----------------------

In this problem, we are interested in enumerating permutations in $\mathcal{S}_n$ that the $i^{\textrm{th}}$ left to right maximum appears at the $j^\mathrm{th}$ position.

We continue our definition of $\mathrm{m}_i(\pi)$ of a permutation $\pi=\pi_1\pi_2\cdots\pi_n\in\mathcal S_n$ in Problem 35.

Let $b_{n;i,j}$ be the number of permutations $\pi=\pi_1\pi_2\cdots\pi_n\in\mathcal S_n$ such that $\mathrm{m}_i(\pi)=\pi_j$. For $i=1$, $b_{n;1,j}$ is trivial. Since $\mathrm{m}_1(\pi)$ is always equal to $\pi_1$, we have $b_{n;1,1}=n!$ and $b_{n;1,j}=0$ for all $j>1$.

For $i=2$, the enumeration $b_{n;2,j}$ is no longer trivial, which can be an exercise. We also have $b_{n;i,i}=\binom{n}{i}$.


Our problem is to find a general formula for $b_{n;i,j}$.







Back to top