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!