Cuántos arreglos de los números 1,2,3, ... ,9 tienen esta propiedad?

Question

Cuántos arreglos de los números 1,2,3, ... ,9 tienen la propiedad de que cada dígito (excepto la primera) no es más que 3 mayor que el dígito anterior?

(Por ejemplo, la disposición 214369578 tiene esta propiedad. Sin embargo, 312548697 no tiene la propiedad, desde el 8 se produce inmediatamente después de 4 y 8>4+3.)

EDIT: creo que este problema debe tener catalán números involucrados, ya que esta era parte de algunas tareas y otras preguntas similares que participan de ellos.

Answer 1

Conté las permutaciones que satisface la condición deseada con un PARI-programa. El resultado es

?

z=0;for(k=1,9!,x=numtoperm(9,k);fmam=1;for(j=1,8,si(x[j+1]-x[j]>3,el fmam=0));si(ge f==1,z=z+1));print(z)

24576

Pero no tengo idea de cómo utilizar el catalán-números para obtener este resultado.

Tal vez, ayuda a que la factorización del número deseado $2^{13}*3$

Yo generalizada a las permutaciones con 5,6,... elementos y obtuvo los siguientes resultado :

?

para(l=5,10,z=0;for(k=1,l!,x=numtoperm(l,k);fmam=1;for(j=1,l-1,si(x[j+1]-x[j]>3, el fmam=0));si(fmam==1,z=z+1));print(l," ",z" a ",el 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]

Así, el número deseado parece ser $2^{2p-5}*3$ de permutaciones con p elementos.