Suponga que usted está desarrollando un proyecto y debe designar una comisión de tres personas para llevar a cabo ciertas tareas. Entonces, considerando cinco personas, ¿de cuántas formas se puede conformar la comisión? Para responder a esta pregunta, debemos tener clara una definición.
También pudiera interesarte
Anuncios
Considerando una colección de objetos distintos, una r-combinación de estos es simplemente una forma de escoger de estos objetos (sin importar el orden), en términos de conjuntos, podemos decir que una r-combinación es cualquier subconjunto de tamaño de la colección de objetos. Por ejemplo, si tenemos cinco bolas, una azul, una roja, una amarilla, una verde y una naranja; una 3-combinación es la siguiente:
Entonces, considerando todas las 3-combinaciones, incluyendo la que ya vimos, tenemos:
En total podemos contar diez 3-combinaciones, pero listar todas las combinaciones posibles para después contarlas puede resultar en un proceso engorroso cuando tenemos muchos más objetos distintos, es por esto que debemos recurrir a los métodos de conteo que ya hemos visto. Entonces, si queremos tomar tres bolas de las cinco bolas, contemos primero todas las 3-permutaciones posibles:
Para fijar la primera bola, podemos considerar cinco opciones. Notemos que si contamos combinaciones, cualquiera de las tres posiciones es indiferente.
Para fijar la segunda bola, como ya hemos fijado una, podemos considerar sólo cuatro opciones. Notemos que si contamos combinaciones, cualquiera de las dos posiciones restantes es indiferente.
Para fijar la tercera bola, como ya hemos fijado dos, podemos considerar sólo tres opciones. Notemos que si contamos combinaciones, la última posición es indiferente.
El Método del Producto nos indica que la cantidad total de 3-permutaciones será el producto de las opciones para cada posición, es decir, .
Pero debemos tomar en cuenta que la posición en la que estas se encuentran es indiferente, el Método del Producto nos indica que la cantidad total posiciones indiferentes será el producto de las posiciones indiferentes cuando se ha fijado cada bola, es decir, .
De esta forma, el Método de la División nos indica que la cantidad de 3-combinaciones, será la división de todas las 3-permutaciones entre todos los casos indiferentes, es decir,
De formar general, si consideramos n objetos distintos, el total de r-combinaciones distintas se calcula con la siguiente división:
Las r-combinaciones de objetos se denota de la forma , y usando permutaciones, también podemos reescribir el cociente que las definen de la siguiente forma:
Usando expresiones factoriales, también podemos expresar las r-combinaciones como el coeficiente binomial:
Tomando en cuenta que el factorial de cero es igual a uno, es decir, $latex0! = 1$. Entonces, notamos que una n-combinación de una colección de n objetos, es exactamente igual a uno. Veamos con algunos ejemplos como contar todas las r-combinaciones en distintas situaciones.
Anuncios
Ejemplos
Ejemplo 1
Suponga que usted está desarrollando un proyecto y debe designar una comisión de tres personas para llevar a cabo ciertas tareas. Entonces, considerando cinco personas, ¿de cuántas formas se puede conformar la comisión?
Este problema se puede abordar contando todas las 3-combinaciones posibles de cinco objetos y estas son:
Ejemplo 2
Considerando una bolsa con siete bolas de distinto color, si se sacan cuatro bolas, ¿de cuántas formas distintas se pueden sacar cuatro de ellas?
Este problema se puede abordar contando todas las 4-combinaciones posibles de siete objetos y estas son:
Ejemplo 3
En una carrera de 100 metros planos compiten ocho personas, si a las tres últimas personas se les da un premio por participar indistintamente, ¿de cuántas formas posibles pueden otorgarse estos premios al culminar esta carrera?
Este problema se puede abordar contando todas las 3-combinaciones posibles de ocho objetos y estas son:
Suponga que usted está desarrollando un proyecto y debe designar una comisión de tres personas para llevar a cabo ciertas tareas. Esta comisión debe tener un coordinador, un secretario y un vocero. Entonces, considerando tres personas, ¿de cuántas formas se puede conformar la comisión? Para responder a esta pregunta, debemos tener clara una definición.
También pudiera interesarte
Anuncios
Considerando una colección de objetos distintos, una permutación de estos es simplemente una forma de ordenarlos uno tras otro. Por ejemplo, si tenemos tres bolas, una azul, una roja y una amarilla, una permutación es la siguiente:
Y reordenándolas, consideremos todas las permutaciones, incluyendo la que ya vimos
En total podemos contar seis permutaciones, pero listar todas las permutaciones posibles para después contarlas puede resultar en un proceso engorroso cuando tenemos muchos más objetos distintos, es por esto que debemos entonces recurrir a los métodos de conteo que ya hemos visto. Entonces, si queremos ordenar estas tres bolas:
Para fijar la primera bola, podemos considerar tres opciones.
Para fijar la segunda bola, como ya hemos fijado una, podemos considerar sólo dos opciones.
Para fijar la tercera bola, como ya hemos fijado dos, podemos considerar sólo una opción.
El Método del Producto nos indica que la cantidad total de permutaciones será el producto de las opciones para cada posición, es decir, .
De formar general, si consideramos objetos distintos, el total de permutaciones distintas se calcula con el siguiente producto:
Este producto se puede resumir usando la notación de factorial, que se expresa con un signo de exclamación de la siguiente forma:
Veamos con algunos ejemplos como contar todas las permutaciones en distintas situaciones.
Anuncios
Ejemplos
Ejemplo 1
Suponga que usted está desarrollando un proyecto y debe designar una comisión de tres personas para llevar a cabo ciertas tareas. Esta comisión debe tener un coordinador, un secretario y un vocero. Entonces, considerando tres personas, ¿de cuántas formas se puede conformar la comisión?
Este problema se puede abordar contando todas las formas en que se pueden ordenar tres personas, es decir, contando todas las permutaciones posibles de tres objetos y estas son:
Ejemplo 2
Considerando una bolsa con cinco bolas de distinto color, si se sacan todas una a una, ¿de cuántas formas distintas se pueden sacar?
Este problema se puede abordar contando todas las formas en que se pueden ordenar cinco bolas de distinto color, es decir, contando todas las permutaciones posibles de cinco objetos y estas son:
Ejemplo 3
En una carrera de 100 metros planos compiten ocho personas, ¿de cuántas formas posibles puede culminar esta carrera?
Este problema se puede abordar contando todas las formas en que se pueden ordenar ocho personas, es decir, contando todas las permutaciones posibles de ocho objetos y estas son:
Anuncios
r-Permutaciones
Habiendo definido las permutaciones de una colección de objetos, pueden surgir otro tipo de situaciones. Suponga que usted está desarrollando un proyecto y debe designar una comisión de tres personas para llevar a cabo ciertas tareas. Esta comisión debe tener un coordinador, un secretario y un vocero. Entonces, considerando 5 personas, ¿de cuántas formas podemos conformar la comisión? Para responder a esta pregunta, debemos tener clara una definición.
Considerando una colección de objetos distintos, una r-permutación de estos es simplemente una forma de ordenar de estos objetos uno tras otro. Por ejemplo, si tenemos cuatro bolas, una azul, una roja, una amarilla y una verde. Una 3-permutación es la siguiente:
Y reordenándolas, consideremos todas las 3-permutaciones, incluyendo la que ya vimos
En total podemos contar veinticuatro permutaciones, pero listar todas las permutaciones posibles para después contarlas puede resultar en un proceso engorroso cuando tenemos muchos más objetos distintos, es por esto que debemos entonces recurrir a los métodos de conteo que ya hemos visto. Entonces, si queremos ordenar tres bolas de las cuatro bolas:
Para fijar la primera bola, podemos considerar cuatro opciones.
Para fijar la segunda bola, como ya hemos fijado una, podemos considerar sólo tres opciones.
Para fijar la tercera bola, como ya hemos fijado dos, podemos considerar sólo dos opciones.
El Método del Producto nos indica que la cantidad total de 3-permutaciones será el producto de las opciones para cada posición, es decir, .
De formar general, si consideramos objetos distintos, el total de r-permutaciones distintas se calcula con el siguiente producto:
Las r-permutaciones de objetos se denota de la forma , y usando expresiones factoriales, también podemos reescribir el producto que las definen de la siguiente forma:
Tomando en cuenta que el factorial de cero es igual a uno, es decir, . Entonces, notamos que una n-permutación de una colección de n objetos, es justamente una permutación como la hemos definido originalmente. Veamos con algunos ejemplos como contar todas las r-permutaciones en distintas situaciones.
Anuncios
Ejemplos
Ejemplo 4
Suponga que usted está desarrollando un proyecto y debe designar una comisión de tres personas para llevar a cabo ciertas tareas. Esta comisión debe tener un coordinador, un secretario y un vocero. Entonces, considerando cinco personas, ¿de cuántas formas se puede conformar la comisión?
Este problema se puede abordar contando todas las 3-permutaciones posibles de cinco objetos y estas son:
Ejemplo 5
Considerando una bolsa con siete bolas de distinto color, si se sacan cuatro bolas una a una, ¿de cuántas formas distintas se pueden sacar cuatro de ellas?
Este problema se puede abordar contando todas las 4-permutaciones posibles de siete objetos y estas son:
Ejemplo 6
En una carrera de 100 metros planos compiten ocho personas, ¿de cuántas formas posibles pueden otorgarse las medallas de oro, plata y bronce al culminar esta carrera?
Este problema se puede abordar contando todas las 3-permutaciones posibles de ocho objetos y estas son:
Suponga que usted está en una plaza observando las palomas que pululan en ella, la bandada que vive en la zona cuenta con once palomas y usted observa que en su totalidad, hay diez nidos en una hilera, cuando las palomas retornan una a una a sus hogares la primera va al primer nido, la segunda al segundo nido, la tercera al tercer nido, y así sucesivamente, la décima al décimo nido pero… ¿A dónde va la última paloma? Pues inevitablemente, esta tiene que compartir el nido con alguna de las otras palomas.
El Principio de Dirichlet, popularmente conocido como El Principio del Palomar, establece que considerando cajas, si en ellas se meten o más objetos, entonces habrá al menos una caja que contiene al menos dos de estos objetos.
Este principio tiene su interpretación al considerar funciones, y es que si y son dos conjuntos con cardinales y , respectivamente (esto es la cantidad de elementos que ellos contienen). Entonces, cualquier función definida de en no es inyectiva.
Consideremos algunos ejemplos prácticos de este principio para entender cómo se aplica.
También pudiera interesarte
Anuncios
Ejemplos
Ejemplo 1
Suponga que usted es un médico que trata casos complejos, si atiende sólo de lunes a viernes, y debe practicar una consulta a 6 pacientes en una semana. Entonces, necesariamente debe atender a dos pacientes en un mismo día de la semana.
Ejemplo 2
Si en una clase de 16 estudiantes, se efectúa una evaluación cuya calificación tiene un rango entre 0 y 10 puntos. Entonces, se puede garantizar que habrán al menos dos estudiantes con la misma calificación.
Ejemplo 3
Si se efectúa una evaluación cuya calificación tiene un rango entre 0 y 20 puntos. ¿Cuál es la cantidad mínima de estudiantes que debe haber para garantizar que al menos dos tengan la misma calificación?
Podemos abordar este problema usando el principio del palomar, pues si consideramos el rango de las calificaciones hay 21 opciones . Entonces, básicamente, si contamos con 21 cajas, deberían haber al menos estudiantes para garantizar que al menos dos tengan la misma calificación.
Anuncios
Estos ejemplos pudieran resultar sencillos, pero el Principio del Palomar tiene mayor utilidad para asentar afirmaciones sobre números enteros. Un ejemplo de esto es la siguiente afirmación:
Para todo número entero, existe un múltiplo de este número cuyos dígitos son ceros o unos. Es decir, para todo número entero , existe un número entero tal que
Donde es cero o uno.
Demostración:
Para demostrar esta afirmación, definamos el siguiente conjunto:
Debemos notar que y que cada elemento del conjunto está definido de la forma
.
Considerando el algoritmo de la división, debemos notar que cualquier número entero se puede expresar de la forma y al ser , podemos asegurar que existen posibles restos. Entonces, al dividir obtendremos un resto , al dividir obtendremos un resto , y así sucesivamente, al dividir obtendremos un resto .
De esta forma, obtenemos restos al efectuar cada una de estas divisiones pero ya hemos visto que hay posibles restos al dividir por , así, recurriendo al Principio del Palomar, concluimos que al menos dos de estos restos deben ser iguales. Es decir, existen dos elementos de , digamos , tal que y . Entonces, si consideramos la resta del mayor menos el menor, obtenemos que
De donde concluimos que el número es un múltiplo de y además, notamos que esta resta es igual a
Por lo tanto, es un múltiplo de que cuyos dígitos son ceros o unos.
Hemos visto que el Principio del Palomar nos ayuda a garantizar cuando hay al menos dos elementos en una caja, por ejemplo, si contamos con 5 sacos e introducimos naranjas en ellos, ¿al menos cuántas naranjas debemos tener para garantizar que habrán al menos dos en un saco? La respuesta es 6.
Pero, ¿al menos cuántas naranjas deben haber para garantizar que habrán al menos tres en un saco? ¿O al menos cuatro? ¿Cinco? Para responder a estas preguntas, veamos que este principio se puede generalizar pero primero debemos definir algunas funciones especiales.
Anuncios
Funciones de parte entera
La función pisoredondea todo número decimal hacia abajo, formalmente, para todo número entero , definimos la función piso como una función de la forma y de forma general, está definida como si .
La función techoredondea todo número decimal hacia arriba, formalmente, para todo número entero , definimos la función techo como una función de la forma y de forma general, está definida como si .
El Principio del Palomar Generalizado
El Principio del Palomar Generalizado, establece que considerando cajas, si en ellas se meten objetos, entonces habrá al menos una caja que contiene al menos de estos objetos.
Cuando no sabemos con certeza la cantidad de elementos en un conjunto, este principio nos ayuda principalmente a fijar cotas inferiores. Consideremos algunos ejemplos prácticos de este principio para entender cómo se aplica.
Anuncios
Ejemplos
Ejemplo 4
Si contamos con 5 sacos e introducimos naranjas en ellos, ¿al menos cuántas naranjas debemos tener para garantizar que habrán al menos tres en un saco? En términos del principio del palomar, si tenemos objetos y 5 cajas, ¿cuál es el mínimo valor de para que ?
Si , esto implica que es un elemento del intervalo . Entonces, considerando el extremo inferior de este intervalo, el menor número entero que estamos buscando es tal que , y en efecto, veamos el peor de los casos que es cuando distribuimos los objetos uno a uno:
Si consideramos cinco sacos vacíos:
E introducimos cinco naranjas, cada una en cada saco
Luego, introducimos cinco naranjas más, cada una en cada saco
Contamos diez naranjas, pero si consideramos una naranja adicional (la onceava), sea cual sea el saco en donde la metamos, tendremos un saco con tres naranjas en él.
Ejemplo 5
Considerando un mazo de barajas de 52 cartas, es decir, 13 corazones, 13 picas, 13 diamantes y 13 tréboles. ¿Cuántas cartas debe tomar una persona, para garantizar que al menos 3 son de la misma pinta? En términos del principio del palomar, si tenemos objetos y 4 cajas, ¿cuál es el mínimo valor de para que ?
Si , esto implica que es un elemento del intervalo . Entonces, considerando el extremo inferior de este intervalo, el menor número entero que estamos buscando es tal que , y en efecto, veamos el peor de los casos que es cuando:
Tomando las primeras cuatro cuartas, todas son de diferente pinta,
Tomamos cuatro cartas más, y todas son nuevamente, de diferente pinta,
Contamos ocho cartas, pero si tomamos una carta adicional (la novena), sea cual sea la carta que tomemos, esta será de alguna de las cuatro pintas.
Nota: Cuando se menciona el peor de los casos, es para evitar considerar aquellos casos en los que se cumple la condición que estamos buscando, pero no necesariamente siendo esta la regla general.
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 elementos para la primera secuencia y elementos para la segunda secuencia, entonces el evento puede ocurrir de 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 y , es decir, . Este conjunto alberga todas las posibles parejas de elementos de con elemento de , ¿Cuántos elementos tiene este producto cartesiano?
Pudiéramos contar uno a uno todos los elementos, empezando por el , , 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 con los elementos de de 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 y los elementos del conjunto . Entonces, si el primer conjunto tiene cinco elementos y el segundo tiene treinta y siete, podemos concluir que se deben imprimir 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 tipos de adornos.
Nota: El método del producto se puede generalizar pues si evento se puede desglosar en una secuencia de partes, si hay elementos para la primera secuencia, elementos para la segunda secuencia y así de forma sucesiva, elementos para la -ésima secuencia, entonces el evento puede ocurrir de 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 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 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 casos para la primera parte y casos para la segunda parte, entonces el evento puede ocurrir de 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 y son conjuntos tales , entonces
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 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 etiquetas y por otra parte, lo que queremos saber es de cuantas formas podemos emparejar los elementos del conjunto y los elementos del conjunto . Entonces, si el primer conjunto tiene seis elementos y el segundo veinte, podemos concluir que se deben imprimir etiquetas.
Por lo tanto, se deben imprimir un total de 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 casos para la primera parte y casos para la segunda parte, entonces el evento puede ocurrir de 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 y , entonces
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 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 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 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 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
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 , pero a su vez, este se puede llevar a cabo siguiendo uno los procedimientos del conjunto . Si para cada procedimiento , existen exactamente procedimientos de que coinciden con , entonces el total de formas en las que se puede llevar a cabo el evento es igual a .
En términos del cardinal de un conjunto finito, esto es, la cantidad de elementos en el conjunto. Considerando un conjunto que es igual a la unión de conjuntos , donde para . Si entonces
Donde, las barras denotan el cardinal del conjunto.
Otra forma de presentar este método consiste en considerar dos conjuntos finitos y , y una función tal que para todo elemento de existen exactamente valores de tales que para todo . Entonces,
Nota: Haciendo la analogía con las funciones inyectivas, también conocidas como funciones . Decimos que la función es pues corresponde a elementos de con un único elemento de 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 circuitos distintos. Pero debemos notar que para cada arreglo, hay cuatro circuitos equivalentes, por lo que concluimos que sólo hay 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 , para esto dibujamos una rama desde la raíz del diagrama que llega hasta .
A partir de este nodo, parten dos nodos uno con y otro con .
A partir de estos nodos, parten a su vez, dos nodos uno con y otro con . De esta forma, obtenemos todas las cadenas de bits que empiezan con .
A partir de este nodo, parten dos nodos uno con y otro con .
Hacemos un procedimiento análogo para determinar todas las cadenas de bits que empiezan con , para esto dibujamos una rama desde la raíz del diagrama que llega hasta .
A partir de estos nodos, parten a su vez, dos nodos uno con y otro con . De esta forma, obtenemos todas las cadenas de bits que empiezan con .
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, . Notemos además, que en este diagrama se pueden identificar visualmente todas las cadenas de bits, por ejemplo, la cadena 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 , 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, .
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 .
.
, y usando expresiones factoriales, también podemos reescribir el producto que las definen de la siguiente forma:
. Entonces, notamos que una n-permutación de una colección de n objetos, es justamente una permutación como la hemos definido originalmente. Veamos con algunos ejemplos como contar todas las r-permutaciones en distintas situaciones.
o más objetos, entonces habrá al menos una caja que contiene al menos dos de estos objetos.
y 
son dos conjuntos con cardinales 
. Entonces, básicamente, si contamos con 21 cajas, deberían haber al menos 
estudiantes para garantizar que al menos dos tengan la misma calificación.
, existe un número entero 
tal que
es cero o uno.
y que cada elemento 
del conjunto 
.
y al ser 
, podemos asegurar que existen 
obtendremos un resto 
, al dividir 
obtendremos un resto 
, y así sucesivamente, al dividir 
obtendremos un resto 
.
restos al efectuar cada una de estas divisiones pero ya hemos visto que hay 
, tal que 
y 
. Entonces, si consideramos la resta del mayor menos el menor, obtenemos que
es un múltiplo de 
, definimos la función piso como una función ![\lfloor \ \ \rfloor : [a,a+1] \to \mathbb{Z}](https://s0.wp.com/latex.php?latex=%5Clfloor+%5C+%5C+%5Crfloor+%3A+%5Ba%2Ca%2B1%5D+%5Cto+%5Cmathbb%7BZ%7D&bg=ffffff&fg=5e5e5e&s=0&c=20201002)
de la forma 
y de forma general, 
está definida como 
.
, definimos la función techo como una función ![\lceil \ \ \rceil : (b-1,b] \to \mathbb{Z}](https://s0.wp.com/latex.php?latex=%5Clceil+%5C+%5C+%5Crceil+%3A+%28b-1%2Cb%5D+%5Cto+%5Cmathbb%7BZ%7D&bg=ffffff&fg=5e5e5e&s=0&c=20201002)
de la forma 
y de forma general, 
está definida como 
si 
.
cajas, si en ellas se meten 
de estos objetos.
?
es un elemento del intervalo ![(2,3]](https://s0.wp.com/latex.php?latex=%282%2C3%5D&bg=ffffff&fg=5e5e5e&s=0&c=20201002)
. Entonces, considerando el extremo inferior de este intervalo, el menor número entero 
, y en efecto, veamos el peor de los casos que es cuando distribuimos los objetos uno a uno:
?
es un elemento del intervalo 
, y en efecto, veamos el peor de los casos que es cuando:
elementos para la primera secuencia y 
elementos para la segunda secuencia, entonces el evento puede ocurrir de 
formas posibles.
y 
, es decir, 
. Este conjunto alberga todas las posibles parejas de elementos de 
, 
, 
y así sucesivamente, sin embargo, podemos también ilustrar estos dos conjuntos en el plano cartesiano para contar con mayor facilidad.
formas posibles. Notemos que de esta forma podemos contar los elementos de cualquier producto cartesiano.
y los elementos del conjunto 
. Entonces, si el primer conjunto tiene cinco elementos y el segundo tiene treinta y siete, podemos concluir que se deben imprimir 
etiquetas.
tipos de adornos.
elementos para la 
formas posibles.
cadenas distintas de ocho bits.
cadenas distintas de ocho bits.
formas posibles.
, entonces
denotan el cardinal del conjunto.
casos posibles.
etiquetas y por otra parte, lo que queremos saber es de cuantas formas podemos emparejar los elementos del conjunto 
y los elementos del conjunto 
. Entonces, si el primer conjunto tiene seis elementos y el segundo veinte, podemos concluir que se deben imprimir 
etiquetas.
etiquetas.
etiquetas.
direcciones que cumplen con esta condición.
direcciones que cumplen con esta condición.
direcciones que cumplen con esta condición.
, pero a su vez, este se puede llevar a cabo siguiendo uno los procedimientos del conjunto 
. Si para cada procedimiento 
, existen exactamente 
.
, donde 
para 
. Si 
entonces
tal que para todo elemento 
valores de 
para todo 
. Entonces,
. Decimos que la función es 
pues corresponde a 
circuitos distintos. Pero debemos notar que para cada arreglo, hay cuatro circuitos equivalentes, por lo que concluimos que sólo hay 
circuitos distintos.
, para esto dibujamos una rama desde la raíz del diagrama que llega hasta 
.
. Notemos además, que en este diagrama se pueden identificar visualmente todas las cadenas de bits, por ejemplo, la cadena 
se ve de la siguiente forma:
.
totumat 