Number of ways to permute a string of all numbers 1-n such that the string can be separated into two ascending strings

Question

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!)

Answer 1

Building on @Evargalo comments, let $f(n,k)$ be the number of sequences of length $n$ where $n$ appears in position $k$.

We have:

• $f(1,1)=1$ as the starting case, the sequence $1$
• $f(n,k)=0$ when $k > n$ as $n$ must appear in one of the $n$ positions.
• $f(n,1)=1$ as the only possibility for $n$ in the first position is $n1234\ldots$. Note we can write this as $f(n,1)=\sum_{j=1}^{1} f(n-1,j)$ when $n \gt 1$
• $f(n,n) = \sum_{j=1}^{n-1} f(n-1,j)$ since we simply stick $n$ into position $n$ on the far end of any sequence of length $n-1$. Note we can write this as $f(n,n)=\sum_{j=1}^{n} f(n-1,j)$ since $f(n-1,n)=0$
• $f(n,k) = \left(\sum_{j=1}^{k-1} f(n-1,j)\right) + f(n-1,k)$ when $1 \lt k \lt n$ since we can put $n$ into position $k$ either by inserting it between positions $k-1$ and $k$ of a sequence of length $n-1$ when $n-1$ is in any of the first $k-1$ positions, or by taking a sequence of length $n-1$ when $n-1$ is position $k$ and replacing $n-1$ in position $k$ by $n$ and putting $n-1$ at the far end in position $n$. Note we can write this as $f(n,j)=\sum_{j=1}^{k} f(n-1,j)$

So this can be reduced to

• $f(1,1)=1$ as the starting case
• $f(n,k)=0$ when $k > n$
• $f(n,k)=\sum_{j=1}^{k} f(n-1,j)$ otherwise

which the recurrence for a shifted version of the Catalan triangle where $f(n,k)= \frac{(n+k-2)!(n-k+1)}{(k-1)!n!}$ can be shown by induction and looks like something like this

      k 1   2   3   4   5   6
n                           
1       1   0   0   0   0   0
2       1   1   0   0   0   0
3       1   2   2   0   0   0
4       1   3   5   5   0   0
5       1   4   9   14  14  0
6       1   5   14  28  42  42

You are actually interested in summing across $k$, i.e. $\sum_{k=1}^{n} f(n,k)$, which gives you $5$ for the third row and $14$ for the fourth row as expected, and this is equal to $f(n+1,n) = \frac{(2n-1)!\times 2}{(n-1)!(n+1)!}=\binom{2n}{n}/(n+1) $ which is the $n$th Catalan number, as Evargalo identified