Métodos básicos de conteo

Al estudiar la probabilidad de que ocurra un evento se requiere saber con certeza la cantidad de elementos involucrados en dicho evento, por ejemplo: si lanzamos una moneda, ¿cuántas caras tiene la moneda? Si lanzamos un dado, ¿cuántas caras tiene el dado? Si queremos ganar la lotería nacional, ¿cuántos boletos posibles hay? Si queremos pescar un pez dorado en un riachuelo, ¿cuántos peces dorados hay en el riachuelo? ¿Cuántos peces hay de otros colores?

Contar de cuantas formas pudiera ocurrir un evento es tan sencillo como contar con los dedos como por ejemplo lanzar un dado de 6 caras, sin embargo, hay ocasiones en las que la cantidad es muy grande y los dedos de las manos no alcanzan, así que debemos usar los dedos de los pies (jaja, chiste malo).

Hablando seriamente, podemos encontrar eventos con tantos casos que debemos desarrollar métodos que nos permitan contar con precisión todos los casos posibles, por ejemplo, si en los boletos de la lotería nacional se pueden escoger seis números de treinta, ¿cuántos boletos posibles hay?

Dependiendo del evento que estemos estudiando, el método que se usa para contar los posibles casos puede contarse directamente, pero cuando los problemas son más complejos, es necesario sentar una base para abordarlos, así que veremos a continuación los casos que sientan la base para los métodos básicos de conteo.

También pudiera interesarte

Anuncios

El método del producto

Este método que se basa en multiplicar la cantidad de elementos de un conjunto por la cantidad de elementos del otro conjunto se conoce como el método del producto y formalmente, diremos que si evento se puede desglosar de forma secuencial en dos partes, si hay $n_1$ elementos para la primera secuencia y $n_2$ elementos para la segunda secuencia, entonces el evento puede ocurrir de $n_1 \cdot n_2$ formas posibles.

Veamos como aplicar este método de conteo con algunos ejemplos, que si bien pueden resultar bastante intuitivos, formalizar el método permitirá abordar problemas más complejos.

Ejemplos

Ejemplo 1

Consideremos el producto cartesiano de dos conjuntos, particularmente consideremos el producto cartesiano de los conjuntos $A = \{ 1,2,3,4,5,6,7 \}$ y $\{ 1,2,3,4 \}$ , es decir, $\{ (a,b) : a \in A, b \in B \}$ . Este conjunto alberga todas las posibles parejas de elementos de $A$ con elemento de $B$ , ¿Cuántos elementos tiene este producto cartesiano?

Pudiéramos contar uno a uno todos los elementos, empezando por el $(1,1)$ , $(2,1)$ , $(3,1)$ y así sucesivamente, sin embargo, podemos también ilustrar estos dos conjuntos en el plano cartesiano para contar con mayor facilidad.

Observando esta ilustración, no hace falta contar todos los puntos pues observando que estos formar un rectángulo, podemos multiplicar base por altura, para determinar que podemos emparejar los elementos de $A$ con los elementos de $B$ de $7 \cdot 4 = 28$ formas posibles. Notemos que de esta forma podemos contar los elementos de cualquier producto cartesiano.

Ejemplo 2

Una vez ilustrado este ejemplo, sentamos la base para estudiar problemas más complejos de conteo. Por ejemplo, supongamos que usted está organizando un evento de caridad y debe identificar el asiento de cada uno de los asistentes, sabiendo que hay cinco filas A, B, C, D, E y 37 puestos por cada fila. ¿Cuántas etiquetas se deben imprimir?

Básicamente, lo que queremos saber es de cuantas formas podemos emparejar los elementos del conjunto $\{ A, B, C, D, E \}$ y los elementos del conjunto $\{ 1,2,3, \ldots , 37 \}$ . Entonces, si el primer conjunto tiene cinco elementos y el segundo tiene treinta y siete, podemos concluir que se deben imprimir $5 \cdot 37 = 185$ etiquetas.

Anuncios

Ejemplo 3

Estableciendo este método, supongamos que una pequeña empresa fabrica adornos imantados para refrigeradores con forma de libélula, mariposa y escarabajo, que posteriormente son pintados de distintos colores: azul, verde, naranja, amarillo y rojo. ¿Cuántos tipos de adornos imantados fabrica esta empresa?

