Considere la siguiente secuencia de letras: a,b,c,d,e,f,g,h,i,j,k,l,m,n. Cuántas formas hay de ordenar las letras en conjuntos de cualquier longitud (incluido el conjunto vacío) de manera que ninguna secuencia contenga letras consecutivas.
Respuestas
¿Demasiados anuncios?
leoinfo
Puntos
3364
Puede contarlos utilizando la función principio de inclusión-exclusión :
(Por conveniencia utilizaré números $1,...,14$ en lugar de letras) Dejemos que $X$ sea el conjunto de todas las secuencias de letras de cualquier longitud, sin restricciones. Entonces $$|X|=\sum_{k=0}^{14}k!\binom{14}{k}$$ Ahora denota $A_i$ , $i=1,...,13$ sea el conjunto de todas las secuencias de este tipo que incluyen tanto $i$ y $i+1$ . Entonces $$|A_i|=\sum_{k=2}^{14}k!\binom{12}{k-2}$$ Como cualquier secuencia de este tipo tiene una longitud mínima de 2, elige los elementos restantes y ordénalos.
Ahora encuentra $|A_i\cap A_j|$ para $i<j$ Hay dos opciones: si $j=i+1$ entonces $|A_i\cap A_{i+1}|=\sum_{k=3}^{14}k!\binom{11}{k-3}$ y si $j\neq i+1$ entonces $|A_i\cap A_j|=\sum_{k=4}^{14}k!\binom{10}{k-3}$ .
Continúe en la forma (es bastante tedioso, pero funciona).
Al final, el número disered será $$|X|-\sum_{k=1}^{13}(-1)^{k+1}\left(\sum_{1\leq i_1<...<i_k\leq 13}|A_{i_1}\cap...\cap A_{i_k}|\right)$$
Voy a reemplazar el conjunto $\{a,b,\dots,n\}$ por el conjunto $[14]=\{1,2,\dots,14\}$ . Primero contaré los $k$ -subconjuntos de elementos de $[14]$ que no contengan dos enteros consecutivos, donde $0\le k\le 14$ . Imagina que he elegido un subconjunto de este tipo; llámalo $K$ . Escribo la secuencia $1,2,\dots,14$ y luego reemplazo cada miembro de $K$ con una barra y cada miembro de $[14]\setminus K$ con una estrella. Dejemos que $x_0$ sea el número de estrellas antes de la primera barra; para $i=1,\dots,k-1$ dejar $x_i$ sea el número de estrellas entre el $i$ -y $(i+1)$ -st bares; y dejar que $x_k$ sea el número de estrellas después del $k$ -en la barra. Los compases no pueden ocupar positivos consecutivos, por lo que $x_i\ge 1$ para $i=1,\dots,k-1$ , y por supuesto $\sum_{i=0}^kx_i=14-k$ . Por la habitual estrellas y barras cálculo hay $$\binom{\big((14-k)-(k-1)\big)+(k+1)-1}{(k+1)-1}=\binom{15-k}k$$ tales secuencias de estrellas y barras y por lo tanto $\binom{15-k}k$ $k$ -subconjuntos de elementos de $[14]$ sin miembros consecutivos. Cada uno de ellos puede, por supuesto, permutarse en $k!$ formas, por lo que el número deseado es
$$\begin{align*} \sum_{k=0}^{14}k!\binom{15-k}k&=\sum_{k=0}^7k!\binom{15-k}k\\ &=\sum_{k=0}^7\frac{(15-k)!}{(15-2k)!}\\ &=\frac{15!}{15!}+\frac{14!}{13!}+\frac{13!}{11!}+\frac{12!}{9!}+\frac{11!}{7!}+\frac{10!}{5!}+\frac{9!}{3!}+\frac{8!}{1!}\\\\ &=140,451\;. \end{align*}$$
