21.3: Contar permutaciones
- Page ID
- 117967
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Porque\(\vert A \vert = n\text{,}\) hay\(n!\) permutaciones en\(A\text{.}\)
- Prueba
-
Prueba informal.
Queremos contar el número de formas de construir una lista ordenada de los\(n\) elementos de\(A\text{.}\) Hay\(n\) formas de elegir el primer elemento de la lista,\(n-1\) formas de elegir el segundo,\(n-2\) formas de elegir el tercero, y así sucesivamente, terminando en una sola forma para elegir la Regla\(n^{th}\text{.}\) Por la Multiplicación, hay\ comenzar {ecuación*} n\ cdot (n - 1)\ cdot (n - 2)\ cdot\ cdot\ cdots\ cdot 1 = n! \ end {equation*}
formas de construir tal lista.Prueba formal.
Por inducción.Estuche base\(n=1\).
Si\(\vert A \vert = 1\text{,}\) entonces\(A\) consiste en un solo elemento, digamos Solo\(A = \{a\}\text{.}\) hay una posible permutación de\(A\text{,}\) y esa es la función de identidad\(\text{id}_A: A \rightarrow A\) definida por\(\text{id}_A(a) = a\text{.}\) Así, hemos verificado que hay\(1! = 1\) permutación de\(A\text{.}\)Paso de inducción.
Dejar\(k \ge 1\) ser un entero fijo. Nuestra hipótesis de inducción es asumir que si\(B\) hay algún conjunto con\(\vert B \vert = k\) elementos, entonces hay\(k!\) permutaciones en\(B\text{.}\) Queremos usar esta hipótesis para probar que si\(A\) es un conjunto con\(\vert A \vert = k+1\) elementos, entonces hay\((k+1)!\) permutaciones en\(A\text{.}\)Escribir\(A = \{ a_0, a_1, \ldots , a_k \}\) y\(B = \{ a_1, a_2, \ldots , a_k \}\text{.}\) Entonces\(B\) es un subconjunto de\(A\) que contiene\(k\) elementos, y así por nuestra hipótesis de inducción hay\(k!\) permutaciones en\(B\text{.}\) Para cada tal permutación de\(B\text{,}\) podemos construir\(k+1\) permutaciones de\(A\) “insertando” \(a_0\)en diferentes posiciones en la lista de salida. Por ejemplo, considere cómo la permutación de identidad activada se\(B\) puede convertir en\(k+1\) diferentes permutaciones en\(A\) — ver Figura\(\PageIndex{1}\).
Figura\(\PageIndex{1}\): Insertar un elemento extra en varias posiciones de una permutación para crear nuevas permutaciones más largas. Cada una de las\(k!\) permutaciones de\(B\) puede ser utilizada para construir\(k+1\) permutaciones de\(A\text{,}\) la misma manera que tenemos arriba para la permutación de identidad de\(B\text{.}\) Así que tenemos en\((k+1) \cdot k! = (k+1)!\) permutaciones totales de\(A\text{,}\) como se requiera.
Al aplicar el método de inducción matemática en la prueba formal, comenzamos nuestro caso base en\(n = 1\text{.}\) Pero la fórmula\(n!\) sigue siendo válida para el número de permutaciones del conjunto vacío. En este caso,\(n = 0\) y así\(n! = 0! = 1\) por la Convención 21.1.1. Y efectivamente hay exactamente una permutación del conjunto vacío: la función vacía. (Ver Declaración 2 de la Proposición 12.1.1.)
Cada una de las pruebas proporcionadas para el Teorema\(\PageIndex{1}\) arriba contiene una idea que es de uso práctico en el conteo de colecciones.
- En la prueba informal, se utilizó la Regla de Multiplicación para contar el número de formas de construir una lista ordenada, donde las tareas en la construcción son elegir los elementos de la lista uno a la vez. (Usamos este pensamiento similar a menudo en el Capítulo 20, aunque no conectamos explícitamente la Regla de Multiplicación a listas ordenadas).
- En la prueba formal, utilizamos la idea de “insertar” un objeto en una lista ordenada existente para crear una nueva lista ordenada.
Para una clase de veinte alumnos, en cuántos órdenes diferentes puede un profesor entregar pruebas marcadas:
- ¿En total?
- Si la prueba de Karishma debe ser devuelta primero?
- ¿Si las pruebas de Elizabeth y Ruijing no pueden seguirse inmediatamente unas a otras?
Solución
- Un orden de distribución de pruebas es lo mismo que una permutación de los alumnos en la clase, por lo que hay\(20!\) diferentes órdenes de handback (aproximadamente\(2.4\) quintillones).
- Esto es solo el número de formas de ordenar los diecinueve trabajos de los estudiantes restantes, que es\(19!\) (aproximadamente\(122\) cuadrillón).
- Es más fácil contar las formas en que se siguen entre sí. Una forma de hacerlo es la siguiente. Retira la prueba de Elizabeth de la pila. Ahora hay\(19!\) formas de ordenar los diecinueve papeles restantes. Hay dos formas de volver a insertar la prueba de Elizabeth en cualquier orden de este tipo, ya sea inmediatamente antes o después del papel de Ruijing. Entonces hay\(2 \cdot 19!\) ordenamientos que no queremos. Por lo tanto, aplicar la Regla de Resta arroja respuesta
\ begin {ecuación*} 20! - ¡2\ cdot 19! = 20\ cdot 19! - ¡2\ cdot 19! = 18\ cdot 19! \ texto {.} \ end {ecuación*}
Para un alfabeto\(\Sigma\) con\(\vert \Sigma \vert = n\text{,}\) cuántas palabras\(\Sigma^{\ast}\) contiene cada elemento del alfabeto exactamente una vez?
Solución
Aquí solo queremos ordenar todos los elementos de\(\Sigma\) en una palabra, entonces la respuesta es\(n!\text{.}\)
- Comparar.
-
Ver Ejemplo Trabajado 20.3.11.
Ejemplo\(\PageIndex{2}\) Trabajado justifica la convención\(0! = 1\text{,}\) ya que si\(\vert \Sigma \vert = 0\text{,}\) entonces\(\Sigma^{\ast}\) contiene exactamente una palabra: la palabra vacía\(\emptyset\text{.}\) Y en este caso es vacuamente cierto que\(\emptyset\) contiene cada elemento de\(\Sigma\) exactamente una vez.
Si\(\vert A \vert = n\text{,}\) ¿cuántos pedidos totales diferentes\(A\) existen?
Solución
Especificar un pedido total en\(A\) realmente solo significa ordenar los elementos de\(A\text{:}\)
\ begin {equation*} a_1\ le a_2\ le a_3\ le\ cdots\ le a_n.\ end {equation*}
Así que hay pedidos totales\(n!\) posibles.
¿Cuántos patrones de color diferentes podemos obtener colocando tres botellas rojas y cinco botellas azules en una repisa? (Supongamos que las botellas son indistinguibles excepto por el color.)
Solución
Usemos la Regla de División, donde primero contaremos una colección más estructurada. Si las botellas del mismo color fueran distinguibles entre sí, tendríamos\(8!\) formas de alinearlas en la repisa. Asumiendo indistinguibilidad, ahora consideramos que dos pedidos con el mismo patrón de color pero mezclados con botellas rojas y/o azules son equivalentes. Por ejemplo, los dos ordenamientos
\ begin {reunir*}\ mathrm {R} _1\;\ mathrm {B} _1\;\ mathrm {B} _2\;\ mathrm {R} _2\;\ mathrm {R} _3\;\ mathrm {B} _3\;\ mathrm {B} _4\;\ mathrm {B} _5,\\ mathrm {R} _2\;\ mathrm {B} _5\;\ mathrm {B} _3\;\ mathrm {R} _1\;\ mathrm {R} _3\;\ mathrm {B} _1\;\ mathrm {B} _4\;\ mathrm {B} _2,\ end {reunión*}
de las botellas distinguibles crean el mismo patrón de color, y por lo tanto son equivalentes. Una vez determinadas las posiciones de las botellas rojas y azules, podemos permutar los rojos (\(3!\)vías) y azules (\(5!\)vías) de forma independiente, por lo que cada clase de equivalencia dentro de la colección de pedidos de botellas distinguibles contiene pedidos\(3! \cdot 5!\) equivalentes. Aplicando la Regla de División, llegamos a
\ comenzar {ecuación*}\ dfrac {8!} {3! \ cdot 5!} =\ dfrac {8\ cdot 7\ cdot 6} {3\ cdot 2} = 56\ end {ecuación*}
posibles patrones de color.
¿Cuántos arreglos diferentes de asientos de diez personas alrededor de una mesa redonda son posibles, si no se considera que nadie está a la “cabeza” o “pie” de la mesa?
Solución
Solución. 1
Usemos la Regla de División, donde primero contaremos una colección más estructurada. Hay\(10!\) formas de alinear a la\(10\) gente. Envolver el final de la línea alrededor para cumplir con el principio forma una disposición de asientos circulares. Pero “rotar” alrededor de la línea (\(10\)posibles rotaciones) produce una disposición de asientos circulares equivalente. Entonces la respuesta es
\ comenzar {ecuación*}\ dfrac {10!} {10} = ¡9! \ texto {.} \ end {ecuación*}
Solución. 2
Obligar a una persona en particular a ser siempre el “comienzo” de la disposición de los asientos, sin importar en qué asiento físico estén sentados, e ignorando el hecho de que una disposición circular realmente no tiene “comienzo”. Entonces hay\(9!\) formas de organizar a\(9\) las personas restantes alrededor de la mesa comenzando desde el asiento a la izquierda de la persona “inicio”.