Lo que queremos saber es de cuantas formas podemos emparejar los elementos del conjunto {libélula, mariposa, escarabajo} y los elementos del conjunto {azul, verde, naranja, amarillo, rojo}. Entonces, si el primer conjunto tiene tres elementos y el segundo tiene cinco, podemos concluir que se deben imprimir $3 \cdot 5 = 15$ tipos de adornos.

Nota: El método del producto se puede generalizar pues si evento se puede desglosar en una secuencia de $k$ partes, si hay $n_1$ elementos para la primera secuencia, $n_2$ elementos para la segunda secuencia y así de forma sucesiva, $n_k$ elementos para la $k$ -ésima secuencia, entonces el evento puede ocurrir de $n_1 \cdot n_2 \cdot \ldots \cdot n_k$ formas posibles.

Ejemplo 4

Un bit es una unidad básica de información sobre un estado lógico con únicamente dos valores, generalmente representados por un cero (0) o un uno (1), aunque pueden pueden también representar positivo (+) y negativo (-), encendido y apagado, verdadero y falso, etc.

La ventaja del uso de los bits como unidades de información, es que se pueden concatenar para generar cadenas de información mucho más complejas como las Direcciones IP (Internet Protocol Address) que son cuatro cadenas de ocho bits usadas para identificar cada dispositivo del mundo conectado a internet. Es por esto que al observar el módem que permite a su computadora conectarse a internet, este enciende y apaga la luz de conexión reiteradas veces.

Entonces, sabiendo lo que es un bit y lo que es una Dirección IP, ¿cuántas Direcciones IP posibles se pueden asignar? Empecemos por determinar cuantas cadenas de 8 bits distintas podemos contar. Básicamente tenemos un evento que se puede desglosar en ocho secuencias y donde cada una tiene dos elementos, entonces, contamos $2 \cdot 2 \cdot \ldots \cdot 2 = 2^8 = 256$ cadenas distintas de ocho bits.

Sabiendo que las Direcciones IP tienen cuatro cadenas de ocho bits, entonces, tenemos un evento que se puede desglosar en cuatro secuencias y donde cada una tiene doscientos cincuenta y seis elementos, entonces, contamos $256 \cdot 256 \cdot 256 \cdot 256 = 256^4 = 4 \ 294 \ 697 \ 296$ cadenas distintas de ocho bits.

Anuncios

El método de la suma

Este método que se basa en sumar la cantidad de elementos de un conjunto con la cantidad de elementos del otro conjunto se conoce como el método de la suma y formalmente, diremos que si un evento se puede desglosar en dos partes y que este ocurre sólo en una de las partes, si hay $n_1$ casos para la primera parte y $n_2$ casos para la segunda parte, entonces el evento puede ocurrir de $n_1 + n_2$ formas posibles.

En términos del cardinal de un conjunto finito, esto es, la cantidad de elementos en el conjunto. Considerando dos conjuntos disjuntos, es decir, que no tienen elementos en común, entonces el cardinal de la unión de estos dos conjuntos es la suma de sus cardinales. Formalmente, si $A$ y $B$ son conjuntos tales $A \cap B = \varnothing$ , entonces

$|A \cup B| = |A| + |B|$

Donde, las barras $| \ * \ |$ denotan el cardinal del conjunto.

Veamos como aplicar este método de conteo con algunos ejemplos, que si bien pueden resultar bastante intuitivos, formalizar el método permitirá abordar problemas más complejos.

Ejemplos

Ejemplo 5

Suponga que usted está presidiendo una reunión de condominio, se cuentan con limitados recursos y sólo puede atenderse uno de dos problemas importantes: restaurar el asfaltado de los estacionamientos o restauración de los depósitos de basura; para el primer problema hay 4 licitaciones y para el segundo problema hay 9 licitaciones. Contar todos los casos posibles es muy sencillo, pues simplemente debemos sumar los casos posibles, entonces contamos $4+9=13$ casos posibles.

Nota: Si bien estos métodos presentan soluciones bastante intuitivas, sientan la base para situaciones que requieren la combinación de métodos conteo.

Ejemplo 6

