6
$\begingroup$

I need help with the following:

Define a descent of a permutation to be $j$ when $p_{j+1} < p_j$. Then the descent set of a permutation is the set of all descents. For example, the $5$-permutation: \begin{equation} 4, 3, 1, 5, 2 \end{equation}

has descent set $D=\{1, 2, 4\}$

How many $9$-permutations have descent sets $D$ such that $D$ is a subset of $\{1,4,7\}$?

I cannot think of any way to enumerate a result so I started thinking of inclusion exclusion, however I feel like this approach is the same in terms of complexity because finding the descent sets that are not subsets is just as hard. By complexity I mean figuring it out.

EDIT I am looking for a concrete answer now. For example, say we have $2$-descents between elements $1$ and $2$ and elements $5$ and $6$. A solution I have seen says that the quantity given by ${8 \choose 1}\cdot{7\choose 4}\cdot {3\choose 3}$ tells us the number of subsets with descent set $=\{1 5\}$. That is the two descents happen between indices $1$ and $2$ and $5$ and $6$.

What does the quantity mean though? I see we are "choosing" numbers between the indices of the descents but I still cannot piece enough reasoning together to convince myself that this is correct. I am now multiplying these numbers together because I do see that these steps are independent.

Thanks, and all help is greatly appreciated!

| cite | improve this question | | | | |
$\endgroup$
4
$\begingroup$

It's the same as asking for the number of permutations with $$p_2\lt p_3\lt p_4,\quad p_5\lt p_6\lt p_7,\quad{\rm and}\quad p_8\lt p_9$$ So, given a random permutation, what is the probability of $p_2\lt p_3\lt p_4$? Is it independent of the probability of $p_5\lt p_6\lt p_7$? and so on....

EDIT: There are $9!$ permutations of $1,\dots,9$. Pick any one of these, call it Joe. How many of the $9!$ agree with Joe except, possibly, at positions 2, 3, and 4? Well, that's the number of permutations of the numbers at those $3$ positions, so it's $3!$. Of those $3!$, how many have no descent at positions 2, 3, and 4? Only one, the one that has $p_2\lt p_3\lt p_4$. So, we have to divide the $9!$ total permutations by $3!$ to get the number with no descent at 2, 3, and 4. Similarly, we have to divide again by $3!$ to get the number with no descent at 5, 6, and 7, and by $2!$ to get the ones with no descent at 8 or 9. So we come up with $${9!\over3!3!2!}$$ This is basically the same reasoning as in Michael's answer, without using the vocabulary of group theory.

I don't see how to get the result in the comment for $9$-permutations with descent set $\{{1,5\}}$. I get $9!/(4!4!)=630$, where your formula gives $280$.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Can you give a more concrete explanation without probability? For example, say we have $2$-descents between elements $1$ and $2$ and elements $5$ and $6$. I solution I have seen says that the quantity given by ${8 \choose 1}\cdot{7\choose 4}\cdot {3\choose 3}$ tells us the number of subsets with descent set $=\{1 5\}$. That is the two descents happen between indices $1$ and $2$ and $5$ and $6$. What does the quantity mean though? I cannot piece enough reasoning together. I am multiplying these numbers together because I caught your independence reasoning. $\endgroup$ – CodeKingPlusPlus Feb 27 '13 at 0:34
1
$\begingroup$

Here's a hint if you know some group theory:

Consider the subgroup $H = S_1 \times S_3 \times S_3 \times S_2$ that permutes the sets $\{1\}$, $\{2,3,4\}$, $\{5,6,7\}$ and $\{8,9\}$ individually (but elements of $H$ aren't allowed to send numbers from one of these sets to another). Then $H$ acts on $S_9$ on the right and each coset in $S_9 / H$ has a unique representative whose descent set is contained in $D = \{1, 4, 7\}$. (Why? Remember that multiplying one permutation by another permutation on the right has the effect of shuffling the positions of the original permutation.)

Thus, the number of permutations you seek is equal to the number of cosets in $S_9 / H$, so it equals $|S_9| / |H| = 9! / (3! 3! 2!) = 5040$.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ This leads to the same numbers as my answer of 17 Feb, but I wonder if we aren't both wrong. Let's take permutations of $\{{1,2,3,4,5\}}$ with descent set $\{{3\}}$. I think our reasoning gives $5!/(2!3!)=10$, but I only find $9$; 12435, 12534, 13425, 13524, 14523, 23415, 23514, 24513, 34512. $\endgroup$ – Gerry Myerson Feb 27 '13 at 2:50
  • $\begingroup$ @GerryMyerson: I believe the question asked for the descent set to be a subset of $D$ (= $\{3\}$ in your example). So the missing permutation is the identity $12345$. :) If you want exactly a specific descent set $D$, I think you might be stuck relying on inclusion-exclusion. $\endgroup$ – Michael Joyce Feb 27 '13 at 4:31
  • $\begingroup$ You're right --- I missed the word "subset". Good, that probably means my answer was OK, too. $\endgroup$ – Gerry Myerson Feb 27 '13 at 5:24

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.