Repaso: Análisis combinatorio
Saber cuántos elementos tiene un conjunto o, equivalentemente, saber de cuántas formas puede suceder un evento
pareciera sencillo. Sólo necesitamos enlistar todos los posibles resultados consistentes con el evento y contar. Sin
embargo, no es raro enfrentarnos a problemas para los que no será factible enlistar cada elemento del conjunto. Por
ejemplo, ¾cuántos número de teléfono de 10 digitos existen tales que terminen en 0? El principio de multiplicación
es la base para resolver muchos problemas de conteo.
Proposición. Principio de Multiplicación. Considere un experimento compuesto E que consiste en dos sub-experimentos
E1 y E2 . Suponga además que el experimento E1 tiene m posibles resultados y para cada uno de ellos el experimento
E2 tiene n posibles resultados, entonces el experimento compuesto E tendrá n×m posibles resultados.
Se presentan ahora algunos ejercicios que pueden resolverse con este principio.
Ej. Helados. Una heladería ofrece 10 sabores diferente de helado, así como vaso, cono o wa e.
a) Si cada día quiero ordenar algo que no haya ordenado antes, ¾durante cuántos días consecutivos podré
hacerlo?
b) ¾Cuál sería la respuesta si además la heladería ofrece 5 posibles toppings?
c) Supongamos ahora que compro un helado a medio día y otro a media tarde, ¾de cuántas posibles formas
podría pedir mi par de helados en un día cualquiera, tomando en cuenta que no dese repetir la elección de la
mañana en la tarde?
d) ¾Cuántas formas tendría si no soy tan exigente y permito repetición en la tarde?
e) ¾Y si el orden me es irrelevante? Es decir, ordernar cono-vainlla-chispas (co-va-ch) en la mañana y ordenar
wa e-choco-oreo (wa-ch-or) es lo mismo que ordenar wa-ch-or en la mañana y co-va-ch en la tarde.
Ej. ¾Cuántos subconjuntos podemos construir con los elementos de un conjunto de cardinalidad n?
Observación. El principio de multiplicación no sólo es válido para 2 sub-experimentos o sub-procedimientos, en
general se puede aplicar a k de ellos, como se hizo en los ejercicios anteriores.
Muchos experimentos pueden ser interpretados en términos de tomar muestras con y sin reemplazo. El principio de
multiplicación nos será de utilidad para estos casos.
Muestreo con orden y con reemplazo: Considere n objetos de los cuales se seleccionan k de ellos con
la posibilidad de que un objeto sea seleccionado más de una vez. Usando el principio de multiplicación,
existen nk formas distintas de hacer dicha selección considerando que el orden es importante.
Muestreo con orden y sin reemplazo: Considere n objetos de los cuales se seleccionar k de ellos sin la
posibilidad de que un objeto sea seleccionado más de una vez. Usando el principio de multiplicación,
existen n(n − 1)...(n − k + 1) = (n−k)!
n!
formas distintas de hacer dicha selección considerando que el
orden es importante.
Observación.
1) A estos tipos de muestreo también se les conoce como ordenaciones con y sin repetición respectivamente.
2) El muestreo con reemplazo puede pensarse como seleccionar una canica de una bolsa con n de ellas, regresarla
a la bolsa y volver a sacar otra (esto permite la posibilidad de volver a sacar la misma), así sucesivamente k veces.
3) El caso sin reemplazo se puede pensar como sacar canicas de la bolsa pero no se regresan a ésta, se hacen a
un lado.
4) Para el muestreo sin reemplazo es necesario que k ≤ n, esto contrasta con el muestreo con reemplazo pues k
podría ser mayor, menor, o igual a n.
El caso particular cuando k = n en las ordenaciones sin repetición tiene un nombre especial.
Permutación: El número de formas que se pueden ordenar n objetos está dado por n!.
Ej. ¾Cuántos passwords diferentes se pueden construir de longitud 8 si sólo se permiten 26 letras del abcdario
(tanto mayúsculas como minúsculas) y los 10 dígitos usuales?
1
Ej. Placas de autos
a) ¾Cuántas placas de autos de 7 posiciones pueden construirse tomando en cuenta que los primeros 3 lugares
deben ser letras (26 posibilidades) seguidas de 4 números?
b) ¾Cuántas placas se pueden hacer si adicionalmente se tiene la restricción de no poder repetir letras y
números?
Ej. Se hará una rifa con boletos y habrá premios para el primer, segundo y tercer lugar. Si se venden 500
boletos, ¾de cuántas formas se pueden asignar los premios?
Ej. Un estudiante tiene 20 libros y desea ordenarlos en un estante.
a) Si el estante sólo tiene espacio para 10 libros, ¾de cuántas formas puede ordenarlos?
b) ¾De cuántas formas puede ordenarlos si ahora el estudiante tiene un estante con mayor capacidad que
puede albergar sus 20 libros?
c) Si de esos 20 libros: 10 son de mate, 5 de programación, 3 de nanzas y 2 de literatura, ¾de cúantas formas
pueden ser ordenados tomando en cuenta que el estudiante desea que todos los libros de un mismo tema estén
juntos?
Ej. ¾Cuántas palabras distintas pueden formarse al reordenar las letras de la palabra
a) ITAM?
b) FARAH?
c) COLMILLO?
Así como en el ejemplo anterior, en ocasiones tendemos a contar casos de más, sobre todo cuando el orden no es
importante.
Ej. ¾De cuántas formas podemos formar un comité estudiantil de 5 personas de un total de 100 posibles
estudiantes?
Combinaciones (muestras sin orden y sin reemplazo):
El número de subconjuntos posibles de
tamaño k de un conjunto de tamaño n está dado por n
k = (n−k)!k! .
n!
El término n
también se le conoce como coe ciente binomial pues aparece en el famoso teorema del
Observación.
k
binomio: (a + b)n = nk=0 nk ak bn−k .
P
Observación. La fórmula de las combinaciones puede pensarse también como el número de formas en que se pueden
dividir n objetos en dos grupos, uno de tamaño k y otro de tamaño n − k.
Consideremos ahora un generalización del concepto anterior, se tienen n objetos y se quieren construir m grupos,
el primero de tamaño k1 , el segundo de tamaño k2 , ..., el m-ésimo de tamaño km , de modo que k1 + ... + km = n.
¾De cuántas formas podemos construir esos m grupos tomando en cuenta que los objetos de un mismo grupo serán
indistinguibles?
Coe ciente multinomial: El número de posibles formas en que se pueden construir m grupos (de
tamaños k1 , ..., km ) de un conjunto de n objetos es n
k1 ,...,km = k1 !...km ! .
n!
Observación. Cuando m = 2 el coe ciente multinomial claramente se reduce al coe cinete binomial.
Observación. El teorema del binomio se puede generalizar y es donde aparece el coe ciente multinomial:
X n
n
(a1 + ...am ) = ak1 ...akmm .
k1 , ..., km 1
k1 ,...,km
La suma se realiza sobre todos los posibles enteros k1 , ..., km tales que k1 + ... + km = n.
Llegado este punto nos falta un caso por analizar, hacer k extracciones de una urna con n objetos donde el orden
no es importante, pero cada objeto seleccionado es regresado a la urna por lo que podría ser extraído múltiples
veces. Que el orden no sea importante implica que sólo queremos saber el número de veces que cada objeto fue
seleccionado. Encontrar una expresión para este caso es posible si pensamos el problema de manera diferente.
2
Se tienen n urnas o casillas contiguas y se lanzan k pelotas indistinguibles entre sí, este experimento es equivalente
al descrito anteriormente. Por ejemplo, si la primer urna termina con 5 pelotas será a equivalente a decir que en el
experimento original el primer objeto fue seleccionado 5 veces. Finalmente, tener n urnas contiguas es como tener
una gran urna con n − 1 lugares para poner divisiones, si además queremos colocar k pelotas entonces se necesitan
n + k − 1 lugares para poner pelotas o divisiones.
Muestras sin orden y con reemplazo: El número de posibles formas en
que se pueden extraer k
objetos de un total de n sin considerar orden y con reemplazo es n+k−1 n+k−1
.
k = n−1
Observación. Nuevamente por ser un caso con reemplazo no es necesario que k ≤ n, se pueden tener más pelotas
que urnas.
Ej. a) ¾Cuántas soluciones distintas de números enteros no negativos x1 , ..., xn existen para la ecuación
x1 + ... + xn = r,
donde r ∈ N? En este caso la solución (r, 0, ..., 0) se considera distinta a la solución (0, ..., 0, r).
b) ¾Y si ahora queremos soluciones estrictamente positivas?
Cuadro resumen
Muestras de tamaño k de entre n objetos con orden sin orden
con reemplazo n+k−1
k
n k
sin reemplazo n!/(n − k)! n
k
Contar puede tornarse complicado, al momento de resolver un problema no necesariamente debe caer en alguna
casilla de la tabla anterior. Para el lector interesado en profundizar combinatoria se le sugiere consultar:
Cameron, P. J. (1994). Combinatorics: topics, techniques, algorithms . Cambridge University Press.
Morris. J. (2023). Combinatorics: an upper-level introductory course in enumeration, graph theory,
and design theory .
Disponible libremente en: [Link]