Suponga que usted está organizando un evento de caridad y debe identificar el asiento de cada uno de los asistentes, sabiendo que se deben imprimir etiquetas personalizadas los 2 representantes de cada una de las 7 asociaciones que colaboran con el evento caritativo y además, seis filas A, B, C, D, E, F y 20 puestos por cada fila. ¿Cuántas etiquetas se deben imprimir?

Desglosamos el conteo en dos partes, contando primero las etiquetas personalizadas, que en este caso serían $2 \cdot 7 = 14$ etiquetas y por otra parte, lo que queremos saber es de cuantas formas podemos emparejar los elementos del conjunto $\{ A,B,C,D,E,F \}$ y los elementos del conjunto $\{ 1,2,3, \ldots , 20 \}$ . Entonces, si el primer conjunto tiene seis elementos y el segundo veinte, podemos concluir que se deben imprimir $6 \cdot 20 = 120$ etiquetas.

Por lo tanto, se deben imprimir un total de $14 + 120 = 134$ etiquetas.

Anuncios

El método de la resta

El método de la resta, también conocido como el Principio de Inclusión-Exclusión, generaliza el método de la suma, y se basa en sumar la cantidad de elementos de un conjunto con la cantidad de elementos del otro conjunto, notando que si estos conjuntos tienen elementos en común estaríamos contando los elementos comunes dos veces, por lo tanto, restamos esa cuenta adicional.

Formalmente, diremos que si un evento se puede desglosar en dos partes y que ambas partes tienen casos comunes, si hay $n_1$ casos para la primera parte y $n_2$ casos para la segunda parte, entonces el evento puede ocurrir de $n_1 + n_2$ formas posibles, menos la cantidad de casos comunes.

En términos del cardinal de un conjunto finito, esto es, la cantidad de elementos en el conjunto. Considerando dos conjuntos con elementos comunes $A$ y $B$ , entonces

$|A \cup B| = |A| + |B| - |A \cap B|$

Donde, las barras $| \ * \ |$ denotan el cardinal del conjunto.

Ejemplos

Ejemplo 7

Suponga que usted está organizando un evento de caridad y debe identificar el asiento de cada uno de los asistentes, sabiendo que se deben imprimir etiquetas personalizadas para los 2 delegaciones que colaboran con el evento caritativo, la primera delegación cuenta con 10 personas y la segunda con 13, pero se sabe que 4 personas pertenecen a ambas delegaciones. ¿Cuántas etiquetas se deben imprimir?

Para la primera delegación se deberían imprimir 10 etiquetas y para la segunda delegación se deberían imprimir 13 etiquetas. Sin embargo, debemos considerar que 4 personas están en ambas delegaciones, si se imprimen estas 4 etiquetas en el lote de la primera delegación y estas mismas 4 etiquetas en el lote de la segunda de legación, se estarían imprimiendo 4 etiquetas de más. Así, estas se imprimen sólo una vez que para evitar imprimir las mismas etiquetas dos veces.

En conclusión, se deben imprimir $10 + 13 - 4 = 23 - 4 = 19$ etiquetas.

Ejemplo 8

Suponga que usted está administrando una red de información de una empresa con un Dominio IP que fija las primeras tres cadenas de bits, y debe determinar cuantas Direcciones IP hay disponibles para los dispositivos del personal administrativo, sabiendo que las direcciones asignadas para estos son las que empiezan 0000 o que terminan en 11.

Contemos la cantidad de direcciones que empiezan en 0000. En vista de que los primeros cuatro bits de estas cadenas están fijos, los restantes cuatro bits varían entre cero y uno, de esta forma, aplicando el método del producto, concluimos que hay $2^4 = 16$ direcciones que cumplen con esta condición.

Contemos la cantidad de direcciones que terminan en 11. En vista de que los dos últimos bits de estas cadenas está fijos, los restantes seis bits varían entre cero y uno, de esta forma, aplicando el método del producto, concluimos que hay $2^6 = 64$ direcciones que cumplen con esta condición.

Debemos tomar en cuenta que estamos contando dos veces las direcciones que empiezan en 0000 y terminan en 11 al mismo tiempo, entonces contemos estas direcciones para restarlas al final. En vista de que los primeros cuatro bits y el último bit de estas cadenas está fijos, los restantes 2 bits varían entre cero y uno, de esta forma, aplicando el método del producto, concluimos que hay $2^2 = 4$ direcciones que cumplen con esta condición.

