combinatorial descents finding the number of permutations with criteria

Question

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!

Answer 1

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

Answer 2

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