Formas de la fusión de dos incomparable listas ordenadas de elementos de mantener su orden relativo

Question

Supongamos que, para una aplicación real, he acabado con una lista ordenada A = {$a_1, a_2, ..., a_{|A|}$} de elementos de un cierto tipo (por ejemplo, Tipo a), y otra lista ordenada B = {$b_1, b_2, ..., b_{|B|}$} de elementos de un tipo diferente (Tipo B), que Tipo de elementos que sólo son comparables con el Tipo-a los elementos, y de la misma manera para el Tipo-B.

En este momento busco a contar la siguiente: ¿en cuántas formas puedo combinar ambas listas, de tal manera que el orden relativo de Tipo a y de Tipo B-elementos, respectivamente, se conserva? (es decir, que si $P_M(x)$ representa la posición de un elemento de a o B en la lista combinada, a continuación, $P_M(a_i)<P_M(a_j)$ $P_M(b_i)<P_M(b_j)$ todos los $i<j$)

He tratado de averiguar esto de manera constructiva, comenzando con el vacío de la lista combinada y la inserción de elementos de a o B de una en una, a contar de cuántas maneras, cada inserción se puede hacer, pero ya que esta depende de la colocación de los elementos anteriores del mismo tipo, yo he tenido un poco de suerte hasta ahora. También he intentado explícitamente a contar todas las posibilidades para diferentes (pequeño) de longitudes a y B, pero he sido incapaz de extraer todo el potencial de principio general en esta forma.

Answer 1

La lista combinada tiene una longitud de $|A|+|B|$. Una vez que usted sabe que $|A|$ posiciones en que están ocupados por los elementos de la lista a, usted también sabe exactamente cómo todo esto tiene que ser ordenado, ya que las órdenes internas de los elementos de a y los elementos de B son ya conocidos. Por lo tanto, hay $$\binom{|A|+|B|}{|A|}=\binom{|A|+|B|}{|B|}$$ possible merged lists, one for each choice of $|A|$ posiciones de los elementos de la lista A.