A beautiful problem

Let $p^{n}$ denote a permutation of $[0, 1, . ., n]$ . define $f (p^{n}, v) = p_{i}^{'} : p_{i}^{'} = p_{i} + 1 if p_{i} \geq v else p_{i}$ . We claim that $f$ is a bijection from ${p^{n}}$ to $p e r m ({0. . n} - v)$ where $v \in [0, n + 1]$ .

$f$ is surjective: let $p^{'} \in p e r m ({0. . n} - v)$ $p_{i}^{'}$ is either greater than $v$ or smaller than $v$ . as a set, this permutation $p^{'}$ is a re-arrangement of $0, 1. . v - 1, v + 1. . n + 1$ . Hence decrementing $p_{i}^{'}$ if $p_{i}^{'} > v$ results in a re-arrangement of $0, 1, . . n$ , hence $f^{- 1} (p^{n}, v) \in {p^{n}}$ .
$f$ is injective: this follows from the definition of $f$ . If $f (p^{n}, v) = f (q^{n}, v)$ it is either the case that $p_{i} = q_{i}$ or $p_{i} + 1 = q_{i} + 1$ for any $i$ .

it is important to note that if $f : A \to B$ is biijective, then $f : U \to f (U)$ is also bijective whenever $U \subset$ A.

We say that $p^{n}$ is $c$ valid (where $c = c_{0}, c_{1}, \dots c_{n - 1}$ and $c_{i} \in {↑, ↓}$ ) if for every $i$ $c_{i} =↑ ⟹ p_{i} < p_{i + 1}, c_{i} =↓ ⟹ p_{i} > p_{i + 1}$ .

$p^{n}$ is $c$ valid implies $f (p^{n}, v)$ is $c$ valid.
- if $p_{i} > p_{i + 1}$ : suppose $p_{i + 1} \geq v$ and hence $p_{i} > v$ , giving $p_{i}^{'} = p_{i} + 1 \geq p_{i + 1} + 1 = p_{i + 1}^{'}$ , or $p_{i} \geq v$ and hence $p_{i}^{'} = p_{i} + 1 > p_{i + 1} + 1 \geq p_{i + 1}^{'}$
- A similar argument can be given when $p_{i} < p_{i + 1}$ .

Now, let $P^{n}$ denote the set of all permutations of $[0, 1, . ., n]$ that are $c$ valid for a given $c$ .
define a partition $P^{n} | k = {p : p \in P^{n}, p_{n} = k}$ of those permutations in $P^{n}$ that end with $k$ , for $k \in [0, n]$ .
The following is a theorem: for $c + + c_{n}$ valid permutations $P^{n + 1}$ .

P^{n + 1} | v = {\begin{cases} ⋃_{k \geq v} f (P^{n} | k, v) + + v & if c_{n} =↓ \\ ⋃_{k < v} f (P^{n} | k, v) + + v & if c_{n} =↑ \end{cases}

where $+ +$ means concatenation, (which when applied on a set means concatenation on each element, and also $f$ is applied elementwise to a set).
To prove the theorem, at least we know that the right hand side are permutations, as $f (p, v)$ does not contain $v$ , and is a permutation, so the right hand side definitely contains permutations of $[0, . . n + 1]$ that end in $v$ .

Now we need to show that these permutations are $c + + c_{n}$ valid.