The number of permutations with descents at specified positions $1 \leq a_1 < a_2 < \cdots < a_m \leq n-1$

Question

(a) We say that a permutation $\sigma$ of $[n]$ has a descent at position $i$ if $\sigma(i) > \sigma(i+1)$. Let $a_1,\dotsc,a_m$ be integers, with $1 \leq a_1 \lt \dotso \lt a_m \leq n-1$. Use inclusion-exclusion to show that the number of permutations of $\{ 1, 2, \ldots, n \}$ with descents at positions $a_1, \dotsc, a_m$ (and nowhere else) is $$ \sum_{\scriptstyle{j \geq 0}\atop{\scriptstyle1 \leq i_1 \lt \cdots \lt i_j \leq m}} (-1)^{m-j} \frac{n!}{\prod \limits_{\ell=1}^{j+1} (a_{i_\ell} - a_{i_{\ell -1}})!} . $$ where, by convention, $a_{i_0} = 0$ and $a_{i_{j+1}}=n$ in the summation.

(b) Let $(A_{ij})_{i,j = 0, \ldots, m}$ be the matrix $$ A_{ij} = \begin{cases} \frac{1}{(a_{j+1} - a_i)!} &\text{if } j+1 \geq i, \\ 0, &\text{otherwise}, \end{cases} $$ where $a_0=0$ and $a_{m+1}=n$. Prove that the summation in part (a) is equal to $n! \, \det A$.

Can you give me some hints?

Answer 1

For the first question: Imagine the given descent positions dividing the permutation into ascending stretches. Each stretch must be ordered in ascending order, so there's no freedom of choice within each stretch. In how many ways can you distribute the numbers to be permuted over the stretches? That counts the number of permutations that have descents at most at the given positions, but we only want the ones that have descents at exactly the given positions. So we have to subtract the ones that have descents at most at any of the subsets obtained by removing one descent position. And so on...

For the second question, it may help to visualize the matrix. Let's put $b_{kl}=1/(a_l-a_k)!$. Then

$$A=\pmatrix{ b_{01}&b_{02}&b_{03}&\ldots&&b_{0,m+1}\\ 1&b_{12}&b_{13}&\ldots&&b_{1,m+1}\\ &1&b_{23}&\ldots&&b_{2,m+1}\\ &&1&\ldots&&b_{3,m+1}\\ &&&\ddots&&\vdots\\ &&&&1&b_{m,m+1} }\;$$

with zeros below the subdiagonal ones. Now recall that the determinant is the sum of all (signed) products you can form with one factor from each row and column. Starting at the left and going right, in each column you have the choice to either pick a $1$ or one of the $b_{kl}$. But when you first pick one of the $b_{kl}$, it has to be in the first row, since you've picked $1$s in all the other non-zero rows. Now you've used up all the rows up to the diagonal, and when you go on towards the right, you're in the same situation again: you can pick any number of $1$s, but when you pick one of the $b_{kl}$ again, it has to be in the first row that was left, so its first index must be the second index of the previous one. Thus, overall, you can form a product of any number of the $b_{kl}$ in different rows and columns, with the constraint that their indices form a chain. Now you just have to do some bookkeeping to get the signs right and check the boundary cases to see that the resulting sum is the one given in the first part of the question (except for the factor $n!$).

If you want to do this more rigorously, you can formulate it as a proof by induction.