Number of permutations such that each number is either greater than all the numbers to its left or less than all the numbers to its right.

Question

I've been stuck on the following problem which I've been trying to do recursively.

Let n be a positive integer. Consider all permutations of $\{1, 2, \dots , n \}$. Let $A_n$ denote the set of those permutations such that each number is either greater than all of the numbers to its left or less than all of the numbers to its right. Let $B_n$ denote the set of those permutations $a_1,\dots a_n$ such that for $1 \leq i \leq n-1$, there is a $j > i$ with $|a_j -a_i| = 1$. Show that $|A_n| = |B_n|$.

I've been trying to do this recursively by showing there's the same recursion on $|A_n|$ and $|B_n|$ but I haven't been able to go anywhere. My first thought was that $|A_n| = n|A_{n-1}|$ because $n$ can be in any position of the permutation; $n$ can be in any position because it's always greater than the elements to it's left. But this recursion would lead to $|A_n| = n!$ which is clearly not true. However I don't see what I'm missing here, so any help would be appreciated.

Answer 1

Only half an answer but too long for a comment.

$|A|=2^n-n$

A “good” permutation is a set of numbers you select, written in ascending order, followed by the numbers you didn’t select, also in ascending order.

Each number selection corresponds to a unique good permutation except that selections $\{\}$, 1, 12, 123, etc all correspond to the same permutation (the super-good one, where everything is in one ascending sequence).

Selectedness is a yes-or-no decision, so there are $2^n$ possible selections. The supergood permutation corresponds to $n+1$ selections, so we have to subtract $n$ from this total.

You can verify this by hand for values of $n$ from 4 down to 1. Or even 0 if you want.

Answer 2

I couldn't make this any cleaner. Let $\sigma$ be a permutation on $\{1,\ldots,n\}$. There exist unique intervals $I_1,\ldots,I_t$ such that $\max I_i<\min I_{i+1}$ for all $1\leqslant i<t$, $\sigma|_{I_i}$ is increasing, and $\sigma(\max I_i)>\sigma(\min I_{i+1})$ for all $1\leqslant i<t$. That is, we partition $\{1,\ldots, n\}$ into the maximum intervals on which it's increasing.

For subsets $R,S$ of $\{1,\ldots,n\}$, we let $R<S$ denote the relation that $r<s$ for all $r\in R$ and $s\in S$.

When we describe a $\sigma$, it is sufficient to provide the ranges $\sigma(I_1)$, $\sigma(I_2)$, $\ldots$, $\sigma(I_t)$, because we know that $\sigma$ maps $I_i$ to $\sigma(I_i)$ in a strictly increasing way. So in order to define a $\sigma$, it is necessary and sufficient to provide a partition $C_1,\ldots, C_t$ of $\{1,\ldots,n\}$. This determines a $\sigma$ by letting $I_1,\ldots, I_t$ be the interval partition of $\{1,\ldots,n\}$ such that $I_1<\ldots<I_t$ and $|I_i|=|C_i|$. Then $\sigma$ maps $I_i$ to $C_i$ in a strictly increasing way.

There is one permutation with $t=1$ increasing interval $I_1$, the identity permutation, which is good.

As was mentioned in the other answer, there are $2^n-(n+1)$ good permutations which have two increasing intervals. These are obtained by choosing a subset $A$ of $\{1,\ldots, n\}$ to be the range $\sigma(I_1)$, and then $\{1,\ldots, n\}$ is forced to be the range $\sigma(I_2)$. However, $n+1$ choices of $A$ are actually re-counting the $t=1$ permutation above. These are $A=\varnothing,\{1\},\{1,2\},\ldots, \{1,2,\ldots,n\}$.

Let's consider $t>2$. Let $I_1,\ldots, I_t$ be the intervals of increase of a good permutation $\sigma$. Let $P=\sigma(I_1)$ be the range of the first interval and let $Q=\sigma(I_t)$ be the range of the last interval. Let $p=\max P$ and $q=\min Q$.

It must be the case that $P\cup Q$ is an interval and there exist $A_1<\ldots <A_m<Q$ and $P<B_m<\ldots<B_1$ such that $P,Q,A_1,\ldots,A_m,B_1,\ldots,B_m$ forms a partition of $\{1,\ldots, n\}$ and the ranges $\sigma(I_1),\sigma(I_2),\ldots, \sigma(I_t)$ are, in order, $P,A_1\cup B_1,A_2\cup B_2,\ldots, A_m\cup B_m,Q$. Every member of $P$ is greater than the entries to the left (because it is the first interval of increase), every member of $Q$ is less than the entries to the right of it (because it is the last interval of increase), every member of $A_i$ is less than the entries to the right of it (because those are either other members of $A_i$ to the right (which are good because $A_i$ is an interval of increase), or members of $A_{i+1},B_{i+1},\ldots, A_m,B_m,Q$, all of which are greater than every member of $A_i$. Every member of every $B_i$ is greater than every entry to the right for similar reasons.

We've sketched how we know that any such $\sigma$ is good. I'm going to omit the details that any good $\sigma$ must be of this form.