Divídelo mediante el principio de multiplicación:
$$abcdefgh$$
- Paso 1: Elija cuáles son los cuatro $n$ se van a intercambiar las letras (por ejemplo $bdeg$ )
$$\color{grey}{a}\color{red}{b}\color{grey}{c}\color{red}{de}\color{grey}{f}\color{red}{g}\color{grey}{h}$$
¿De cuántas formas se puede realizar este paso para una cadena de $n$ ¿Cartas?
$\binom{n}{4} = \frac{n!}{4!(n-4)!}$
- Paso 2: Colorea de azul la letra elegida que aparezca más pequeña. Elija una más de las tres letras rojas restantes para colorearla de azul. ( por ejemplo $g$ en la imagen siguiente )
$$\color{grey}{a}\color{blue}{b}\color{grey}{c}\color{red}{de}\color{grey}{f}\color{blue}{g}\color{grey}{h}$$
¿De cuántas maneras puede realizarse este paso?
$3$ vías
Ahora, intercambia las letras azules, e intercambia las letras rojas.
$$agcedfbh$$
El ejemplo de la imagen tiene los dos pares de desajustes siguientes: $(b,g)$ y $(d,e)$ .
Debe quedar claro que cada secuencia de elecciones de los pasos anteriores generará exactamente una permutación del tipo deseado de forma única y que todas las permutaciones son generadas exactamente por una secuencia de elecciones. El principio de multiplicación dice que el número de permutaciones es el producto del número de elecciones disponibles en cada paso.
Principios de una generalización:
Sea la cadena a permutar $\underbrace{aa\dots a}_{\alpha_a~\text{copies}} \underbrace{bb\dots b}_{\alpha_b~\text{copies}} cc\dots c\dots \underbrace{kk\dots k}_{\alpha_k~\text{copies}}$ donde hay $k$ letras distintas que aparecen, y $\alpha_a+\alpha_b+\dots+\alpha_k = n$ letras en total (contando las letras repetidas).
Sea $\chi_{a,0}$ denotan el caso de que dos $a$ se intercambiaron entre ellos y ningún otro $a$ se intercambiaron. Dejemos que $\chi_{a,1}$ denotan el caso de que dos $a$ 's se intercambiaron entre ellos y un tercero $a$ se cambió por otra letra. Sea $\chi_{a,2}$ denotan el caso de que cuatro $a$ se intercambiaron entre sí. Define eventos similares para las otras letras.
Asumir temporalmente que cada letra es distinta (cada copia de una letra concreta, asumir que tiene un número de subíndice específico, por ejemplo).
$$a_1b_1b_2b_3b_4c_1c_2c_3d_1e_1f_1f_2$$
Cuente cuántas permutaciones existen con las propiedades deseadas como arriba ignorando temporalmente el hecho de que algunas letras pretenden ser idénticas.
$3\binom{n}{4}$ vías
Elimine las permutaciones que intercambian al menos un par de letras idénticas. Para contar cuántas de éstas hay, intentamos contar $|\chi_{a,0}\cup \chi_{a,1}\cup \chi_{a,2}\cup \chi_{b,0}\cup \dots\cup \chi_{k,2}|$ .
Por exclusión de inclusión, esto es $\sum\limits_{x\in\{a,b,\dots,k\}}\sum\limits_{i=0}^2|\chi_{x,i}| -\sum\limits_{\{x,y\}\subset\{a,b,\dots,k\},~x< y}|\chi_{x,0}\cap \chi_{y,0}|$
Contar $|\chi_{x,0}|$ elige las dos letras ofensivas $x$ 's, y luego elegir los otros dos no $x$ 's. $\binom{\alpha_x}{2}\binom{n-\alpha_x}{2}$ tales permutaciones.
Contar $|\chi_{x,1}|$ elija a los tres infractores $x$ 's, elija uno de ellos para emparejarlo con un no $x$ y elija el no $x$ para ser emparejado. $\binom{\alpha_x}{3}\cdot 3\cdot (n-\alpha_x)$ tales permutaciones.
Contar $|\chi_{x,2}|$ elija a los cuatro infractores $x$ y luego elegir cómo se emparejaron. $3\binom{\alpha_x}{4}$ tales permutaciones.
Obsérvese que al expandir la unión por inclusión-exclusión, las únicas intersecciones que sobreviven son de la forma $\chi_{x,0}\cap \chi_{y,0}$ con $x\neq y$ ya que cualquier otra intersección implicaría que había cinco o más letras seleccionadas.
Contar $|\chi_{x,0}\cap \chi_{y,0}|$ seleccione los dos $x$ y seleccione los dos $y$ 's. $\binom{\alpha_x}{2}\binom{\alpha_y}{2}$ tales permutaciones.
Quitando estos del total original, tenemos entonces un total final de:
$$3\binom{n}{4} - \sum\limits_{x\in \{a,b,\dots,k\}}\left(\binom{\alpha_x}{2}\binom{n-\alpha_x}{2}+\binom{\alpha_x}{3}\cdot 3\cdot (n-\alpha_x)+3\binom{\alpha_x}{4}\right) + \sum\limits_{\{x,y\}\subset\{a,b,\dots,k\},~x<y}\binom{\alpha_x}{2}\binom{\alpha_y}{2}$$
Para un ejemplo concreto, como $abbbbcccdeff$ tendríamos $3\binom{12}{4} - \underbrace{\binom{4}{2}\binom{8}{2}}_{\chi_{b,0}} - \underbrace{\binom{4}{3}3\cdot 8}_{\chi_{b,1}} - \underbrace{3}_{\chi_{b,2}} - \underbrace{\binom{3}{2}}_{\chi_{c,0}}-\underbrace{\binom{3}{3}\cdot 3\cdot 9}_{\chi_{c,1}}-\underbrace{\binom{2}{2}\binom{10}{2}}_{\chi_{f,0}}+\underbrace{\binom{4}{2}\binom{3}{2}}_{\chi_{b,0}\cap\chi_{c,0}}+\underbrace{\binom{4}{2}\binom{2}{2}}_{\chi_{b,0}\cap\chi_{f,0}}+\underbrace{\binom{3}{2}\binom{2}{2}}_{\chi_{c,0}\cap\chi_{f,0}} = 1170$
Para un ejemplo más pequeño que debería poder ser forzado, $abbde$ habría $3\binom{5}{4} - \binom{2}{2}\binom{3}{2} = 15-3=12$ . En concreto, son $adebb,aedbb,babed,badbe,baedb,bbaed,bdabe,beadb,dbeab,debab,ebdba,edbba$ (copiado de su lista anterior, sustituido $c$ con $b$ y he eliminado las tres permutaciones infractoras)