De esta forma, concluimos que la cantidad de Direcciones IP disponibles para los dispositivos del personal administrativo son $16 + 64 - 4 = 76$

Anuncios

El método de la división

El método de la división permite contar los elementos de un conjunto, ignorando leves diferencias entre un elemento y otro. La idea básicamente consiste en hacer un conteo aplicando los métodos conocidos y posteriormente, combinar aquellos elementos que no presentan mayor diferencia.

Supongamos que al considerar las formas llevar a cabo un evento, este se puede llevar a cabo siguiendo uno de los procedimientos del conjunto $A = \{ a_1,a_2, \ldots a_m \}$ , pero a su vez, este se puede llevar a cabo siguiendo uno los procedimientos del conjunto $B = \{ b_1,b_2, \ldots b_n \}$ . Si para cada procedimiento $b_i$ , existen exactamente $k$ procedimientos de $A$ que coinciden con $b_i$ , entonces el total de formas en las que se puede llevar a cabo el evento es igual a $\frac{m}{k}$ .

En términos del cardinal de un conjunto finito, esto es, la cantidad de elementos en el conjunto. Considerando un conjunto $A$ que es igual a la unión de $n$ conjuntos ${ A_1, A_2, \ldots, A_n }$ , donde $A_i \cap A_j$ para $i \neq j$ . Si $|A_i| = k$ entonces

$n = \frac{|A|}{k}$

Donde, las barras $| \ * \ |$ denotan el cardinal del conjunto.

Otra forma de presentar este método consiste en considerar dos conjuntos finitos $A$ y $B$ , y una función $f : A \to B$ tal que para todo elemento $b$ de $B$ existen exactamente ${ a_1, a_2, \ldots, a_k }$ valores de $A$ tales que $f(a_i) = b$ para todo $i=1, \ldots k$ . Entonces,

$|B| = \frac{|A|}{k}$

Nota: Haciendo la analogía con las funciones inyectivas, también conocidas como funciones $1-1$ . Decimos que la función es $k-1$ pues corresponde a $k$ elementos de $A$ con un único elemento de $B$ y viceversa.

Ejemplos

Ejemplo 9

Suponga que usted está armando un circuito de entrenamiento con únicamente cuatro obstáculos distintos: una valla (V), una ría (R), un muro de 1 metro (M1) y un muro de 2 metros (M2). Considerando que dos circuitos son equivalentes si uno se obtiene rotando el otro, por ejemplo, el circuito V-R-M1-M2 es equivalente al circuito M1-M2-V-R. ¿Cuántos circuitos distintos se pueden crear?

Para fijar el primer obstáculo, podemos considerar cualquier de las cuatro opciones. Para el segundo, ya hemos fijado uno anteriormente, así que debemos considerar sólo las tres opciones restantes. Para el tercero, ya hemos fijado dos anteriormente, así que debemos considerar sólo las dos opciones restantes. Para el cuarto, ya hemos fijado tres, así que consideramos el que queda que es sólo una opción.

Entonces, aplicando el método del producto, podemos contar $4 \cdot 3 \cdot 2 \cdot 1 = 24$ circuitos distintos. Pero debemos notar que para cada arreglo, hay cuatro circuitos equivalentes, por lo que concluimos que sólo hay $\frac{24}{4} = 6$ circuitos distintos.

Anuncios

Diagramas de Árbol

Existen eventos que ocurren de forma secuencial en los que se pueden contar todos los casos posibles con mayor facilidad haciendo una ilustración, como es el caso de los diagramas de árbol en los que se cuentan todos los casos posibles de forma exhaustiva, pues partiendo de un nodo originario (la raíz del diagrama) podemos dibujar aristas (ramas del diagrama) hasta otros nodos, de los cuales se generan otras ramas. De esta forma, se representan todos los casos posibles del evento en cuestión.

Aunque los diagramas de árbol se pueden aprovechar con mayor profundidad desarrollando la Teoría de Grafos, nos limitaremos en esta ocasión con algunos ejemplos básicos para entender la forma en que se usan para los métodos de conteo.

Ejemplos

Ejemplo 10

