The problem is to find how many permutations of length n consisting of all numbers 1-n are able to be separated into two ascending strings. One example would be 13724856, which could be separated into '1378' and '2456'.
I had listed out all cases for n=3 and n=4, for which I got 5 and 14 permutations respectively, so I'm thinking it follows the Catalan sequence but I've not been able to prove it yet.
One thought was to try and separate it into two smaller cases to try and get the summation form of the Catalan sequence but that didn't lead me anywhere. Something else I thought of trying was to find the permutations of n-k and k strings, then use nCr(n-k, k) to calculate the number of ways, but some strings can be sorted multiple ways.
Then I tried a bijective proof with another Catalan problem where you have to order n '(' and n ')' with the number of ')' never exceeding the number of '(' at any point, but it doesn't seem to follow the same pattern as this so I'm at a wall. Maybe these don't follow the Catalan sequence but I'm fairly certain that they do.
For anyone wanting the n=3 and n=4 cases:
123, 132, 213, 231, 312
1234, 1243, 1324, 1342, 1423, 2134, 2143, 2341, 2314, 2413, 3412, 3142, 3124, 4123
preemptive thanks for your help and sorry if the formatting is wonky (mobile!)