Crossings and nestings

Consider the permutation {2, 10, 1, 8, 9, 4, 6, 3, 5, 7}.

It can be decomposed in 4 "runs" of ascending values:

• 2, 10
• 1, 8, 9
• 4, 6
• 3, 5, 7

Let's draw the following graph:

• 10 nodes (1 to 10)
• we join by an edge each consecutive node in the same run.

We get the following graph:

We count how many times edges are crossing: 3 (blue dots)

• [1,8] crosses [2,10]
• [3,5] crosses [4,7]
• [4,6] crosses [5,7]

We count how many egdes are nested below an other one: 7 (green lines)

• [3,5] nested below [2,10]
• [3,5] nested below [1,8]
• [4,6] nested below [2,10]
• [4,6] nested below [1,8]
• [5,7] nested below [2,10]
• [5,7] nested below [1,8]
• [8,9] nested below [1,10]

• Among all the permutations of {1,2,...,10} how many have exactly 4 crossings and 8 nestings?
• What is the latest in lexicographic order?

Answer format: count/permutation (as comma separated list)

Example: 99/1,2,3


[My timing: 20 sec]