Considerando cadenas de bits, ¿cuántas cadenas de tres bits diferentes se pueden contar?

Estas cadenas se pueden contar usando el método del producto, pero para efectos didácticos, veamos como se aborda este problema si se usa un diagrama de árbol.

Empezamos contando todas las cadenas que empiezan con $0$ , para esto dibujamos una rama desde la raíz del diagrama que llega hasta $0$ .

A partir de este nodo, parten dos nodos uno con $0$ y otro con $1$ .

A partir de estos nodos, parten a su vez, dos nodos uno con $0$ y otro con $1$ . De esta forma, obtenemos todas las cadenas de bits que empiezan con $0$ .

A partir de este nodo, parten dos nodos uno con $0$ y otro con $1$ .

Hacemos un procedimiento análogo para determinar todas las cadenas de bits que empiezan con $1$ , para esto dibujamos una rama desde la raíz del diagrama que llega hasta $1$ .

A partir de estos nodos, parten a su vez, dos nodos uno con $0$ y otro con $1$ . De esta forma, obtenemos todas las cadenas de bits que empiezan con $0$ .

Entonces, la cantidad de cadenas de bits que se pueden formar con tres bits es igual a la cantidad de nodos que al final no tienen ramificaciones adicionales, es decir, $8$ . Notemos además, que en este diagrama se pueden identificar visualmente todas las cadenas de bits, por ejemplo, la cadena $010$ se ve de la siguiente forma:

Anuncios

Ejemplo 11

Aunque el ejemplo anterior se pudo haber resulto de forma más simple recurriendo al método del producto, consideremos otro ejemplo en que el método del producto no es el mejor método para abordarlo. ¿cuántas cadenas de cuatro bits diferentes no tienen dos ceros consecutivos?

Para esto construimos un diagrama de árbol pero al construir una rama, si un nodo es $0$ , no se continúa construyendo la rama que dirige hacia otro cero.

Entonces, la cantidad de cadenas de bits que se pueden formar con cuatro bits que no tengan dos ceros consecutivos es igual a la cantidad de nodos que al final no tienen ramificaciones adicionales, es decir, $8$ .

Ejemplo 12

En un torneo de «Piedra, Papel o Tijera», la final se disputa entre dos personas y el ganador será el que gane dos de tres partidas. Los organizadores deben contar todos los casos posibles para determinar el tiempo máximo que durará la final del torneo. ¿Cuántas partidas posibles pueden ocurrir?

Identifiquemos a cada jugador como el jugador Azul (A) y el jugador Rojo (R), entonces, construimos un diagrama de árbol de la siguiente manera:

Por lo tanto, concluimos que la cantidad de partidas posibles es $6$ .

2 comentarios en “Métodos básicos de conteo”

Combinatorias – totumat dice:

06.03.2021 a las 10:46 pm

[…] Método del Producto nos indica que la cantidad total de 3-permutaciones será el producto de las opciones para cada […]

Me gustaMe gusta

Responder
Permutaciones – totumat dice:

04.03.2021 a las 10:00 pm

[…] Métodos básicos de conteo […]

Me gustaMe gusta

Responder

¿Tienes alguna duda? Compártela en los comentarios. Cancelar la respuesta

Introduce aquí tu comentario...

Introduce tus datos o haz clic en un icono para iniciar sesión:

Correo electrónico (obligatorio) (La dirección no se hará pública)

Nombre (obligatorio)

Web

Estás comentando usando tu cuenta de WordPress.com. ( Salir / Cambiar )

Estás comentando usando tu cuenta de Facebook. ( Salir / Cambiar )

Cancelar

Conectando a %s

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

El método del producto

Ejemplos

Ejemplo 1

Ejemplo 2

Ejemplo 3

Ejemplo 4

El método de la suma

Ejemplos

Ejemplo 5

Ejemplo 6

El método de la resta

Ejemplos

Ejemplo 7

Ejemplo 8

El método de la división

Ejemplos

Ejemplo 9

Diagramas de Árbol

Ejemplos

Ejemplo 10

Ejemplo 11

Ejemplo 12

Comparte

Related

2 comentarios en “Métodos básicos de conteo”

¿Tienes alguna duda? Compártela en los comentarios. Cancelar la respuesta