4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If you have a solution for $1...n$ with $n$ not in the last spot, then the integer $(n+1)$ can be included in that sequence at any point after $n$ in the first sequence. For instance from your solution for $1...8$: 13724856, we get three solutions for $1...9$: 137248569, 137248596 and 137248956. The extra solutions when $n$ is in the last spot seem to be twice as numerous as the solutions for $1...n-1$. That way we get all solutions for $1...n+1$ once and only once, but counting them is another story. $\endgroup$ – Evargalo Jul 7 '17 at 7:42
  • 1
    $\begingroup$ Another way to formulate the problem is : Find every permutation of $\{1,...,n\}$ s.t. no triplet of integers appears in reverse order. Not sure if that helps. $\endgroup$ – Evargalo Jul 7 '17 at 7:50
  • 3
    $\begingroup$ Your intuition was correct: the solution is given by Catalan numbers: en.wikipedia.org/wiki/Stack-sortable_permutation $\endgroup$ – Evargalo Jul 7 '17 at 7:56
  • 1
    $\begingroup$ @Evargalo: I think your first comment describes something else. With your rule you could not get from $213$ to $2143$ but the latter can be split into $24$ and $13$ $\endgroup$ – Henry Jul 7 '17 at 8:05
  • 1
    $\begingroup$ @Henry : My rule was "with $n$ not in the last spot". ;o). With $n$ in the last spot, I would need to look if $n-1$ is just before, then $n-2$ just before it, etc; $n+1$ can go as far back as all numbers after it are the biggest ones, ranged in ascending order - not easy to enumerate, right. $\endgroup$ – Evargalo Jul 7 '17 at 8:10
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.