How many arrangements of the digits $1,2,3, ... ,9$ have this property?

Question

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\gt 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.

Answer 1

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.

Answer 2

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.}$

Answer 3

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)