Problema de combinatoria en el conteo.

Question

¿Cuántos enteros positivos n hay de tal manera que todo lo siguiente tenga lugar:

1) n tiene 1000 dígitos.

2) todos los dígitos son impares.

3) el valor absoluto de la diferencia de dos dígitos consecutivos (vecinos) es igual a 2.

Por favor ayuda. Ni siquiera sé cómo empezar.

Answer 1

El texto era demasiado largo para un comentario y objetivos en la finalización de las anteriores respuestas y comentarios, que se reducen a una muy simple la respuesta final para $n\ge2$: $$a_n=\begin{cases}\hphantom18\cdot 3^{\frac{n-2}2},& n\text{ even},\\14 \cdot 3^{\frac{n-3}2},& n\text{ odd}.\end{cases}\tag1$$

La manera más simple para demostrar $(1)$ es contar directamente el número de maneras para los casos de $n=2,3,4,5$ obtener $a_n=8,14,24,42$, y, a continuación, proceder por inducción de la aplicación de la recurrencia de la relación sugerida por Mike Serio en la base del polinomio característico de la matriz introducida por Julian Mejia: $$a_n=4a_{n-2}-3a_{n-4}.\tag2$$

De hecho, la simplicidad de la respuesta sugiere que es posible que exista una manera más simple de demostrar $(2)$ o incluso directamente a$(1)$.

Answer 2

Definir $n_i=2i-1$ (para un bijection entre 1,2,3,4,5 con 1,3,5,7,9). Considere la matriz de 5x5 $A=(a_{i,j})$ con $a_{i,j}=1$ si $n_i$ e $n_j$ difieren por 2 y $a_{i,j}=0$ lo contrario. Entonces, el número de enteros positivos con "m" los dígitos de la satisfacción de sus propiedades es la suma de las entradas de $A^{m-1}$. Así que usted quiere encontrar la suma de las entradas de $A^{999}$. No sé si esto es fácil de calcular, sin ordenadores.

Editar: Tenemos $$A=\left(\begin{array}{ccccc} 0&1&0&0&0\\ 1&0&1&0&0\\ 0&1&0&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0\\ \end{array} \right)$$ Así, gracias a @Mike comentario, no debería ser difícil encontrar las entradas de $A^{999}$ tenemos que $A=PDP^{-1}$ con

$$D=\left(\begin{array}{ccccc} -1&0&0&0&0\\ 0&0&0&0&0\\ 0&0&1&0&0\\ 0&0&0&-\sqrt{3}&0\\ 0&0&0&0&\sqrt{3}\\ \end{array} \right)$$

$$P=\left(\begin{array}{ccccc} -1&1&-1&1&1\\ 1&0&-1&-\sqrt{3}&\sqrt{3}\\ 0&-1&0&2&2\\ -1&0&1&-\sqrt{3}&\sqrt{3}\\ 1&1&1&1&1\\ \end{array} \right)$$ Así, se puede calcular el $A^{999}=PD^{999}P^{-1}$ cuyas entradas serán una combinación lineal de $(-1)^{999}, (1)^{999}, (-\sqrt{3})^{999},(\sqrt{3})^{999}$.

Answer 3

Aquí hay un programa OCaml que calcula el número de números en términos del tamaño del número:

 type 'a stream= Eos| StrCons of 'a * (unit-> 'a stream)


let hdStr (s: 'a stream) : 'a =
  match s with
  | Eos -> failwith "headless stream"
  | StrCons (x,_) -> x;;

let tlStr (s : 'a stream) : 'a stream =
  match s with
  | Eos -> failwith "empty stream"
  | StrCons (x, t) -> t ();;    



let rec listify (s : 'a stream) (n: int) : 'a list =
  if n <= 0 then []
  else
    match s with
    | Eos -> []
    | _ -> (hdStr s) :: listify (tlStr s) (n - 1);;

let rec howmanynumber start step=
  if step = 0 then 1 else
    match start with
    |1->howmanynumber 3 (step-1)
    |3->howmanynumber 1 (step-1) + howmanynumber 5 (step-1)
    |5->howmanynumber 3 (step-1) + howmanynumber 7 (step-1)
    |7->howmanynumber 5 (step-1) + howmanynumber 9 (step-1)
    |9->howmanynumber 7 (step-1) 
    |_->failwith "exception error"



let count n=
  (howmanynumber 1 n)+(howmanynumber 3 n)+(howmanynumber 5 n)+(howmanynumber 7 n)+(howmanynumber 9 n)

let rec thisseq  n = StrCons(count n , fun ()-> thisseq (n+1))

let result = thisseq 1
 

Entonces, según la solución de @Julian, la respuesta es la suma de las entradas de

$\begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 \\ \end {bmatrix} ^ {999} * \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end {bmatrix}$