¿Cómo puedo encontrar el número de permutaciones sin repetición de la secuencia de todos los números naturales desde $1$ $n$de manera tal que cada permutación comienza con $1$ y termina con $n$ y la diferencia entre términos consecutivos de permutación no es mayor que $3$, es decir,$\lvert a_{i+1} - a_{i}\rvert\in\{1,2,3\}$?
Gracias!
Esto fue bastante dura y mi solución es complicada.
El problema es equivalente a encontrar el número de maneras de saltar de la plaza de $0$ a la plaza de $n$ en una fila de cuadrados, sin saltar a más de tres espacios en un tiempo, y sin perder ninguna plazas en el medio.
$$\begin{array}{c|cccc} \blacksquare&\square&\square&\square&\ldots&\square\\ 0&1&2&3&&n\end{array}$$
Si usted experimente un poco con el problema, usted encontrará que si usted no se le permite moverse más de dos espacios a la vez, luego de su progreso, de izquierda a derecha es altamente predecible. Sin embargo, cuando se puede mover tres espacios en un tiempo, es posible hacer una secuencia de saltos de longitud a la derecha, haga doble vuelta una vez, y luego de regreso, habiendo llenado en todas las plazas perdidas. El hecho de que las formas de hacerlo son limitados, hace que el problema manejable.
En primer lugar, comenzamos con una fila vacía, y la sombra de la primera plaza. Podemos dibujar una línea vertical después de la primera plaza, para recordarnos que todas las casillas a la izquierda de la línea se han llenado. Deje $f(n)$ el número de maneras de llegar a la plaza n, obedeciendo las reglas.
Ahora, hay tres posibilidades: a saltar una plaza, salto de dos plazas, o saltar de tres plazas.
En el primer caso:
$$\begin{array}{|ccccc}\blacksquare&\square&\square&\square&\ldots\end{array}$$
podríamos sacar una nueva línea vertical después de la plaza, justo a la sombra, y estaríamos en la misma situación de nuevo, pero con uno de los cuadrados menos. Así que a partir de este punto, hay $f(n-1)$ formas de llegar a la plaza de la $n$.
En el segundo caso, tenemos la siguiente situación:
$$\begin{array}{|ccccc}\square&\blacksquare&\square&\square&\ldots\end{array}$$
Deje $g(n)$ el número de maneras de obtener la última plaza de esta configuración.
En el tercer caso, tenemos:
$$\begin{array}{|cccccc}\square&\square&\blacksquare&\square&\square&\ldots\end{array}$$
Deje $h(n)$ el número de maneras de obtener la última plaza de esta configuración.
La parte fácil es ver que $f(n)=f(n-1)+g(n-1)+h(n-1)$. Después de que la cosa se complica.
En el segundo caso, llame a la sombra de la plaza "1"; entonces el próximo paso puede ser 1-0-2 o 1-0-3 o 1-2-0-3 o 1-3-0-2-4 o 1-3-0-2-5, o de 1 a 4... (largo saltos a la derecha)
En el tercer caso, llame a la sombra de la plaza "2"; entonces el próximo paso puede ser 2-0-1-3 o 2-0-1-4 o 2-1-0-3 (pero sólo si todos los cuadrados a la izquierda de la línea de llenado) o 2-0-3-1-4 o 2-3-0-1-4 o 2-4-1-0-3-5 o 2-4-1-0-3-6, o de 2 a 5... (largo saltos a la derecha)
¿Cómo podemos lidiar con múltiples saltos a la derecha? En realidad, es bastante simple: vamos a $\hat{h}(n)$ el número de maneras de llegar a la plaza de $n$ en el tercer caso, si quedan plazas vacantes en la izquierda de la línea vertical. Resulta que el orden en el que las primeras plazas se llenan es totalmente dependiente de lo que le pasa a la derecha de la línea.
Poniendo todo junto:
$\begin{array}{rcl}f(n)&=&f(n-1)+g(n-1)+h(n-1)\\ g(n)&=&f(n-2)+f(n-3)+f(n-4)+g(n-2)+g(n-4)+\hat{h}(n-2)\\ h(n)&=&2f(n-3)+2f(n-4)+f(n-5)+g(n-3)+g(n-5)+\hat{h}(n-3)\\ \hat{h}(n)&=&h(n)-f(n-4) \end{array}$
$$\begin{array}{c|ccccccccc} n&0&1&2&3&4&5&6&7&\ldots\\ \hline f&1&1&1&2&6&14&28&56&\ldots\\ g&0&0&1&2&4&8&17&37&\ldots\\ h&0&0&0&2&4&6&11&25&\ldots\\ \hat{h}&0&0&0&2&3&5&10&23&\ldots \end{array}$$
Es fácil de seguir esta tabla utilizar un ordenador. Por ejemplo, he encontrado que, para un centenar de plazas, la respuesta es $f(99)=46103635399805799327514181735963$. Voy a añadir esta secuencia a la OEIS si te gusta.
Edit: he encontrado una manera más simple de expresar la recurrencia: $$f(n)=1\cdot f(n-1)+0\cdot f(n-2)+1\cdot f(n-3)+3\cdot f(n-4)+...$$ Los coeficientes de inicio de $1, 0, 1, 3, 4, 5, 7, 10,$ y a partir de ese punto cada nuevo coeficiente es la suma de la última y la tercera-por último, por lo $5+10=15,$ $7+15=22,$ etc.
Ver la segunda parte para una discusión de Andrew solución
Este problema es equivalente a contar el número de caminos Hamiltonianos en la generalización de la siguiente gráfica (n=8)
$\qquad \qquad \qquad \qquad \qquad \quad$ 
Por supuesto, esto no significa necesariamente que el problema es NP-duro, ya que estos gráficos son "agradable" (simétrica, de título<7, etc). Usando el típico algoritmo de programación dinámica que cuenta con un ({nodos visitados}, nodo actual) me las arreglé para contar las permutaciones de $n\le30$.
$$ \begin{array} ( & \\ 1 & 1 & 1 & 2 & 6 \\ 14 & 28 & 56 & 118 & 254 \\ 541 & 1140 & 2401 & 5074 & 10738 \\ 22711 & 48001 & 101447 & 214446 & 453355 \\ 958395 & 2025963 & 4282685 & 9053286 & 19138115 \\ 40456779 & 85522862 & 180789396 & 382176531 & 807895636 \\ & \\ & \\ \end{array} $$
$$ \qquad $$
Andrew Woods publicado una muy buena solución aquí. Solo quiero añadir un par de cosas. Primera nota de su desplazamiento de la secuencia (mi $a_n$ es igual a su $f_{n-1}$). Porque tenemos una recurrencia lineal, podemos utilizar la matriz deexponenciación método para calcular el valor de $a_n$ para valores muy grandes de $n$. Por ejemplo, $$ \begin{array} ( a_{100} &= 46103635399805799327514181735963 \qquad \checkmark \\ a_{10^{10000}} &= 75922134066658345530 \; \left(\,\text{mod } 10^{20}\,\right) \end{array} $$
La recurrencia de la matriz $M$ e inicial del vector de $b$
$$ \pequeño M = \left( \begin{array} ( . & 1 & . & . & . & . & . & . & . & . & . & . & . \\ . & . & 1 & . & . & . & . & . & . & . & . & . & . \\ . & . & . & 1 & . & . & . & . & . & . & . & . & . \\ . & . & . & . & 1 & . & . & . & . & . & . & . & . \\ . & . & . & . & 1 & . & . & . & . & 1 & 1 & . & . \\ . & . & . & . & . & . & 1 & . & . & . & . & . & . \\ . & . & . & . & . & . & . & 1 & . & . & . & . & . \\ . & . & . & . & . & . & . & . & 1 & . & . & . & . \\ . & . & . & . & . & . & . & . & . & 1 & . & . & . \\ . & 1 & 1 & 1 & . & . & 1 & . & 1 & . & . & . & 1 \\ 1 & 2 & 2 & . & . & 1 & . & 1 & . & . & . & 1 & . \\ . & . & . & . & . & . & . & . & . & . & . & . & 1 \\ -1 & . & . & . & . & . & . & . & . & . & 1 & . & . \\ \end{array} \right) \qquad b = \left( \begin{array} ( f_0 \\ f_1 \\ f_2 \\ f_3 \\ f_4 \\ g_0 \\ g_1 \\ g_2 \\ g_3 \\ g_4 \\ h_4 \\ \hat{h}_2 \\ \hat{h}_3 \\ \end{array} \right) = \left( \begin{array} ( 1\\1\\1\\2\\6\\0\\0\\1\\2\\4\\4\\0\\2\\ \end{array} \right) $$
donde la omitido los valores son todos ceros. A continuación, $a_n$ es simplemente la primera coordenada de $M^{n-1} b$. El siguiente paso es encontrar la ecuación característica de a $M$.
Usted puede encontrar la ecuación característica de a $M$ mediante el uso de Matlab $\texttt{charpoly}$ comando, el cual arroja $x^{13} - x^{12} - x^{11} - x^{10} - 3x^9 - 2x^8 - x^7 + x^6 + 2x^5 + x^4 $, lo que nos da la recurrencia $$a_n = a_{n-1} + a_{n-2} + a_{n-3} + 3a_{n-4} + 2a_{n-5} + a_{n-6} -a_{n-7} - 2a_{n-8} -a_{n-9} $$
Yuval Filmus calcula de la ecuación característica con un método diferente, produciendo el mínimo de recurrencia lineal
$$ a_n = 2a_{n-1} - a_{n-2} + 2a_{n-3} + a_{n-4} + a_{n-5} - a_{n-7} - a_{n-8} $$
Tenga en cuenta que si se resta la segunda repetición de la primera, se obtiene la segunda recurrencia cambiado por uno (el término correspondiente a la raíz (-1) se desvanece). Para ser completo, otro interesante recurrencia que Andrew encontrado es
$$ \begin{array} ( a_n &= a_{n-1} + a_{n-3} + 3a_{n-4} + 4a_{n-5} + 5a_{n-6} + 7a_{n-7} + 10a_{n-8} + ... \\ &:= \sum_{i\ge1}{c_i a_{n-i}} \end{array} $$
donde el coeficiente de $c_i = c_{i-1} + c_{i-3}$$i>8$. Supongo que él encontró esta recurrencia por la expansión de las recurrencias $g,h,\hat{h}$ de su post (que es como la he encontrado). Finalmente, como Yuval señaló, obtenemos una tasa de crecimiento $a_n = \Theta(\gamma^n)$ donde $\gamma \approx 2.11393$ es la magnitud de los más grandes de la raíz de la ecuación característica.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
