Cuántos números de longitud N (N es el número de dígitos) son posibles

Question

Dado $N \le 10^9$, determinar cuántos números de longitud $N$ son posibles con la siguiente restricción: el adyacentes dígitos del número debería haber una diferencia absoluta de $1$.

Por ejemplo, para $N = 3$, números que comiencen con $1$$101,121,123$. Para $N =4$, números que comiencen con $1$$1210,1212,1232,1234$.

Mi acercamiento a este problema es: el primer dígito puede ser cualquier cosa, desde la $1$$9$. El segundo dígito podría ser firstDigit$+1$ o firstDigit $-1$. Y así sucesivamente, si lo hacemos, obtenemos el número total de posibles números de $9\cdot2^{N-1}$. Pero la captura es, debemos restar los números con dígitos menos que $0$ o mayor que $9$.

Estoy atrapado aquí. Cómo obtener una fórmula para restar a estos números de la total. O es que hay un método mejor para solucionar este problema?

Answer 1

Puedo probar un enfoque diferente: yo escribo un $10 \times 10$ de la matriz de transición (de una dimensión por dígito, como una cadena de markov, pero esta vez no se trata de las probabilidades, pero trata de contar el número de posibilidades), donde cada entrada $a_{ij}$ dice que si se puede ir de dos dígitos $j$ de los dígitos $i$. Digamos que la parte superior a la izquierda de la entrada tiene los índices de $(0,0)$ sólo para este ejemplo, (sé que esto no se suele hacer así) Esta matriz es como sigue:

$A= \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}$

If we want to know what the next digit could be if we are at $n=4$ we just multiply the matrix $$ with the vector $e_4 = (0,0,0,0,1,0,0,0,0,0)^t$ (the one is in the fourth position when beginning counting at 0. Then we get the vector $$Ae_4 = (0,0,0,1,0,1,0,0,0,0)^t$$.

After two steps (so for the third digit) we get the following vector:

$$A^2e_4 = (0,0,1,0,2,0,1,0,0,0)^t$$

and so forth. So the $n$th entry of this vector says how many numbers have the digit $n$ as their third digit (=after two steps).

So the total of the new possibilities of those numbers is just the sum of the entries of the new vector. This is if we just take only one step (transition from one to the next digit). So when we want to get the possibilities of the next step, we just have to multiply with $A$ one more time.

As we want all combinations with all starting numbers we have to use the starting vector $v=(0,1,1,1,1,1,1,1,1,1)^t$ (since we cannot start with the digit 0 as @Mathmo123 mentioned (Thanks!))

In total we have $N-1$ transitions, so $v$ needs to be multiplied by $A^{N-1}$. For $N=9$ get:

$$A^8 v = (56,126,153,208,208,228,201,181,125,70)^t$$

Which makes a total of 1556. Or for $N=3$ we get

$$A^2 v = (1,3,3,4,4,4,4,4,3,2)$$

which makes a total of $32$.

Edit

If you want the total of all combinations from $N=1,...,10^9$ we can make use of the geometric series.

We want to sum up all the solutions from all those $N$, then we get (let m=10^9$ ser el máximo exponente):

$Iv+Av+A^2v+A^3v+...+A^mv = (I+A+A^2+A^3+...+A^m )v = (I-A)^{-1}(I-A^{m+1}) v$

Por supuesto, aquí vamos a necesitar una buena cantidad de la multiplicación de la matriz, especialmente para el cálculo de $A^{m+1}$.

Apéndice

PS: por supuesto que no se puede calcular este a mano, yo, rápidamente hizo en Octave/Matlab:

a=diag(ones(9,1),-1);
a=a+a'; %now we have our finished matrix a
e4 = [0,0,0,0,1,0,0,0,0,0]'; 
%the two explaining examples
disp(a*e4);   
disp(a^2*e4);
%our resulting vector:
 v = ones(10,1);
v(1)=0;
disp(a^8 * v);
%the total for N=9
disp( sum(a^8 * v));