Sección 2.6 Permutaciones y Combinatoria
¶Permutaciones Sea \(A\) un conjunto de cardinal \(n\) y \(r\in\mathbb{N}^*\text{,}\) tal que \(r\leq n\text{.}\)
Se define
\begin{equation*}
\mathcal{P}_{r}(A)=\{(a_{1},a_{2},\ldots,a_{r})\in A\times A\times\cdot
\cdot\cdot\times A\quad|\quad\text{con }a_{i}\neq a_{j}\text{ si }i\neq j\},
\end{equation*}
La interrogante que surge es ¿Cuál es el cardinal de \(\mathcal{P}_{r}(A)\text{?}\)
Sea \(A=\{a,b,c,d\}\text{.}\) Luego
\begin{equation*}
\begin{array}[c]{l}
\mathcal{P}_{1}(A)\amp =\amp\{(a),(b),(c),(d)\},\\
\mathcal{P}_{2}(A)\amp =\amp \{(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),\\
\amp \amp \quad ...(c,a),(c,b),(c,d),(d,a),(d,b),(d,c)\},
\end{array}
\end{equation*}
Así, se obtiene que
\begin{equation*}
P_{2}^{4}=\#(\mathcal{P}_{2}(A))=12.
\end{equation*}
Continuando:
\(\mathcal{P}_{3}(A)=\{(a,b,c),(a,c,b),(a,b,d),\ldots\}\text{,}\) luego
\begin{equation*}
P_{3}^{4}=\#(\mathcal{P}_{3}(A))=24.
\end{equation*}
\(\mathcal{P}_{4}(A)=\{(a,b,c,d),(a,b,d,c),(a,c,b,d),(a,c,d,b),\ldots\}\text{,}\) y
\begin{equation*}
P_{4}^{4}=\#(\mathcal{P}_{4}(A))=24.
\end{equation*}
Teorema 2.6.2
Sea \(A\) un conjunto con \(n\) elementos entonces número de permutaciones de \(n\) elementos sobre \(r\leq n\) es
\begin{equation*}
P_{r}^{n}=\frac{n!}{(n-r)!}=\#(\mathcal{P}_{r}(A)).
\end{equation*}
Ahora si \(n= 4\text{,}\) veamos los siguientes cálculos:
-
Si \(r=1\text{,}\) entonces:
\begin{equation*} \frac{4!}{(4-1)!}=\frac{4!}{3!}=4. \end{equation*} -
Si \(r=2\text{,}\) entonces:
\begin{equation*} \frac{4!}{(4-2)!}=\frac{4!}{2!}=12. \end{equation*} -
Si \(r=3\text{,}\) entonces:
\begin{equation*} \frac{4!}{(4-3)!}=\frac{4!}{1!}=24. \end{equation*} -
Si \(r=4\text{,}\) entonces:
\begin{equation*} \frac{4!}{(4-4)!}=\frac{4!}{0!}=24. \end{equation*}
Ejemplo 2.6.3
En cada uno de los siguiente caso considere número de cuatro dígitos
¿Cuántos números con todos sus dígitos distintos se pueden construir?
¿Cuántos números pares con todos sus dígitos distintos se pueden construir?
a) Como el primer dígito no pude ser cero tenemos nueve posibilidades y de los otro nueve dígito ordeno 3 luego
\begin{equation*}
9P_{3}^{9}=9\frac{9!}{6!}=4536
\end{equation*}
b) Tenemos dos posibilidades, la primera es que el número tenga en el dígito de las unidades un cero.
\begin{equation*}
P_{3}^{9}=\frac{9!}{6!}=504
\end{equation*}
La segunda posibilidad es que no sea cero, luego hay que tener cuidado con la cifra de la unidades de mil, ya que no puede ser cero. Para la cuenta argumentamos del siguiente modo, considero que la cifra de las unidades es 2 luego tengo nueve dígitos incluido el cero
\begin{equation*}
8P_{2}^{8}=8\frac{8!}{6!}=224
\end{equation*}
al repetir la cuenta para 4,6,8
\begin{equation*}
8P_{2}^{8}+8P_{2}^{8}+8P_{2}^{8}=3\cdot224
\end{equation*}
La cantidad total es
\begin{equation*}
P_{3}^{9}+8P_{2}^{8}+8P_{2}^{8}+8P_{2}^{8}+8P_{2}^{8}=504+4\cdot224=1400
\end{equation*}
Subsección Ejercicios
Repita el ejemplo anterior para números de dos dígitos y después para tres dígitos
Ejemplo 2.6.4
Usando sólo los siguientes dígitos 1,2,3,4,6,8,9. ¿Cuántos números de cuatro dígitos distintos se pueden construir menores que 4000?
Como los números tiene que ser menores que 4000, luego el dígito de las unidades de mil debe ser 1,2,3 por lo tanto, si es 1 tenemos
\begin{equation*}
P_{3}^{6}=\frac{6!}{3!}=120
\end{equation*}
que es el mismo valor para 2 y 3. Luego el total es
\begin{equation*}
P_{3}^{6}+P_{3}^{6}+P_{3}^{6}=3P_{3}^{6}=360
\end{equation*}
Combinatoria
Sea \(A\) un conjunto de cardinal \(n\) y \(r\in\mathbb{N}\text{,}\) tal que \(r\leq n\text{.}\)
Se define
\begin{equation*}
\mathcal{C}_{r}(A)=\{B\subseteq A\quad|\quad\#(B)=r\}.
\end{equation*}
La interrogante que surge es ¿Cuál es el cardinal de \(\mathcal{C}_{r}(A)\) ?.
Ejemplo 2.6.5
Sea \(A=\{a,b,c,d\}\text{.}\) Determine por extensión \(\mathcal{C}_{r}(A)\) y su cardinal
Para los primeros caso lo podemos hacer por extensión
\begin{equation*}
\begin{array}[c]{l}
\mathcal{C}_{0}(A)=\left\{ \phi\right\} ,\\
\mathcal{C}_{1}(A)=\{\left\{ a\right\} ,\left\{ b\right\} ,\left\{
c\right\} ,\left\{ d\right\} \},\\
\mathcal{C}_{2}(A)=\{\left\{ a,b\right\} ,\left\{ a,c\right\} ,\left\{
a,d\right\} ,\left\{ b,c\right\} ,\left\{ b,d\right\} ,\left\{
c,d\right\} \},
\end{array}
\end{equation*}
Así, se obtiene que
\begin{equation*}
C_{2}^{4}=\#(\mathcal{C}_{2}(A))=6.
\end{equation*}
Para el siguiente caso tenemos que \(\mathcal{C}_{3}(A)=\{\left\{ a,b,c\right\} ,\left\{ a,b,d\right\} ,\left\{ a,c,d\right\} ,\left\{ b,c,d\right\} \}\text{,}\) luego
\begin{equation*}
C_{3}^{4}=\#(\mathcal{C}_{3}(A))=4.
\end{equation*}
Finalmente \(\mathcal{C}_{4}(A)=\{\{a,b,c,d \}\}\text{,}\) con lo cual obtenemos
\begin{equation*}
C_{4}^{4}=\#(\mathcal{C}_{4}(A))=1.
\end{equation*}
Teorema 2.6.6
Sea \(A\) un conjunto con \(n\) elementos entonces número de combinatoria de \(n\) elementos sobre \(r\leq n\) es
\begin{equation*}
C_{r}^{n}=\frac{n!}{(n-r)!\cdot r!}=\#(\mathcal{C}_{r}(A)).
\end{equation*}
Ejemplo 2.6.7
En un juego de azar tenemos que escoger 12 números para formar un cartón de un total de 30 números.
¿Cuántos cartones distintos se pueden fabricar?
\begin{equation*}
C_{12}^{30}=\left(
\begin{array}[c]{l}
30\\ 12
\end{array}\right) =\frac{30!}{18!\cdot12!}=86\,493\,225
\end{equation*}
Ejemplo 2.6.8
Usando sólo los siguientes dígitos 1,2,3,4,6,8,9. ¿Cuántos números pares de cuatro dígitos distintos se pueden construir menores que 4000?
Como los números tiene que ser menores que 4000, luego el dígito de las unidades de mil debe ser 1,2,3 por lo tanto, si es 1 tenemos puede terminar en 2,4,6,8
\begin{equation*}
C_{1}^{4}P_{2}^{5}=4\frac{5!}{3!}=80
\end{equation*}
que es el mismo valor para 3.
Pero para 2 tenemos que puede terminar en 4,6,8
\begin{equation*}
C_{1}^{3}P_{2}^{5}=3\frac{5!}{3!}=60
\end{equation*}
Luego el total es
\begin{equation*}
2C_{1}^{4}P_{2}^{5}+C_{1}^{3}P_{2}^{5}=220
\end{equation*}
Permutaciones con Repetición
Teorema 2.6.9
Sean \(R\) colores tales que hay \(n_{i}\) repetidos de color \(i\text{,}\) donde \(n=n_{1}+n_{2}+\cdot\cdot\cdot+n_{R}\text{.}\) Entonces el número de permutaciones con repetición es:
\begin{equation*}
P_{n_{1},n_{2},\ldots,n_{R}}^{n}=\frac{n!}{n_{1}!\cdot n_{2}!\cdot n_{3}
!\cdot\cdot\cdot n_{R}!}
\end{equation*}
Ejemplo 2.6.10
Consideremos tres lápices dos de color rojo (iguales) y uno azul representados por las letras \(R,R,A\text{,}\) tenemos que:
\begin{equation*}
P_{2,1}^{3}=\frac{3!}{2!1!}=3
\end{equation*}
esta número representa la cantidad de arreglos que podemos hacer con los tres lápices, que podemos distinguir
\begin{equation*}
ARR;\quad RAR;\quad RRA
\end{equation*}
Ejemplo 2.6.11
Con las letras de la palabra CONTRATO. ¿Cuántas palabras (agrupación de letras) de cuatro letras se pueden construir?
a) La palabra posee seis letras diferentes, ( C,O,N,T,R,A) luego tenemos:
\begin{equation*}
P_{4}^{6}=\frac{6!}{2!}=360.
\end{equation*}
b) La palabra puede tener dos letras repetidas (OO ; TT), para completar la palabra de cuatro letras se necesitan dos letras más distinta entre ella, es decir la cantidad es
\begin{equation*}
P_{2,1,1}^{4}=\frac{4!}{2!1!1!}=12
\end{equation*}
pero para escoger estas dos letra distintas tengo \(C_{2}^{5}\) posibilidades, es decir
\begin{equation*}
C_{2}^{5}P_{2,1,1}^{4}=\frac{5!}{3!2!}\frac{4!}{2!1!1!}=120
\end{equation*}
pero hemos contado solamente una posibilidad, falta la otra letra, de esta manera tenemos:
\begin{equation*}
2C_{2}^{5}P_{2,1,1}^{4}=2\frac{5!}{3!2!}\frac{4!}{2!1!1!}=240
\end{equation*}
c) Por último nos falta cuando las dos letras repetidas aparecen
\begin{equation*}
P_{2,2}^{4}=\frac{4!}{2!2!}=6
\end{equation*}
Así, finalmente tenemos que el número es:
\begin{equation*}
P_{4}^{6}+2C_{2}^{5}P_{2,1,1}^{4}+P_{2,2}^{4}=\frac{6!}{2!}+2\frac{5!}
{3!2!}\frac{4!}{2!1!1!}+\frac{4!}{2!2!}=360+240+6=606
\end{equation*}
Subsección Ejercicios
Determinar usando dos método distintos, cuántos números de cuatro dígitos mayores que \(5231\) se pueden formar.