36. [25] An ordering of a set of $n$ elements is a bijective map between the set and $\{1,2, \ldots, n\}$. Call an ordering $\rho$ of the 10 unordered pairs of distinct integers from the set $\{1,2,3,4,5\}$ admissible if, for any $1 \leq a<b<c \leq 5$, either $p(\{a, b\})<p(\{a, c\})<p(\{b, c\})$ or $p(\{b, c\})<p(\{a, c\})<p(\{a, b\})$. Find the total number of admissible orderings.
Answer: 768
This problem is a special case of the higher Bruhat order, a class of combinatorial object widely studied for its connection to an assortment of mathematical areas such as algebraic geometry, algebraic combinatorics, and computational geometry.
An admissble order in our problem - the higher Bruhat order $B(5,2)$-are best viewed as the set of reduced decompositions of the permutation 4321. Loosely speaking, a reduced decomposition is a sequence of adjacent transpositions that changes the permutation $n, n-1, \ldots, 1$ to $1,2, \ldots, n$. For example, for $n=4$, the sequence $(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$ induces the following reduced decomposition:
$$
4321 \rightarrow 4312 \rightarrow 4132 \rightarrow 1432 \rightarrow 1423 \rightarrow 1243 \rightarrow 1234 .
$$

For each permutation above, switching the two bolded numbers yields the next permutation in the chain. For example, switching 3 and 1 in 4312 yields 4132 .
Readers interested in the connection between the higher Bruhat order and reduced decompositions are referred to Delong Meng's paper "Reduced decompositions and permutation patterns generalized to the higher Bruhat order" for background as well as recent development of this subject. The paper is available at
http://web.mit.edu/delong13/www/papers.html.
The number of reduced decompositions of $n, n-1, \ldots, 1$ is equal to the number of $(n-1)$ st standard Young Tableaux of staircase shape, given by the formula
$$
\frac{\binom{n}{2}!}{1^{n-1} \cdot 3^{n-2} \cdots(2 n-3)} .
$$

When $n=5$, the formula gives 768 .
Young Tableaux are one of the most important tools in algebraic combinatorics, especially for problems involving permutations, integer partitions, and posets. For a concise and accessible introduction to the Young Tableaux and reduced decompositions (and much more cool combinatorial stuff!), see Section 7 of Richard Stanley's note "A Combinatorial Miscellany" at