Número de $9-$ números de dígitos, todos los dígitos son diferentes y no nulos y no tienen dígitos consecutivos en posiciones consecutivas

Question

Estoy tratando de resolver un problema: Se nos pide que encontremos el número de $9-$ números de dígitos utilizando los dígitos de $1$ a $9$ sólo una vez. También hay una restricción más. Los dígitos consecutivos no deben colocarse uno al lado del otro.

Por ejemplo, $814953627$ es conveniente mientras que $8\mathbf{21}574936$ no lo es.

Me parece un problema difícil. $1$ y $9$ tienen un dígito consecutivo mientras que otros tienen dos. Esto dificulta un poco el problema. Así que intenté establecer una relación de recurrencia. Para $2\leq n\leq 9$ si el número de tales números es $A_n$ podemos utilizar $A_{n-1}$ . Para cada uno de estos $(n-1)-$ números de dígitos, podemos encontrar $n-2$ tal $n-$ números de dígitos. Permítanme dar un ejemplo, si $n=5$ y tenemos tal $4-$ número de dígitos, $3142$ por ejemplo, tenemos tres posiciones para colocar el dígito $5$ . Por lo tanto, $$A_n = (n-2)A_{n-1} + \cdots$$ Por supuesto, esta no es la única forma de tener una $n-$ número de dígitos. También colocamos el dígito $n$ entre dos dígitos consecutivos. De nuevo, si tomamos $n=5$ y si tenemos un inconveniente $4-$ número de dígitos $4231$ podemos colocar el dígito $5$ entre $2$ y $3$ y obtenemos una conveniente $5-$ número de dígitos $42531$ . Sin embargo, en este caso, debemos tener sólo dos dígitos colocados uno al lado del otro y uno de ellos no debe ser $n-1$ . Por lo tanto, si decimos $B_n$ el número de $n-$ números cuyos dígitos varían entre $1$ y $n$ y tiene dos y sólo dos dígitos consecutivos en posiciones consecutivas tales que los dígitos consecutivos son diferentes de $n$ entonces tenemos $$A_n = (n-2)A_{n-1} + B_{n-1}.$$ Sin embargo, necesitamos una ralación de recurrencia más para encontrar $B_{n-1}$ . No he podido encontrar todavía. ¿Qué debo hacer? Tratar de resolver utilizando un método completamente diferente o repasar $B_n$ ? Su ayuda me hace feliz en ambos casos.

Answer 1

El primer paso de cualquier problema de combinatoria enumerativa es calcular los primeros casos y luego buscar la secuencia en OEIS. Si hacemos eso aquí, encontramos A002464 :

Problema de Hertzsprung: formas de disponer n reyes no atacantes en un tablero de n X n, con 1 en cada fila y columna. También número de permutaciones de longitud n sin sucesiones ascendentes o descendentes.

No existe una fórmula especialmente agradable para $A_n$ lo que echa por tierra nuestras esperanzas de encontrar una solución especialmente agradable.

Su enfoque de encontrar $A_n$ en términos de $A_{n-1}$ y $B_{n-1}$ parece que podría llevar a la recurrencia $$A_n = (n+1)A_{n-1} - (n-2)A_{n-2} - (n-5)A_{n-3} + (n-3) A_{n-4}$$ después de mucho más trabajo. Pero la fuente original para esta recurrencia la encuentra algebraicamente, por lo que no está claro si se conoce una interpretación combinatoria.

Adoptar un enfoque de tipo inclusión-exclusión para este problema es algo más sencillo. Para ello, queremos calcular el número de $n$ -números de un dígito que al menos contengan algo de $r$ pares de dígitos consecutivos adyacentes, en $c$ "grupos". Por ejemplo, en $843256917$ Hay $r=3$ pares adyacentes en total: $(4,3)$ , $(3,2)$ y $(5,6)$ en dos grupos: $432$ y $56$ .

Podemos:

• permutar el $c$ grupos y $n-r-c$ elementos fuera de los grupos ( $n-r$ objetos en total) en $(n-r)!$ formas,
• orientar los grupos en $2^c$ formas,
• elija los tamaños de los $c$ grupos (cada uno con un tamaño de al menos $2$ , tamaño total $r+c$ ), en $\binom{r-1}{c-1}$ formas, y
• elija los tamaños de los $n-c+1$ espacios entre el elemento más grande de una agrupación y el más pequeño de la siguiente, más el inicio y el final (cada espacio al menos $0$ Tamaño total de los huecos $n-r-c$ ) en $\binom{n-r}{c}$ formas.

Esto nos da la fórmula $$A_n = n! + \sum_{r=1}^{n-1} (-1)^r (n-r)! \sum_{c=1}^r 2^c \binom{r-1}{c-1} \binom{n-r}{c}.$$

(Ver el Hilo del arte de resolver problemas para más información sobre esta fórmula).

Por último, podemos aproximar $A_n$ bastante cerca por una fórmula asintótica: hay $n-1$ pares de elementos consecutivos, que pueden ser adyacentes en una permutación aleatoria con probabilidad $\frac{2}{n-1}$ . Asumiendo la independencia (falsamente), hay un a $(1 - \frac{2}{n-1})^{n-1} \approx e^{-2}$ probabilidad de que ningún par de elementos consecutivos sea adyacente, lo que implica que $A_n \approx e^{-2} n!$ .

Answer 2

He realizado una simulación a $1,000,000$ veces ya que nadie encontró una respuesta todavía.

set.seed(123)
n = 9
samps <- 1000000
good <- 0

for (i in 1:samps){
  k <- n
  possible <- 1:n
  num <- c()
  while(k > 0){
    x <- sample(possible, 1)
    num <- c(num, x)
    possible <- possible[-1*which(possible == x)]
    k <- k - 1
  }
  fine <- T
  for (j in 1:(n-1)){
    if(abs(num[j] - num[j+1]) == 1){
      fine = F
    }
  }
  good <- good + fine
}
good/samps*factorial(9)
#48914.05

Esto es de $R$ que no es el mejor en esto pero estoy bastante seguro de que la respuesta está en el $48,900$ gama.

Editar:

He programado la permutación organizada real y la respuesta aceptada es correcta.

Aquí está el código de interés, de nuevo escrito en $R$ .

library(combinat)
a <- permn(1:9)

good <- 0
for (i in 1:length(a)){
  num <- a[[i]]
  fine <- T
  for (j in 1:(n-1)){
    if(abs(num[j] - num[j+1]) == 1){
      fine = F
    }
  }
  good <- good + fine
}
good
#47622

Debe haber un sesgo en $R$ en alguna parte.