Permutar "aaaaabbbbbccccc" de modo que no dos cartas idénticas adyacentes

Question

Esta es una pregunta de seguimiento de Aplicación de PIE. ¿Cuántas secuencias con las letras "aaaaabbbbbccccc" son hay para que no hay dos cartas idénticas son adyacentes?

Answer 1

Mis pensamientos iniciales:

Hay $15!$ permutaciones cuando consideramos todas las cartas para ser distinto (para empezar!), decir $a_1,\ldots a_5$, y del mismo modo para $b$'s y $c$'s. Las condiciones que se deben evitar son $A(i,j)$, $B(i,j)$, $C(i,j)$ (donde $i < j$), que, por ejemplo, $A(i,j)$ significa que todas las permutaciones donde $a_i$ $a_j$ son adyacentes etc. Así que tenemos que contar todas las permutaciones que evitar todas las condiciones (clásica de inclusión-exclusión), y luego dividir el resultado por $5! 5! 5!$, debido a que en el resultado final, en realidad no podemos distinguir la $a$s, $b$'c $c$'s.

Cómo recuento $A(i,j)$: podemos combinar $a_i$ $a_j$ a un símbolo de $a(i,j)$, por lo que nos quedamos con $14!$ símbolos, que nos permutar. En el resultado final, podemos expandir $a(i,j)$ a $a_i a_j$ o $a_j a_i$ y obtiene dos permutaciones que cumplan con la condición. Así que tenemos $2!14!$ muchas permutaciones en $A(i,j)$ por cada $i < j$. Y tenemos ${5 \choose 2}$ tales condiciones. El mismo tiene para todos los $B(i,j)$$C(i,j)$.

Así que tenemos $15! - 3\cdot {5 \choose 2} 2! 14!$ como la primera aproximación.

Por supuesto, hacemos doble-contar aquí: condiciones de $A(i,j)$ $A(l,k)$ ambos pueden ocurrir al mismo tiempo. Hay una diferencia aquí al $(i,j)$ $(l,k)$ se superponen o no. En el último caso tenemos $2!2!13!$ muchas permutaciones diferentes (dos nuevos símbolos, ambos de los cuales puede ser ampliado en dos formas), en la ex $3! 12!$ formas (un nuevo símbolo para 3 diferentes $a_i a_j a_k$, aumentó $3!$ maneras. Del primer tipo se ${5 \choose 2}{3 \choose 2}$ pares, y el segundo, ${5 \choose 3}$ muchos.

Además, las condiciones $A(i,j)$, $B(i,j)$ puede ocurrir al mismo tiempo. (y de manera similar $A$ $C$ $B$ $C$ condiciones). Recopilación de todos estos juntos, y agregar a la anterior.

Y así sucesivamente. Esto podría ser demasiado complicado, pero es la primera cosa que se me ocurrió.

Answer 2

Hay una repetición tridimensional para esto: que $f(x,y,z)$ es el número de combinaciones de $x$ a, b de $y$ y $z$ c de modo que no hay dos idénticas letras son adyacente y la primera letra son una "a".

$$f(1,0,0)=1$$ $$f(x,y,z)=f(y,z,x-1)+f(z,x-1,y)\quad\text{if }x>0\text{ and }0\text{ otherwise.}$$

Así que un simple código JavaScript para calcular esto es:

function f(x,y,z)
{
    var mem=[];
    function f2(bag)
    {
        if( bag in mem ) return mem[bag];
        if( bag.toString()=="1,0,0" ) return 1;
        if( bag[0]>0 ) return mem[bag]=f2([bag[1],bag[2],bag[0]-1])+f2([bag[2],bag[0]-1,bag[1]]);
        else return 0;
    }
    return f2([x,y,z])+f2([y,z,x])+f2([z,x,y]);
}
var ans=f(5,5,5);
alert(ans); // which gives 7188 but I'm not sure if that's correct.

Answer 3

Hice un algoritmo y la misma respuesta como user1537366, luego buscar una fórmula general y aquí es

Answer 4

Mejor enfoque creo que solo uso recursividad y unas cuantas funciones apropiadas:

$f(5,5,5) = a(4,5,5) + b(5,4,5) + c(5,5,4)$

$a(a,b,c) = b(a,b-1,c) + c(a,b,c-1)$ etc...

$a(-1,b,c) = 0$ etc..

Donde $f(a,b,c)$ es el número total de secuencias con $a$ de un etc..

$a(a,b,c)$ es el número de secuencias donde la última letra es 'a' y se puede usar $a$ a, $b$ b etc..

Otra opción sería utilizar la inclusión y exclusión, pero que tendría algunas funciones muy difíciles para los duplicados.

Answer 5

Según secuencias con elementos adyacentes desiguales, el número de secuencias de una de, b y c que comprende $n$ de cada letra que no hay dos cartas idénticas son adyacentes es: $$3\left(\sum_{v=0}^{\lfloor(s-1)/2\rfloor}{s-1\choose 2v}{2v\choose v}{s+v-1\choose v+1}2^{s-1-2v}+\sum_{v=0}^{\lfloor s/2\rfloor}{s\choose 2v}{2v\choose v}{s+v-1\choose v}2^{s-2v}\right)$ $

El truco fundamental era tener en cuenta que los bloques de b y c entre consecutivos de una son el alternarse.