¿De cuántas maneras podemos organizar dos cadenas con elementos distintos para que el orden esté intacto?

Question

¿De cuántas maneras podemos organizar dos cadenas (con elementos distintos) para que el orden esté intacto?

Por ejemplo, si las cadenas son "aA" y "bk". Los arreglos válidos son: "aAbk", "abAk", "abkA", "baAk", "bakA" y "bkaA" y los arreglos no válidos son "akbA", "Aabk". Entonces, en este caso, la respuesta requerida es$6$.

Estoy buscando un enfoque combinatorio para resolver este problema. ¿Alguna idea?

Answer 1

Si la primera cadena tiene una longitud$n_1$ y la segunda tiene una longitud$n_2$, la respuesta es$\binom{n_1+n_2}{n_1}=\binom{n_1+n_2}{n_2}$. De hecho, la disposición se determina de manera única cuando en la secuencia de$n_1+n_2$ de lugares decide cuáles están ocupados por los caracteres de la primera cadena. Luego tiene un conjunto de$n_1$ lugares para completar con los caracteres de la primera cadena en el orden correcto, y los lugares restantes forman un conjunto de$n_2$ lugares para completar con los caracteres de la segunda cadena en el orden correcto

Answer 2

así lo veo como una cadena binaria 00 es aA y 11 es bk. ahora 0011,0101,0110,1001,1010,1100 son soluciones, como se puede ver reemplazando el primer 0 con un y el segundo con A. y el primer 1 con b y el segundo con k. tenemos todas las soluciones Entonces esto es solo un coeficiente binomial.

Así que permita que$s$ sea la longitud de la cadena 1 y$t$ la longitud de la cadena 2, luego el recuento de todas las combinaciones es$\binom{s+t}{t}$.

En tu ejemplo$\binom{4}{2} = 6$

Answer 3

Otra forma de mirarlo, utilizando las variables de Carlo Verschoor la solución:

Tome $(s+t)$ cosas, s con la etiqueta "1" y " t con la etiqueta "2". Estos se pueden organizar en $(s+t)!$ maneras. Luego se divide por $s!$ e $t!$ a dar a los distintos arreglos de 1 y 2. Cada arreglo es un diferente conjunto de instrucciones para seleccionar el siguiente elemento de la indicada, ordenó la cadena.

Por ejemplo, "112122121..." significa tomar los dos primeros caracteres desde el inicio de la cadena #1, a continuación desde el inicio de la Cadena #2, luego el siguiente en la cadena #1, luego el siguiente o dos en Cadena #2, y así sucesivamente...