The number of permutations $p$ of {1,2,3,4,5,6,7,8,9} such that $p_1p_3, p_3p_6, p_6How could I count the number of permutations $ p=p_1p_2p_3p_4p_5p_6p_7p_8p_9 $ of {1,2,3,4,5,6,7,8,9} such that $p_1<p_2, p_2>p_3, p_3<p_4<p_5, p_5>p_6, p_6<p_7<p_8<p_9$ ? I need some hints.
I tried counting them all by hand by counting the cases for $p_1 = 1,2,3, ... 8 $ (It can't be 9, obviously). But it takes a long time and it's hard to check for mistakes, so I was curious whether there is a shorter/simpler method. I also thought there could be a method of drawing a graph (ascending six times and descending twice at the appropriate positions), but couldn't finalize it. Thanks for your help!
 A: This question is actually not very difficult with the help of a really nice formula. I mean, I think it's definitely easier than "counting all possibilities" for starters. Let me first define all the terminology.
Given a permutation of $[n] = \{1,2,...,n\}$ , call it $\sigma \in S_n$, the descent set of $\sigma$ is defined as $D(\sigma) = \{1 \leq i \leq n-1 : \sigma(i) > \sigma(i+1)\}$  i.e. the points where $\sigma$ experiences a descent.
If you notice, you want to count permutations $\sigma \in S_9$ such that the descent set of $\sigma$ is exactly $\{2,5\}$. How can one count permutations which have the same descent set? Here is a good recursive idea. The answer comes from this document that also contains some very good details on algorithmically generating such a permutation at random, and a generating function for the number of such permutations.

I'll state the theorem first :

Fix $N \geq 2$ and a $A \subset [1,N-1]$. Let $Q_N(A)$ be the number of permutations $\sigma \in S_N$ with descent set $A$. Then, $Q_N(A)$ can be computed as follows : define a descending sequence of polynomials :
$$
f_N = 1 \quad ; \quad f_i(x) = \begin{cases} \int_0^x f_{i+1}(y)dy & i \in A \\ \int_x^1 f_{i+1}(y)dy  & i \notin A\end{cases}
$$
Then $Q_N(A) = N! \int_0^1 f_1(y)dy$.

Let's first apply this result to our problem. Prior to that, we observe something nice which comes because $8$ is not in $\{2,5\}$ and hence allows the base case to pass through. I'll leave the exercise for induction, but you'll see why it's true as soon as I write some details below.

In the given case, every $f_i(x)$ is of the form $p(x) + C(x-1)^{n-i}$ for some polynomial $p$ of degree at most $n-i$, and constant $C$ that will be the reciprocal of an integer. We  have $f_8 = 0 + (-1)(x-1)^{1}$ to start with.


Let's make the description precise now! Write $f_i(x) = p_i(x) + C_i(x-1)^{n-i}$ for $i \leq 8$. Then we know that if $i-1 \in A$ then :
$$
\int_0^x f_i(t)dt = \int_0^x p_i(t)dt - \frac{C_i(-1)^{n-i+1}}{n-i+1}  + \frac{C_i}{n-i+1}(x-1)^{n-i+1}
$$
So $p_{i-1}(x) = \int_0^x p_i(t)dt - \frac{C_i(-1)^{n-i+1}}{n-i+1}$ and $C_{i-1} = \frac{C_i}{n-i+1}$. On the other hand , if $i-1 \notin A$, then :
$$
\int_x^1 f_{i}(t)dt = \int_x^1 p_i(t)dt - \frac{C_i}{n-i+1} (x-1)^{n-i+1}
$$
so we get $p_{i-1}(x) = \int_x^1 p_i(t)dt$ and $C_{i-1} = -\frac{C_i}{n-i+1}$. Using this, we can now track the polynomials we wish to track. We'll use a table.




$i$
$p_i$
$C_i$




$8$
$0$
$-1$


$7$
$0$
$\frac 12$


$6$
$0$
$-\frac 1{6}$


$5$
$\frac{1}{24}$
$-\frac{1}{24}$


$4$
$\frac{1-x}{24}$
$\frac{1}{120}$


$3$
$\frac{(1-x)^2}{48}$
$\frac{-1}{720}$


$2$
$-\frac{(1-x)^3}{144} + \frac{17}{2520}$
$\frac {-1}{5040}$


$1$
$-\frac{(1-x)^4}{576} +\frac{17}{2520}(1-x)$
$\frac {1}{40320}$




Great! Nothing too complicated thus far (Note : you can use factorials to express the $C_i$, in case you haven't realized. This is why the above computation looks more difficult than it actually is). Now the final answer is $ 9 ! \times\left[\int_0^1 p_1(t)dt + \frac{C_1}{n}\right] = 1099$ (Note that the integration from $0$ to $1$ isn't too hard because everything actually vanishes at $1$, so the hard work is just taking the LCM and so on).
Having said that, you can see that even following integration, there's no more than three to four terms, and at most the fifth power of $x-1$ is involved in the integration. This makes the method particularly appealing if , for example you want to calculate the number of such permutations with a very small descent set.

Now for the proof of the proposition. The document's proof is excellent and I'll summarize it : it produces the functions $f_i$ as conditional densities, and is therefore able to extract the answer as a direct consequence of the random generation, so direct that I probably won't talk about it.
Indeed, it proposes the following algorithm for generation of a  uniformly random tuple : Begin with iid $U_1,...,U_N \in U[0,1]$ and the functions $f_i$ derived as above. We define a real (random) tuple $(Y_1,...,Y_N) \in [0,1]^N$ by that tuple uniquely satisfying $\int_0^{Y_1} f_1(y)dy = U_1\int_0^1 f_1(y)dy$ and $f_i(Y_{i+1}) = U_if_{i}(Y_i)$ for all $i>1$. Then generate $\sigma$ from $Y$ by replacing every entry by it's "rank", the largest one getting $n$ and the smallest one getting $1$.
To see why this works briefly, you need to realize that the way the $Y_i$ are constructed, they work as "conditional" indicators. For example, the rank of $Y_1$ alone, can be seen to be the distribution of $\sigma(1)$ conditioned on the fact that the descent set is $A$. Then the rank of $Y_2$ alone can be proved to be the distribution of $\sigma(2)$ conditioned on the descent set being $A$, and $\sigma(1)$ being fixed. It goes all the way up to $N$, where all coordinates have now been distributed ensuring that the descent set is intact.
If you want a better way to understand this result : try and associate each permutation with the descent set $A$ with the set $\{(x_1,...,x_n) \in [0,1]^n : x_i > x_{i+1} \iff i \in A\}$ and see how the connection between the sets is quite natural (like the continuous analogue of a discrete phenomena) and how the area of the latter set is calculated : see why the "conditional" indicators come into play as well.
