Cuántas palabras con $2n$ cartas puede ser creado si tengo un alfabeto con $n$ letras y cada una de las letras tiene que ocurrir exactamente dos veces en la palabra, pero no hay dos consecutivos letras son iguales?
Gracias!
Respuestas
¿Demasiados anuncios?
universalset
Puntos
6716
No es simple y cerrada fórmula para esto (creo que no sabe cerrado fórmula en todos), pero se puede dar una fórmula como una suma mediante la inclusión-exclusión.
Primero considere la posibilidad de tales ordenamientos, donde las parejas de cartas idénticas son distinguibles. A continuación, $\displaystyle \sum_{k=0}^n (-1)^k2^k(2n-k)!\binom{n}{k}$ da el número de tales órdenes por medio de la inclusión-exclusión (hay $(2n-k)!$ formas para $k$ dado pares de estar juntos (por la fusión de los pares de elementos simples) y el resto arbitrariamente ordenado, $2^k$ maneras de ordenar dentro de los dados y los pares de $\binom{n}{k}$ formas de seleccionar los $k$ pares). Dividiendo por $2^n$ a eliminar el orden de los pares de elementos idénticos, podemos obtener la fórmula $\displaystyle \frac{1}{2^n}\sum_{k=0}^n (-1)^k2^k(2n-k)!\binom{n}{k}$.
mjqxxxx
Puntos
22955
Como se señaló en los comentarios, esta secuencia aparece en la OEIS (A114938), y es un caso especial de una más general, resultado que se encuentra en otra parte de este sitio (por ejemplo, aquí y aquí).
La OEIS da el resultado como una suma: $$ A_{n}=\sum_{k=0}^{n}\frac{(-1)^{n-k}(n+k)!}{2^k}{{n}\choose{k}}\\=\frac{1}{2^n}\sum_{k=0}^{n}(-2)^k(2n-k)!{{n}\choose{k}}, $$ donde la segunda versión se obtiene a partir de la primera, cambiando $k\rightarrow n-k$ en la suma. Para obtener esa de la expresión más general, podemos escribir $$A_{n}=\int_0^\infty (q_2(x))^n \, \exp(-x)\,dx,$$ donde $$q_2(x) = \sum_{i=1}^{2} \frac{(-1)^{2-i}}{i!} {2-1 \choose i-1}x^i=\frac{1}{2}x(x-2);$$ así $$ A_n=\frac{1}{2^n}\int_{0}^{\infty}x^n(x-2)^ne^{-x}dx=\frac{1}{2^n}\sum_{k=0}^{n}(-2)^k{{n}\choose{k}}\int_{0}^{\infty}x^{2n-k}e^{-x}dx, $$ donde el binomio de expansión fue aplicado a $(-2+x)^n$. Ya que fácilmente se puede comprobar que el $\int_{0}^{\infty}x^a e^{-x}dx=a!$ (por repetir la integración por partes, por ejemplo), las dos expresiones coinciden.
Zulu
Puntos
1469
Tenemos 2n posiciones para llenar, le permite llenar dos posiciones con una letra.
Disponemos de n pares de letras dobles. Para el primer par de letras dobles que tenemos (2n-2)(2n-3) posiciones posibles. Esto es debido a que primero nos puso la carta en una posición no en los laterales, y la otra carta, en el resto de posiciones que no están próximos a nuestra carta.
[editar] Ahora vamos a proceder de la siguiente carta: Tenemos 2n-2 posiciones a la izquierda para llenar con otra carta, utilice el procedimiento anterior.
Seguir haciendo esto, en total n veces, para llegar a todas las palabras. Funciona porque no importa dónde ponemos una letra (y su doble) para el resto de las letras.
[EDITAR] se me ha olvidado una cosa:Las palabras de la forma a _ _ _. La adición de ellos se obtiene: Para n 0 para obtener el producto de: (2n-2)(2n-3) Y para añadir a esto :
n de los tiempos " Por la n-1 a 2 se obtiene el producto de: (2n-2)(2n-3) '
Esto da para n=3 : 30 palabras.
Para n=4 : 840
Suraj M S
Puntos
1462
primero de todo, si usted quiere encontrar el número de palabras en el que no hay dos mismas letras son iguales, entonces es equivalente a encontrar el número total de palabras que se pueden hacer con las letras menos el número de palabras en el cual consecutivos cartas están presentes.
usted puede encontrar fácilmente el total de palabras que se pueden hacer con las letras de la a $$\frac{2n!}{(2!)^n}$$ ahora a encontrar el no. de palabras en el que las cartas son consecutivas.
inicialmente considerar un par de $xx$ está formado en la palabra con ninguna otra mismos elementos consecutivos. Consideremos el conjunto a $xx$ como un único elemento que es libre para recorrer a cualquier posición entre el resto de los $2n-2$ elementos.
entonces el conjunto $xx$ puede ser colocado en cualquiera de las $2n-1$ posiciones. Al mismo tiempo, el resto de $2n-2$ elementos en sí mismo puede ser reorganizado $\frac{(2n-2)!}{(2!)^{n-1}}$
por lo tanto, el total no. de maneras en que un par de letras puede ser consecutivos es $$\frac{(2n-2)!*(2n-1)}{(2!)^{n-1}}$$ $$= \frac{(2n-1)!}{(2!)^{n-1}}$$ ahora extender esto para más número de conjuntos de $1$$n$.
usted encontrará la respuesta final para como $k$ va desde $1$ $\to$ $n$ es $$ \frac{2n!}{(2!)^n}-\sum \frac{(2n-k)!}{(2!)^{n-k}}$$
