Arreglos sin dos vocales consecutivas

Question

En general, afirmamos que existen ${r-wn - (n-1) \choose (n-1)}$ formas de distribuir r bolas idénticas en n cajas distintas con al menos w bolas en cada caja. Teniendo esto en cuenta, ¿cuántas formas hay de ordenar las 26 letras del alfabeto de manera que no haya dos vocales consecutivas? He podido obtener la respuesta utilizando la fórmula ${n-k + 1 \choose k}$ donde hay k bolas y n cajas pero tengo dos problemas:

1) No entiendo muy bien por qué esta fórmula es equivalente a la mencionada al principio de esta pregunta;

2) No estoy seguro de cómo en una solución a este problema la respuesta ${21 - 4 + (6-1) \choose 6-1}$ se llegó a.

¿Podría alguien aclarar cómo encajan todos estos elementos? Gracias de antemano.

Answer 1

Primero pon $w$ bolas en cada uno de los $n$ cajas; eso consume $wn$ de las bolas, dejándote $r-wn$ distribuir arbitrariamente entre los $n$ cajas. Según la norma estrellas y barras el número de maneras de distribuir $m$ bolas indistinguibles entre $n$ cajas distinguibles es

$$\binom{m+n-1}{n-1}\;,\tag{1}$$

y en este caso $m=r-wn$ por lo que en este caso obtenemos

$$\binom{r-wn+n-1}{n-1}\;.$$

(Observa que tienes un signo mal en la expresión al principio de tu pregunta).

Recordemos ahora la identidad $\binom{n}k=\binom{n}{n-k}$ y aplicarlo a $(1)$ para obtener

$$\binom{m+n-1}{n-1}=\binom{m+n-1}m\;.\tag{2}$$

Así, el lado derecho de $(2)$ también da el número de formas de distribuir $m$ bolas indistinguibles entre $n$ cajas (y tiene otro error de signo: su $n-k+1$ debe ser $n+k+1$ ). En el caso $m=r-wn$ en la que partimos del mínimo de $w$ bolas en cada caja, se convierte en

$$\binom{r-wn+n-1}{r-wn}\;.$$

En el problema concreto que nos ocupa, sin embargo, no se puede utilizar ninguno de los dos sin hacer algunos ajustes. Tiene que $6$ cajas, a saber, la $4$ ranuras entre vocales adyacentes y las ranuras de los dos extremos, y $21$ bolas. Cada una de las $4$ Las casillas del centro deben recibir al menos una bola, pero cualquiera de las casillas de los extremos, o ambas, pueden dejarse vacías. Por lo tanto, debe empezar colocando una bola en cada una de las $4$ cajas centrales, dejando $17$ bolas que se distribuirán arbitrariamente entre los $6$ cajas. Cualquier expresión en $(2)$ ya se puede utilizar: hay $$\binom{17+6-1}{6-1}=\binom{22}5=\binom{22}{17}=\binom{17+6-1}{17}$$ formas de distribuir las consonantes entre las vocales, ignorando qué consonante es cada una. Por supuesto, esto debe multiplicarse por $5!21!$ para tener en cuenta el orden de las vocales y consonantes dentro de sus respectivos conjuntos de posiciones en la cadena.