How many arrangements of the digits 1,2,3, ... ,9 have this property? How many arrangements of the digits 1,2,3, ... ,9 have the property that every digit (except the first) is no more than 3 greater than the previous digit? 
(For example, the arrangement 214369578 has this property. However, 312548697 does not have the property, since 8 occurs immediately after 4, and 8>4+3.)
EDIT: I think this problem should have catalan numbers involved, since this was part of some homework and other similar questions involved them.

Let $a_n$ denote the number of legal arrangements of the digits $1$ through $n$.
For $n>4$, given a legal arrangement of the first $n-1$ digits, we can create a legal arrangement of the first $n$ digits by inserting the digit $n$ directly after $n-1$, $n-2$, or $n-3$, or at the beginning; these four positions are the only legal ones.
Conversely, removing $n$ from a legal arrangement of $1$ through $n$ leaves a legal arrangement of $1$ through $n-1$. Therefore, we have the recurrence
$$a_n = 4a_{n-1}\quad\text{if }n>4.$$
This easily yields the closed form
$$a_n = 24\cdot 4^{n-4}\quad\text{for all }n>4;$$
in particular, $a_9 = 24\cdot 4^5 = 3\cdot 2^{13} = \boxed{24576.}$
(Solution derived from AoPS)
