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

(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?

-
how to make the image bigger? – Sunni Oct 31 '11 at 2:23
I removed the image and typed out the question. Sunni, Can you please read through the question carefully and ensure that I haven't made any mistakes in transcribing? =) – Srivatsan Oct 31 '11 at 2:44
I made a couple of changes and corrections, most importantly to the index $i$ of $a_i$ in the definition of $A_{ij}$. @Sunni, please do check that this corresponds to your original image. – joriki Oct 31 '11 at 6:48
Perfect, thanks. Next time, I shall type out question them rather than upload an image. Since two questions are there, I may want to know how question one is answered as well. – Sunni Oct 31 '11 at 12:31
Oh, I am sorry about that typo, Sunni. It's a good catch, @joriki. Thanks. – Srivatsan Oct 31 '11 at 21:29

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