Número de configuraciones posibles desplazando los "2" en $12121212$ a la derecha.

Question

Se me ocurrió esta pregunta mientras resolvía otro problema de combinatoria.

Digamos que hay un número $12121212$ . Defina una operación como intercambio de dos dígitos adyacentes cualesquiera si el dígito de la izquierda es $2$ . (Por ejemplo, intercambiando el $2$$nd$ y $3$$rd$ dígito para dar $11221212$ como resultado, pero cambiando el $3$$rd$ y $4$$th$ no está permitido). No hay límite en cuanto a las operaciones que se pueden hacer con el número (tampoco es posible ninguna operación). ¿Cuántos números posibles se pueden formar?

Preguntas

• ¿Existe un nombre para este tipo de problemas?
• ¿Cómo se puede resolver?
• Extra: ¿Qué pasa si el original no es $12121212$ pero algunos otros números (como por ejemplo $121212121111111111$ ? ¿Esto complicará mucho la cuestión?

Mi intento

No estoy seguro de cómo enfocar esta cuestión. Mi observación es que la configuración final $11112222$ se mantiene sin cambios después de cualquier operación. Por lo tanto, parece que el primer ' $2$ ' originalmente en $2$$nd$ se desplaza a la posición $5$$th$ la primera posición ' $2$ ' originalmente en $4$$th$ se desplaza a la posición $6$$th$ posición, etc.
Sin embargo, algunos de los casos no son válidos, pero al menos sé que el número de configuraciones posibles es menor que $4\cdot3\cdot2\cdot1 = 24$ . Así que una posible manera será enumerar todas las configuraciones posibles, pero es un dolor porque no puedo encontrar una manera de hacerlo de una manera organizada. Por lo tanto, tengo curiosidad por saber si hay una manera de hacerlo de manera más eficiente e inteligente.

Answer 1

Piensa en estas cadenas como si describieran caminos de montaña desde $\langle 0,0\rangle$ a $\langle 2n,0\rangle$ , donde $n$ es el número de $1$ s (o $2$ s): cada $1$ corresponde a un paso superior de $\langle x,y\rangle$ a $\langle x+1,y+1\rangle$ y cada $2$ a un paso inferior de $\langle x,y\rangle$ a $\langle x+1,y-1\rangle$ . Inicialmente tenemos un camino que se parece a esto:

             /\/\/\/\.../\

Cada movimiento legal consiste en intercambiar un paso hacia abajo con el paso a su derecha inmediata. Si ese paso es también un paso descendente, el camino no cambia. En caso contrario, una secuencia \/ se convierte en una secuencia /\ . Todavía tenemos $n$ escalones superiores y $n$ pasos hacia abajo, por lo que el camino todavía termina en $\langle 2n,0\rangle$ y una fácil inducción muestra que ningún camino obtenido de esta manera cae por debajo del $x$ -eje.

Se necesita un poco más de trabajo para demostrar que cada camino de montaña desde $\langle 0,0\rangle$ a $\langle 2n,0\rangle$ que nunca desciende por debajo del $x$ -es obtenible de esta manera, pero una vez que tenemos eso, hemos terminado: es bien sabido que el número de tales caminos es $C_n$ El $n$ -el número de catalán.

La idea es bastante sencilla. Tomar cualquier camino de montaña $P$ . Leyendo de izquierda a derecha, encuentre el primer pico a una altura mayor que $1$ . (Si no hay ninguno, hemos terminado: es nuestro camino inicial.) Ese pico consiste en un paso hacia arriba seguido de un paso hacia abajo; intercambia esos dos pasos. Este intercambio es simplemente la inversa del movimiento legal en el procedimiento original. Repite este proceso hasta que no haya más picos de altura superior a $1$ . En ese punto tienes el camino

             /\/\/\/\.../\,

y $P$ puede obtenerse claramente de ella mediante una secuencia de movimientos legales.