Me estoy preguntando cómo calcular el número de alteraciones de la palabra de la BOTELLA. Entiendo como hacer la fórmula para alteraciones ya. Mi problema es, ¿qué hacer con la repetición de letras. Obviamente, voy a estar contando si tengo que hacer la típica fórmula. Me hace pensar que es el número de alteraciones con la letra T en su espacio original, pero no estoy seguro. Alguien puede ayudar, como me estoy preguntando si estoy supone que el uso de la TARTA de resolver esto. Gracias.
Respuestas
¿Demasiados anuncios?
N. Shales
Puntos
51
La siguiente respuesta es bastante largo, pero presenta un método general para la solución de problemas de este tipo.
La respuesta a tu pregunta puede ser declarada de manera muy sucinta
$$\frac{1}{2!}\int_{0}^{\infty}e^{-x}\left(x-1\right)^4\left(x^2-4x+2\right)\, dx=84\tag{*}\label{*}$$
Pero, ¿cómo llegamos allí?
Un increíblemente versátil enfoque que abarca los problemas de permutaciones con restricciones de posiciones es el de la torre de polinomios.
El primer paso es reformular el problema en términos de un 2-matriz bidimensional llamado "ajedrez de la junta" o simplemente un "consejo". A lo largo de la parte superior y lateral de la junta son los objetos (que son temporalmente hecho distinto) a ser permutados.
En la junta vamos a colocar no atacar, idénticos "torres" que especificar una permutación. A continuación, podemos atender a nuestros restricciones en posición de canas prohibidos plazas. Esta colección de cuadrados grises forma lo que se llama el prohibido subboard.
En lugar de explicar a considerar cómo la junta directiva para su problema sería
\begin{array}{c|c|c|c|c|c|c|} &\textbf{B}&\textbf{O}&\textbf{T}_\mathbf{1}&\textbf{T}_\mathbf{2}&\textbf{L}&\textbf{E}\\ \hline \text{B}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}&&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}\\ \hline \text{O}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}\\ \hline \text{T}_1&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&&\\ \hline \text{T}_2&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&&\\ \hline \text{L}&&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}\\ \hline \text{E}&\bbox[white,15px]{\phantom{H}}&&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}\\ \hline\end{array}
A lo largo de la parte superior son sus letras, en sus posiciones originales y a lo largo del lado están las cartas a ser permutados, vamos a la posición 6 torres, 1 en cada fila evitar plazas gris.
Ponemos torres para las posiciones horizontales de los grajos en cada fila dar a la nueva ubicación de la letra de esa fila. El gris "prohibido" plazas claramente impedir que las cartas se colocan en sus lugares originales, y en el caso de los dos Ts ni está permitido en su propia posición original o la de su gemelo. por ejemplo, la siguiente disposición de las torres
\begin{array}{c|c|c|c|c|c|c|} &\textbf{B}&\textbf{O}&\textbf{T}_\mathbf{1}&\textbf{T}_\mathbf{2}&\textbf{L}&\textbf{E}\\ \hline \text{B}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}&\Huge\unicode{x265c}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}\\ \hline \text{O}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\Huge\unicode{x265c}&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}\\ \hline \text{T}_1&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&\Huge\unicode{x265c}&\\ \hline \text{T}_2&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&\bbox[grey, 15px]{\phantom{\Huge H}}&&\Huge\unicode{x265c}\\ \hline \text{L}&\Huge\unicode{x265c}&\bbox[white,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}&\bbox[white,15px]{\phantom{\Huge H}}\\ \hline \text{E}&\bbox[white,15px]{\phantom{H}}&\Huge\unicode{x265c}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[white,15px]{\phantom{H}}&\bbox[grey,15px]{\phantom{\Huge H}}\\ \hline\end{array}
representa la validez de permutación
\begin{array}{c|c|c|c|c|c|c} \text{Original positions}&\textbf{B}&\textbf{O}&\textbf{T}_\mathbf{1}&\textbf{T}_\mathbf{2}&\textbf{L}&\textbf{E}\\ \hline \text{Permutation}&\text{L}&\text{E}&\text{B}&\text{O}&\text{T}_1&\text{T}_2\end{array}
Bien, ahora que hemos establecido nuestro consejo, ¿cómo podemos usarlo para contar nuestras válido permutaciones?
Tenemos que hablar de la torre polinomios
Un estándar de la torre del polinomio es realmente una idea simple, si tenemos algún tablero de ajedrez de cualquier configuración, a continuación, la torre del polinomio para que la junta
$$R(x)=1+r_1x^1+r_2x^2+\ldots +r_kx^k+\ldots +r_nx^n$$
muestra el número de maneras en las $r_k$ que $k$ no atacar a los grajos se pueden colocar. Tenga en cuenta que $n$ es la dimensión más pequeña de la junta.
Para la plaza de las tablas de dimensión $n$ es fácil comprobar que
$$R(x) = \sum_{k=0}^{n}\binom{n}{k}^2k!\, x^k$$
por argumentando que podemos optar $k$ filas en las que el lugar $k$ torres en $\binom{n}{k}$ maneras, a continuación, organizar los $k$ torres en $n$ columnas horizontales en $\binom{n}{k}k!$ maneras.
Usted puede ver que su prohibido subboard se compone de cuatro $1\times 1$ plaza de juntas y un $2\times 2$ plaza de la junta y que estas tablas son todas tensión dialéctica (es decir: que no tienen en común las filas o columnas).
Cada una de las $1\times 1$ junta directiva tiene la torre del polinomio
$$1+x$$
y el $2\times 2$ junta directiva tiene la torre del polinomio
$$1+4x+2x^2$$
Sin mucho esfuerzo, podemos ver que si tenemos dos disparidad tableros $\mathscr{B_1}$ e $\mathscr{B_2}$ o subboards luego multiplicando su torre polinomios da a la torre del polinomio de la unión de las dos juntas
$$R_{\mathscr{B_1}}(x)R_{\mathscr{B_2}}(x)=R_{\mathscr{B_1}\cup\mathscr{B_2}}(x)$$
Así que la torre polinomio para toda prohibido subboard es
$$R_{\mathscr{S}}(x)=(1+x)^4(1+4x+2x^2)$$
Ahora, una vez que tenemos nuestra torre polinomio para el prohibido subboard queremos usarlo para contar las maneras en que nuestra torres puede ser colocado de manera que ninguno de ellos está en él.
Aquí es donde la inclusión-exclusión que viene. Si definimos los conjuntos de la torre ubicaciones
$$A_k=\text{rook placements where the rook in row }k\text{ is on the forbidden subboard}$$
En general prohibido subboard $\mathscr{S_g}$ con $n$ filas ($\le\text{number of columns}$) y la torre del polinomio
$$R_{\mathscr{S_g}}(x)=\sum_{k=0}^{n}r_kx^k\tag{1}\label{1}$$
Entonces tenemos que el número de colocaciones de los grajos, de modo que ninguno de los grajos en el subboard es:
$$|(A_1\cup A_2\cup\ldots\cup A_n)'|=$$ $$n!-\left(\sum_{i}|A_i|-\sum_{i_1<i_2}|A_{i_1}\cap A_{i_2}|+\ldots +(-1)^{n-1}|A_1\cap A_2\cap\ldots\cap A_n|\right)$$
Donde podemos ver que
$$\sum_{i}|A_i|=r_1(n-1)!$$ $$\sum_{i_1<i_2}|A_{i_1}\cap A_{i_2}|=r_2(n-2)!$$ $$\vdots$$ $$|A_1\cap A_2\cap\ldots\cap A_n|=r_n(n-n)!$$
También podemos ver que (desde $r_0=1$)
$$n! = r_0(n-0)!$$
así
$$|(A_1\cup A_2\cup\ldots\cup A_n)'|=$$ $$r_0(n-0)!-r_1(n-1)!+r_2(n-2)!-\ldots +(-1)^nr_n(n-n)!$$ $$=\sum_{k=0}^{n}(-1)^kr_k(n-k)!$$
Esto puede ser comparado con la torre polinomio $\eqref{1}$ para$\mathscr{S_g}$, de modo que todo lo que tenemos que hacer es reemplazar cada una de las $x^k$ con $(-1)^k(n-k)!$. Esto es una aceptable forma de calcular y si usted hace esto con su ejemplo, usted consigue
$$(1+x)^4(1+4x+2x^2)= 1+ 8 \, x+ 24 \, x^{2}+ 36 \, x^{3}+ 29 \, x^{4}+ 12 \, x^{5}+2 \, x^{6}$$ $$\implies|(A_1\cap A_2\cap A_3\cap A_4\cap A_5\cap A_6)'|$$ $$=6!- 8 \cdot 5!+ 24 \cdot 4! - 36\cdot 3! + 29 \cdot 2!- 12 \cdot 1!+2 \cdot 0!=168$$
recordando los dos T son en realidad idénticos dividimos por $2!$ dar $\bbox[yellow, 5px]{84}$.
Para hacer esta respuesta se parece al de la en la parte superior observamos que mediante la modificación de la torre polinomios de modo que tenemos
$$(x-1)^4(x^2-4x+2)\text{ instead of }(1+x)^4(1+4x+2x^2)$$
A continuación, la multiplicación de estos modificado polinomios cabo da
$$(x-1)^4(x^2-4x+2)=x^{6} - 8 \, x^{5} + 24 \, x^{4} - 36 \, x^{3} + 29 \, x^{2} - 12 \, x + 2$$
así que todo lo que tenemos que hacer para conseguir la inclusión-exclusión de la fórmula es reemplazar cada una de las $x^k$ con $k!$. Bien, si recordamos
$$\int_{0}^{\infty}e^{-x}x^k\, dx=k!$$
Para un entero no negativo,$k$,, a continuación, $\eqref{*}$ sigue inmediatamente.
Hay una excelente torre polinomio de solver que la salida de la norma que la torre del polinomio y el número de la torre ubicaciones que evitar que el usuario define subboard.
Para más información sobre la torre de los polinomios de una búsqueda en Internet le dará una gran cantidad de resultados o de un buen libro, ver John Riordan Introducton a la Combinatoria en la que dedica 2 capítulos enteros al tema.
Misha
Puntos
1723
Hay $\left\lfloor \frac{6!}{e}\right\rfloor = 265$ alteraciones de 6-element set, pero la aplicación de esta fórmula a las letras de "BOTELLA" tiene dos problemas:
Algunas de estas "alteraciones" mover la T en la cuarta posición a la tercera posición, o viceversa, o ambos, así que una vez que tome en cuenta, que ya no estás reales alteraciones.
De la validez de las alteraciones, cada uno se cuenta dos veces: si interruptor de los dos T, que es otra permutación de una $6$-element set, pero no debería ser diferente la alteración de las letras de la "BOTELLA".
Comencemos por fijar el primer problema. Hay tres casos:
- La falsa alteración en realidad intercambia las dos camisetas. Este caso es en bijection (por el intercambio de los dos T) con las permutaciones que se fijan tanto en T y volver loca a todo lo demás, así que hay $\left\lfloor \frac{4!}{e}\right\rfloor = 9$ de estos.
- La falsa alteración mueve el primer T para el segundo T del lugar, y el segundo T a otro de la primera T del lugar. Este caso es en bijection (por el intercambio de los dos T) con las permutaciones que fijan el segundo T y volver loca a todo lo demás, así que hay $\left\lfloor \frac{5!}{e}\right\rfloor = 44$ de estos.
- Mismo que el caso anterior, pero con el segundo T va a la primera T del lugar; también se $44$ de estos.
Esto nos deja con $265-44-44-9 = 168$ real alteraciones.
El segundo problema es fácil de solucionar; ahora podemos dividir por $2$ y consigue $84$ como nuestra respuesta final.
(También me engañó y confirmado esto por fuerza bruta en Mathematica.)
Joffan
Puntos
7855
Elija dos ubicaciones válidas para las letras $T$, $\binom 42$ maneras. Las letras que se inició en esos lugares que son "libres", los otros dos son "no libre".
Elija una ubicación para la primera no libre de la carta de las $3$ disponible para ello. Dos casos:
- elija uno de los dos $T$ posiciones de inicio, en cuyo caso el otro controlados carta tiene sólo dos opciones, o
- elija los otros no libre de la carta de la posición de inicio, en el que caso de que la carta es libre.
Restante $n$ libre de las letras van como $n!$.
Sobre todo tenemos $\binom 42(2\cdot2\cdot 2! + 1\cdot 3!) = 6\cdot (8+6) = 84$.
Steampunk Solutions Inc
