Permutations with inequalities constraint - analytical solution I asked here in how many ways could I arrange the first $6$ positive integers such that this inequalities chain will hold
$a < b > c < d < e > f$
The answer showed me how to use Mathematica to count  those permutations.
Now I would like to know how can I derive that answer analytically. In the case above I have $5$ inequality signs, so I can have $2^5 = 32$ different inequalities chains, and each one correspond to one of those numbers of permutations
$\{1, 5, 10, 14, 19, 26, 35, 40, 61\}$
Of course if I sum all the permutations I have a total of $6!= 720$, but I don't know how to calculate each one for a specific inequalities chain.
Edit: the answers resolve the case with alternating $<,>$ signs, but what if they in a specific, non alternating, chain?
 A: Apologies for prematurely closing your question as a duplicate. Although counting the things you want – linear extensions – for general posets is indeed hard, the special case of chained inequalities can be solved in polynomial time as detailed below.
Given the poset $x_1-x_2-\cdots-x_n$ where $-$ is $<$ or $>$, find all maximal elements. These are the only places the largest number can go. For each "peak":

*

*Delete the peak, splitting the chain into two sub-chains of lengths $k$ on the left and $n-k-1$ on the right (see picture)

*Recurse into the sub-chains and count their numbers of linear extensions – say the left and right chains have $L$ and $R$ of them

*The number of linear extensions of the whole chain with the largest number at that peak is $LR\binom{n-1}k$

Then the final answer is the sum of these counts for each peak. Because only the $O(n^2)$ continuous sub-chains are considered, memoising their extension counts leads to an $O(n^3)$ time algorithm.

For the given inequality chain $a<b>c<d<e>f$ applying the above procedure yields this evaluation tree, where $(x)$ denotes the number of linear extensions of chain $x$:

*

*(a<b>c<d<e>f) = (a)(c<d<e>f) + (a<b>c<d)(f) = 1×3×5 + 5×1×5 = 40

*

*(c<d<e>f) = (c<d)(f) = 1×1×3 = 3

*(a<b>c<d) = (a)(c<d) + (a<b>c)() = 1×1×3 + 2×1×1 = 5

*

*(a<b>c) = (a)(c) = 1×1×2 = 2
The base cases used here are total orders, which have only one linear extension.
