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.
 A: I counted the permutations satisfying the desired condition with a PARI-program.
The result is 
? 
z=0;for(k=1,9!,x=numtoperm(9,k);gef=1;for(j=1,8,if(x[j+1]-x[j]>3,gef=0));if(ge
f==1,z=z+1));print(z)
24576
But I have no idea how to use catalan-numbers to get this result.
Perhaps, it helps, that the factorization of the desired number is
$2^{13}*3$
I generalized to permutations with 5,6,... elements and got the following
result :
? 
for(l=5,10,z=0;for(k=1,l!,x=numtoperm(l,k);gef=1;for(j=1,l-1,if(x[j+1]-x[j]>3,
gef=0));if(gef==1,z=z+1));print(l,"  ",z,"   ",factor(z)))
5  96   [2, 5; 3, 1]
6  384   [2, 7; 3, 1]
7  1536   [2, 9; 3, 1]
8  6144   [2, 11; 3, 1]
9  24576   [2, 13; 3, 1]
10  98304   [2, 15; 3, 1]
So, the desired number seems to be $2^{2p-5}*3$ for permutations with p elements.
A: Let $a_n$ denote the number of valid configurations.
Note that if $n\ge 4$, $a_{n+1}=4a_n$. $a_4=4!$, so $a_9=4! \cdot 4^5=\boxed{24576.}$
A: 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)
