Take the 2-minute tour ×

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

share|improve this question
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer


