Question 29
A tourist is learning an incorrect way to sort a permutation $\left(p_{1}, \ldots, p_{n}\right)$ of the integers $(1, \ldots, n)$. We define a fix on two adjacent elements $p_{i}$ and $p_{i+1}$, to be an operation which swaps the two elements if $p_{i}\gt p_{i+1}$, and does nothing otherwise. The tourist performs $n-1$ rounds of fixes, numbered $a=1,2, \ldots, n-1$. In round $a$ of fixes, the tourist fixes $p_{a}$ and $p_{a+1}$, then $p_{a+1}$ and $p_{a+2}$, and so on, up to $p_{n-1}$ and $p_{n}$. In this process, there are $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$ total fixes performed. How many permutations of $(1, \ldots, 2018)$ can the tourist start with to obtain $(1, \ldots, 2018)$ after performing these steps?