Número de funciones$f\colon\{1,2,3,\dots,n\} \to \{1,-1,i,-i\}$ que satisface una cierta condición

Question

¿Qué debo hacer aquí? Ni siquiera sé por dónde empezar. Por favor, ayúdame dándome una pista.

Encuentre cuántas son las funciones:$f: \{1,2,3,\dots,n\} \to \{1,-1,i,-i\}$, donde$n \geq 2$, tal que

ps

Encuentro$$f(k)+f(k+1)\neq 0 \, \, \, (k=1,2,3,\cdots,n-1), \quad \quad \quad f(n)+f(1)\neq 0$ entonces número de$n=2$ es$f$.

Para$12$ entonces el número de$n=3$ es$f$.

Answer 1

Deje $n$ ser un entero positivo. Una función de $f:\{1,2,\ldots,n\}\to\{1,-1,\text{i},-\text{i}\}$ se dice $n$-admisible si $f(k)+f(k+1)\neq 0$ todos los $k=1,2,\ldots,n-1$$f(n)+f(1)\neq 0$. Deje $a_n$ denotar el número de $n$-admisible funciones.

Fijar un número entero $n\geq 3$. En primer lugar, hay $4\cdot 3^{n-2}$ funciones $g:\{1,2,\ldots,n-1\}\to\{1,-1,\text{i},-\text{i}\}$ tal que $g(k)+g(k+1)\neq 0$$k=1,2,\ldots,n-2$. (Este es un sencillo recuento de trabajo: $g(1)$ $4$ valores posibles, y $g(k)$ sólo ha $3$ posibles valores de $k=2,3,\ldots,n-1$.) Entre estos $g$'s, hay$a_{n-2}$$g(n-1)=g(1)$, y se puede extender como una función $g$ $n$- admisible en función de $f$ $3$ maneras. Por el otro $g$'s, hay $4\cdot 3^{n-2}-a_{n-2}$ de ellos, y podemos extender esta función a $g$ $n$- admisible en función de $f$ sólo en $2$ maneras. En consecuencia, $$a_n=3\cdot a_{n-2}+2\cdot\left(4\cdot 3^{n-2}-a_{n-2}\right)=a_{n-2}+8\cdot 3^{n-2}\,.$$ Como $a_1=4$$a_2=12$, obtenemos $$a_n=3^n+(-1)^n+2=\left\{ \begin{array}{cc} 3^{n}+1\,,&\text{if }n\text{ is odd}\,,\\ 3^n+3\,,&\text{if }n\text{ is even}\,. \end{array}\right.$$

Answer 2

Bueno, hay una forma simple de recursividad. Para conseguirlo, la caída de la última condición ($f(n)+f(1)\neq 1$). Podemos definir cuatro tipos de cadenas que pasar todas las pruebas, excepto el último.

$a_n$ son los de longitud de $n$ en el que la última es igual a la primera (por lo $a_1=4$)

$b_n$ son los de longitud de $n$ en el que el último es $-1$ los tiempos de la primera ($b_1=0$)

$c_n$ son los de longitud de $n$ en el que el último es $i$ los tiempos de la primera ($c_1=0$)

$d_n$ son los de longitud de $n$ en el que el último es $-i$ los tiempos de la primera ($d_1=0$)

Deje $T_n=a_n+b_n+c_n+d_n$

Claramente tenemos $$a_n=a_{n-1}+c_{n-1}+d_{n-1}=T_{n-1}-b_{n-1}$$ $$b_n=b_{n-1}+c_{n-1}+d_{n-1}=T_{n-1}-a_{n-1}$$ $$c_n=a_{n-1}+b_{n-1}+c_{n-1}=T_{n-1}-d_{n-1}$$ $$d_n=a_{n-1}+b_{n-1}+d_{n-1}=T_{n-1}-c_{n-1}$$

También es claro que la $$T_n=3\times T_{n-1}\implies T_n=3^{n-1}\times 4$$

Si, por último, añadimos de nuevo la condición final y deje $S_n$ ser las cadenas de longitud $n$ que están realmente interesados en la contabilidad de podemos fácilmente obtener un $$S_n=3a_{n-1}+2b_{n-1}+2c_{n-1}+2d_{n-1}=2T_{n-1}+a_{n-1}=3^{n-2}\times 8 +a_{n-1}$$

Muy fácil de implementar esto y puede ser (un poco) simplificado señalando que $n≥3\implies a_n=S_{n-1}$ lo que nos permite escribir $$n≥4\implies S_n=3^{n-2}\times 8+S_{n-2}$$

Si partimos de este con $S_2=12,S_3=28$ podemos suma de los parciales de la serie geométrica para obtener (bastante feo) cerrado fórmulas. Incluso los índices obtenemos $$S_{2n}=12+9\times \left(9^{n-1}-1\right)$$ For odd indices we get $$S_{2n+1}=28+27\times \left(9^{n-1}-1\right)$$ At least for $n≥2$. Tal vez hay una más esclarecedor manera de acercarse a este analíticamente, pero hasta el momento no he localizado.

Answer 3

Deje $A(n)$ el número de tales funciones. Definimos $B(n)$ como el número de funciones de la reunión de la interna, requisito que ha $f(n)=-f(1), C(n)$ como el número de funciones de la reunión de la interna, requisito que ha $f(n)=f(1), D(n)$ el número de funciones de la reunión de la interna, requisito que ha $f(n)=\pm i f(1)$ entonces podemos escribir las recurrencias $$B(n)=B(n-1)+D(n-1)\\C(n)=C(n-1)+D(n-1)\\D(n)=2B(n-1)+2C(n-1)+D(n-1)\\A(n)=D(n)+C(n)\\D(n)-D(n-1)=2B(n-1)-2B(n-2)+2C(n-1)-2C(n-2)+D(n-1)-D(n-2)\\D(n)-D(n-1)=4D(n-2)+D(n-1)-D(n-2)\\D(n)=2D(n-1)+3D(n-2)\\D(2)=8, D(3)=16$$ Esto le da cuatro veces OEIS A122983 para $A(n)$. Con el factor de $4$, comienza a $12,28,84,244,732,2188,6564$ asintótico de la tasa de crecimiento es un factor de $3$, como sería de esperar. Al final el problema se diluye a medida que avanzamos.

Answer 4

Cada función de $f$ que satisface corresponde a una función $g:\{1,\dots,n\}\to\{1,i,-i\}$: $$f(i+1)=f(i)g(i)\text{ for }i=1,\dots,n-1\text{ and }f(1)=f(n)g(n)$$

Sólo hay una condición en esta función $g$: $$g(1)\times\cdots\times g(n)=1$$

Y la función $f$ está determinado por $f(1)$ y la función $g$. Configuración: $$g\left(k\right)=i^{r_{k}}$$ with $r_{k}\in\left\{ -1,0,1\right\} $ esta condición es (precaución este es ${\color{red}{wrong}}$): $$\sum_{k=1}^{n}r_{k}=0\tag1$$

Así que la pregunta ahora es: ¿cuántas de dichas sumas existen? La respuesta a eso es:$$\sum_{s=0}^{\lfloor\frac{1}{2}n\rfloor}\frac{n!}{s!s!\left(n-2s\right)!}$$

Debe ser multiplicado por el $4$ que es el número de posibilidades para$f(1)$, por lo que la respuesta final:$$4\sum_{s=0}^{\lfloor\frac{1}{2}n\rfloor}\frac{n!}{s!s!\left(n-2s\right)!}$$

Lamentablemente no tengo forma cerrada para esto todavía.

---

Edición (después de encontrar el error y eliminación)

Encuentra error en $(1)$: la condición es $$4\mid\sum_{k=1}^{n}r_{k}$$

(¿Cómo diablos podría yo,...,sigh).

Así nos encontramos con:$$\sum_{4\mid s-t}\frac{n!}{\left(n-s-t\right)!s!t!}$$

No de una forma cerrada, sin embargo. Otros han servido mejor.