Demuestre que esta función sobre las secuencias es cíclica.

Question

Dada una secuencia $f$ definir una nueva secuencia $\phi f$ de la siguiente manera:

$$ \phi f(n):=\text{card }\{k\in\mathbb{N}_{\leq{n}}\mid f(k)=f(n)\}$$

donde $\text{card}$ es la función de cardinalidad del conjunto. En otras palabras $\phi f(n)$ cuenta la frecuencia con la que $f(n)=f(k)$ para $k\leq n$ . Además, podemos aplicar iterativamente $\phi$ a $f$ . He aquí un ejemplo:

$$\begin{array} \\ f & = & (a,&b,&a,&c,&b,&d,&a,&c,&a,&b,&...) \\ \phi f & = & (1,&1,&2,&1,&2,&1,&3,&2,&4,&3,&...) \\ \phi^2 f & = & (1,&2,&1,&3,&2,&4,&1,&3,&1,&2,&...) \\ \phi^3 f & = & (1,&1,&2,&1,&2,&1,&3,&2,&4,&3,&...) \\ \end{array}$$

Observe que $\phi f=\phi^3 f$ que por inducción implica $\phi^nf=\phi^{n+2}f$ para todos $n\in\mathbb{N}$

Conjetura : Si $f$ es una secuencia cualquiera, entonces $\phi^n f = \phi^{n+2} f$ para todos $n\in\mathbb{N}$ .

Answer 1

Muy buena observación.
Como usted observa, para la conjetura basta con demostrar $\phi^3=\phi$ .

Secuencias de llamadas $a=(a_1,a_2,\dots)$ y $b=(b_1,b_2,\dots)$ similar , si $\phi a=\phi b$ es decir, para cada índice $n$ , $\ a_n$ ocurre las mismas veces entre $a_1,\dots,a_n\ $ como $\ b_n$ entre $b_1,\dots,b_n$ .
Por ejemplo, las secuencias $(1,1,2,2,3,3,1),\ (1,1,2,2,3,3,2),\ (1,1,2,2,3,3,3)$ son similares.

Tenemos que demostrar que $\phi^2 a$ es similar a $a$ para una secuencia arbitraria $a$ .

Supongamos que se mantiene para $n$ secuencias largas, y tomar $a_{n+1}$ en $a=(a_1,\dots,a_{n+1})$ .

• Se trata de un "nuevo elemento" ( $\phi a(n+1)=1$ ), en cuyo caso el número de $1$ que denota los nuevos elementos, se incrementa en uno en $\phi a$ , lo que implica $\phi^2 a(n+1)=|\{a_1,\dots,a_{n+1}\}|$ que es un nuevo elemento de la secuencia $\phi^2a$ .
• O bien, es un elemento que se repite, y $s:=\phi a(n+1)=|\{i\le n+1:a_i=a_{n+1}\}|$ .
  Ce site $s$ se produce en $\phi a$ para exactamente $q$ veces, donde $q$ es el número de $a_i$ 's ocurriendo exactamente $s$ veces en $a$ . (Si $s$ es nuevo, entonces $q=1$ y $a_{n+1}$ puede ser sustituido por cualquiera de estos $a_i$ para obtener una secuencia similar).
  Por un lado, significa $\phi^2 a(n+1)=q$ .
  Por otro lado, $q$ ya se produjo en $\phi^2 a(1,\dots,n)$ exactamente $s-1=|\{i\le n:a_i=a_{n+1}\}|$ tiempos.

---

Otro enfoque

Llamar a una secuencia $a$ de enteros positivos a secuencia regular si para todo $n$ ,

1. $\ 1\le a_n\le\max_{i<n}a_i+1$
2. En cada segmento inicial de $a$ el número de $x$ es al menos el número de $y$ siempre que $x\le y$ .

Obsérvese que 2. puede reformularse como: si $a_n=a_i$ para algunos $i<n$ entonces $a_n$ es mínima entre los elementos de la secuencia que aparecen exactamente $(\phi a)_n-1$ veces en $(a_1,\dots,a_{n-1})$
[porque $a_n$ en $(a_1,\dots,a_n)$ tiene una ocurrencia más que cualquiera de ellos].

Por ejemplo, $(1,2,2)$ y $(1,2,3,2)$ no son regulares, mientras que $(1,2,1)$ y $(1,2,3,1)$ son regulares.

Propuesta.
$\ $ a) $\ \phi a$ es regular para cualquier secuencia $a$ .
$\ $ b) $\ $ Si $a$ es una secuencia regular, entonces $\phi^2 a=a$ .

Answer 2

Solución en curso

Para una secuencia $f$ definir

1. el pre-imagen de $f$ denotado $f^{-1}(a):=\{n\in\mathbb{N}\mid f(n)=a\}$ .

2. a truncamiento de $f$ en $t$ , denotado como $f_{\leq t}$ es la secuencia con el dominio restringido a $\{n\in\mathbb{N}\mid n\leq t\}$ .

Entonces, por $f_{\leq t}^{-1}(n)$ denotan $\{k\in\mathbb{N}\mid k\leq t,f(k)=f(n)\}$ . He aquí una nueva definición para $\phi$ :

Definición 1: Para cualquier secuencia $f$ , defina $\phi f(n) := \text{card }f_{\leq n}^{-1}(n) $

La siguiente definición y conjetura describe las secuencias que $\phi$ producirá:

Definición 2: Una secuencia $f$ con rango $\mathbb{N}$ es regular si para cualquier truncamiento en $t\in\mathbb{N}$ , $$\text{card }f_{\leq t}^{-1}(1)\geq\text{card }f_{\leq t}^{-1}(2)\geq\text{card }f_{\leq t}^{-1}(3)\geq...$$

Es decir, para cualquier truncamiento de la secuencia $f$ el número de $1$ es $\geq$ el número de $2$ s, que es $\geq$ el número de $3$ s y así sucesivamente, lo que asegura que la secuencia está contando correctamente. Estoy casi seguro de que esta definición es equivalente a las de los comentarios.

Conjetura: Si $f$ es una secuencia cualquiera, entonces $\phi f$ es regular, y si $f$ es regular entonces $\phi^2 f = f$ .

Prueba $\phi f$ es regular por inducción al tamaño de los truncamientos y utilizando el siguiente lema:

Lema 1: Una secuencia $f$ es regular si para cada $t\in\mathbb{N}$ la secuencia truncada $f_{\leq t}$ es regular.

Propuesta: Para cualquier secuencia $f$ , $\phi f$ es regular.

Prueba: Si $t=1$ , $\phi f_{\leq 1}$ es la secuencia única, $\phi f_{\leq 1}=(1)$ por lo que es trivialmente regular.

Paso inductivo: Supongamos que para cualquier $s<t$ la secuencia truncada $\phi f_{\leq s}$ es regular. Ahora muestra $\phi f_{\leq t}$ es regular demostrando que para cualquier truncamiento se cumple la desigualdad definitoria. De hecho, basta con demostrar la desigualdad para el truncamiento hasta la longitud $t$ .