Conteo
La enumeración, o conteo, puede
parecer un proceso obvio que un estudiante aprende al estudiar aritmética por
primera vez. Pero luego comúnmente se presta poca atención a un desarrollo más
amplio del conteo, pasando a áreas “más difíciles” de las matemáticas, como
álgebra, cálculo, etc. El conteo no termina con la aritmética, también tiene
aplicaciones en áreas como la teoría de códigos, la probabilidad y estadística,
y el análisis de algoritmos. Para estos eventos difíciles de cuantificar, son
usadas las técnicas de conteo.
Nuestro primer principio del
conteo es:
Regla de la suma: Si una primera tarea puede realizarse de \(m\) formas, mientras que una segunda tarea puede realizarse de \(n\) formas, y no es posible realizar ambas
tareas de manera simultánea, entonces, para llevar a cabo cualquiera de ellas
pueden utilizarse cualquiera de \(m+n\) formas.
Ejemplo:
La biblioteca de una universidad tiene 40 libros de texto de
sociología y 50 de antropología. Por la regla de la suma, un estudiante de esta
universidad puede elegir entre 40+50 = 90 libros de texto para aprender acerca
de alguno de estos dos temas.
Nuestro
segundo principio del conteo será:
Regla del producto: Si
un procedimiento se puede descomponer en las etapas primera y segunda, y si
existen \(m\) resultados posibles de la
primera etapa y si, para cada uno de estos resultados, existen \(n\) resultados posibles para la segunda
etapa, entonces el procedimiento total se puede realizar de \(mn\) formas.
Ejemplo:
El club de teatro de una universidad realiza ensayos para
una obra que se montará en primavera. Si 6 hombres y 8 mujeres ensayan para los
papeles principales (masculino y femenino), por la regla del producto, el
director puede elegir a la pareja principal de 6x8 = 48 formas.
A partir de estos dos principios, se derivan tres técnicas de conteo que enumeramos a continuación:
- Permutaciones o Arreglos
- Combinaciones
- Diagrama de árbol. (no abordaremos en este artículo).
Permutaciones
Dada una colección de n objetos distintos, cualquier disposición (lineal) de estos objetos se denomina permutación de la colección.
(Notar que el orden importa).
Ejemplo:
Si partimos de las letras a, b, c, veremos que hay 6 formas de disponerlas, o permutarlas: abc, acb, bac, bca, cab, cba.
Dados los \(n\) elementos \(n_1\), ..., \(n_n\), sea \(r\) un número natural tal que \(1\le r\le n\) una permutación sin repetición de orden \(r\) de dichos elementos,
es un subconjunto ordenado de \(r\) elementos diferentes elegidos entre los \(n\) posibles.
Así es: Las permutaciones representan un arreglo ordenado de \(r\) objetos tomados de \(n\), en donde \(r\le n\)
\(P_r^n\ =\ \frac{n!}{\left(n-r\right)!}\)
Permutaciones con repetición
\(PR_r^n = r^n\)
En general, si existen n objetos con \(n_1\) del primer tipo, \(n_2\) del segundo tipo, ... y \(n_r\) de un \(r\)-ésimo tipo, donde \(n_1\) + \(n_2\) + ... + \(n_r\)= \(n\), entonces existen \(\frac{n!}{n_1!\ n_2!\ ...\ n_r!}\\) disposiciones (lineales) de los \(n\) objetos dados. (Los objetos del mismo tipo son indistinguibles.)
\(PR_r^n=\ \frac{n!}{n_1!\ n_2!\ n_3!}\)
Combinaciones
En general, si partimos de \(n\) objetos distintos, cada selección o combinación de \(r\) de estos objetos, donde el orden no importa, corresponde a \(r!\) permutaciones de tamaño \(r\) de los \(n\) objetos. Así, el número de combinaciones de tamaño \(r\) de una colección de tamaño \(n\), que se denota \(C(n,r)\), donde \(0\le r\le n\) satisface \((r!) * C(n,r)\) = \(P(n,r)\); por lo que
\(C(n,r)=\ \frac{n!}{r! * (n - r)!}\)
Ejemplo:
Miriam quiere dar una fiesta para algunos miembros de su comité de caridad. Debido al tamaño de su casa, sólo puede invitar a 11 de los 20 miembros de su comité. El orden no es importante, de modo que puede invitar a los 11 de \(C(20,11)\) = \(20!(11!9!)\) = \(167,960\) formas. Sin embargo, una vez que lleguen los 11, la forma en que ella los siente en torno de su mesa rectangular es un problema de disposiciones.
Combinaciones con repetición
\(CR(n,r)\) = \(C(n+r-1,r)\)